Does there exist a positive integer $m$, such that if $S_n$ denotes the lcm of $1,2, \ldots, n$, then $S_{m+1}=4S_m$?
Problem
Source: ARO Regional stage 2023 9.6=10.6=11.6
Tags: number theory, least common multiple, Russia
16.02.2023 16:43
Perhaps you meant $S_{m+1}=4S_m$ (clearly $S_{m+1}\ge S_m$). Assuming this, the answer is no. Notice $m$ is odd and that $2+\textstyle \max_{1\le i\le m}v_2(i) = v_2(m+1)$. But we also have $v_2(m+1) = v_2((m+1)/2)+1 \le 1+\textstyle \max_{1\le i\le m}v_2(i)$. So, a contradiction.
16.02.2023 16:45
Yeah, sorry, fixed.
05.03.2023 11:17
More generally, the quotient $\frac{S_{m+1}}{S_m}$ is always either $1$ (if $m+1$ is not a prime power) or a prime (if $m+1$ is a prime power).
05.03.2023 12:12
@above is it true Thanks i will rember this if it is true I have thinked so hard and come to this fact that If $S_m=p_1^{a_1}\cdots p_n^{a_n}$ Then $S_{m+1}=p_1^{a_1}\cdots p_n^{a_n}\cdot {p_{n+1}}^{a_{n+1}}$ (Added $p_{n+1}$ because at most there another prime can be added) Then i have 2 qtns now 1) the powers $a_1$ etc will increase by only 1 as only one number is increased ? 2) how many powers number will change? Thank you
05.03.2023 12:19
Again, if $m+1$ is not a prime power, then clearly $S_{m+1}=S_m$ as $m+1$ can be written as $m+1=ab$ with $a,b \le m$ coprime. On the other hand, if $m+1=p^k$, then $S_{m+1}$ is divisible by $p^k$ while $S_m$ is only divisible by $p^{k-1}$ and all other primes don't change, so $S_{m+1}=pS_m$.
31.03.2023 18:47
06.02.2024 17:20
Quite a standard technique. Assume that, $m+1=p_1^{z_1}p_2^{z_2}\ldots p_k^{z_k}$ wherein $k \in \mathbb{N}$. The rest of the sequences follow the typical definition we use. Let us take, $f(n)$ denotes the number of primes dividing n. So in our case, $f(m+1)=k$. We also take into count that the form is strict i.e $p_i \neq 1$ and the exponents cannot become zero. Now, in such a scenario notice that since $p_i^{z_i}<m+1$ for $i \in {1,2,\cdots,k}$ for $f(m+1)=2,3,\cdots,k$. This strongly implies that since the numbers have already occurred previously the lcm function is going to concatenate them as in $S_m=S_{m+1}$ and we need to make sure that all $p_i<m$ for $p_i \mid m+1$ is guaranteed which is our edge case. Now, consider case $f(m+1)=1$ where, $m+1=p^z$ and then by general definition of $v_p$ we have $v_p(S_m)=z-1$ and a little observation shows that $S_{m+1}=pS_m$ since the other factors are still the same. Obviously $p \neq 4$ in any case. Finally, we have our edge case where $p_i \mid m+1$ but $p_i \not\leq m$. This implies $m+1$ is prime but then $S_{m+1}=(m+1)S_m$ and again $m=3$ is invalid. Thus, we conclude that no such m exist. Q.E.D $\blacksquare$