Find all pairs of positive integers $(m,n)$ such that $$lcm(1,2,\dots,n)=m!$$where $lcm(1,2,\dots,n)$ is the smallest positive integer multiple of all $1,2,\dots n-1$ and $n$.
Problem
Source: OlimphÃada 2024 - Problem 1
Tags: number theory, least common multiple, factorial
29.01.2024 04:35
The answer is $(1,1)$ $(2,2)$ and $(3,3)$ According to Betrand-Tchebychev Thm, the largest prime not greater than is at least $0.5n$, so $m\geq0.5n$ Then $v_2(m!)$ is at least $m/2\geq0.25n$ However, $v_2(lcm(1,2,\dots,n))$ is precisely $log_2(n)$ So we have $log_2(n)\geq0.25n$ , which implies $n\leq16$ After checking each $n$, we finally get the answer.
20.06.2024 18:34
Answer: $\boxed{(1,1),(2,2),(3,3)}$ Bertrand's postulate guarantees the existence of a prime $m<p\leq 2m$. Thus we must have $n<2m$. Consider the unique integer $k$ such that $2^k<m\leq 2^{k+1}$. Then $$v_2(m!)\geq v_2(2^k!)=2^k-1$$$$v_2(\text{lcm} (1,2,\dots, n))\leq v_2(\text{lcm} (1,2,\dots, 2^{k+2}-1))=k+1$$Thus we must have $k+1 \geq 2^k-1\Rightarrow k\leq 2$ . So we only need to check $1\leq m \leq 8$ leading to the above solutions.
04.01.2025 22:33
Claim 1: $lcm(1,2,\dots,n)<n!$ if $n>3$ Proof: if $n>3$ then n at least is $4$ so in $lcm$ when we count $4$ we don't count $2$ which is half of $n!$ so $lcm(1,2,\dots,n)<n!$ Claim 2: $m<n<2m$ So now we have $lcm(1,2,\dots,n)=m!<n!\implies n>m$ By chebyshev's theorem we know that $m<p<2m$ always exists $p$ and $m$ so $n<2m$ Let's say $2^t<m<2^{t+1}\implies v_2(m!)>v_2(2^t!)=2^t-1$ since $n<2^{t+2}-1\implies v_2(lcm(1,2,\dots,n))<v_2(lcm(1,2,\dots,2^{t+2}-1))=t+1$ So we get $t+1\geq 2^t-1\implies 2\geq t\implies 1\leq m\leq 8$ So if $8\geq m\implies 16\geq n$ Case 1:$n=16\implies lcm(1,2,\dots,16)=720720\neq m!$ Case 2:$n=15\implies lcm(1,2,\dots,15)=360360\neq m!$ Case 3:$n=14\implies lcm(1,2,\dots,14)=360360\neq m!$ Case 4:$n=13\implies lcm(1,2,\dots,13)=360360\neq m!$ Case 5:$n=12\implies lcm(1,2,\dots,12)=27720\neq m!$ Case 6:$n=11\implies lcm(1,2,\dots,11)=27720\neq m!$ Case 7:$n=10\implies lcm(1,2,\dots,10)=2520\neq m!$ Case 8:$n=9\implies lcm(1,2,\dots,9)=2520\neq m!$ Case 9:$n=8\implies lcm(1,2,\dots,8)=840\neq m!$ Case 10:$n=7\implies lcm(1,2,\dots,7)=420\neq m!$ Case 11:$n=6\implies lcm(1,2,\dots,6)=60\neq m!$ Case 12:$n=5\implies lcm(1,2,\dots,5)=60\neq m!$ Case 13:$n=4\implies lcm(1,2,\dots,4)=12\neq m!$ So if $3\geq n$ Case 14:$n=3\implies lcm(1,2,3)=6=m!\implies m=3$ Case 15:$n=2\implies lcm(1,2)=2=m!\implies m=2$ Case 16:$n=1\implies lcm(1)=1=m!\implies m=1$ $\boxed{ANSWER: (m,n)=(3,3),(2,2),(1,1)}$