Determine all natural $ n$ for which there exists natural $ m$ divisible by all natural numbers from 1 to $ n$ but not divisible by any of the numbers $ n + 1$, $ n + 2$, $ n + 3$.
Problem
Source: Croatia TST 2009
Tags: number theory unsolved, number theory
15.04.2009 17:49
If $ n+1 \neq p^k$ for prime $ p$, then We can find two coprime factors of $ n+1$ , say $ a,b>1$ so that $ ab=n+1$ and ${ a,b \in \{1,2,...,n}$ This gives that $ n+1|lcm(1,2,...,n)$, contradiction. Similarly for $ n \ge 3$, both $ n+2,n+3$ must be of the form $ p^k$ Case 1: $ n=1,2,3$, it's easy to check $ n=1,2$ are all solutions. Case 2: $ n>3$ and $ n+1$ is even, then $ n+1=2^k$, $ 2^k<n+3<2^{k+1}$, so no solution in this case. Case 3: $ n>3$ and $ n+2=2^k$ is even, then we have $ k>2$, if $ k$ is even, then $ n+1=x^2-1=(x+1)(x-1)=p^y$, impossible. So $ k$ is odd $ \Rightarrow n+3=2^k+1=0(mod 3) \Rightarrow n+3=3^m$, by similarly reason $ m$ cannot be even. $ \Rightarrow 2^k=n+2=3^m-1=(-1)^m-1=2(mod 4)$, which give $ k=1$, so there are no solution in this case. So $ n=1,2$ are the only solutions.
15.04.2009 19:44
Unfortunately I don't know why $ 2^k < n+3 < 2^{k+1}$ implies there is no solution...
15.04.2009 19:57
What about $ n=6$. This problem was proposed on Bulgarian Sprint Mathematical Competition years ago.
15.04.2009 21:08
stephencheng wrote: If $ n + 1 \neq p^k$ for prime $ p$, then We can find two coprime factors of $ n + 1$ , say $ a,b > 1$ so that $ ab = n + 1$ and ${ a,b \in \{1,2,...,n}$ This gives that $ n + 1|lcm(1,2,...,n)$, contradiction. Similarly for $ n \ge 3$, both $ n + 2,n + 3$ must be of the form $ p^k$ Case 1: $ n = 1,2,3$, it's easy to check $ n = 1,2$ are all solutions. Case 2: $ n > 3$ and $ n + 1$ is even, then $ n + 1 = 2^k$, $ 2^k < n + 3 < 2^{k + 1}$, so no solution in this case. Case 3: $ n > 3$ and $ n + 2 = 2^k$ is even, then we have $ k > 2$, if $ k$ is even, then $ n + 1 = x^2 - 1 = (x + 1)(x - 1) = p^y$, impossible. So $ k$ is odd $ \Rightarrow n + 3 = 2^k + 1 = 0(mod 3) \Rightarrow n + 3 = 3^m$, From $ k>2$, $ n+2=2^k$ and $ n+3=3^m$ then $ 3^m-2^k=1$ with only solution for $ m=2$, $ k=3$, and thus $ n=6$ and $ m=30$ micf wrote: Unfortunately I don't know why $ 2^k < n + 3 < 2^{k + 1}$ implies there is no solution... Notice that $ n+3$ is even but not a power of $ 2$ then it is not of the form $ p^k$
15.04.2009 22:08
OMG, how couldn't i see it...
14.05.2009 08:12
it's easy to see that n+1=p^a,n+2=q^b,n+3=r^c where p,q,r are prime. since one of them divisible by 2 and another one divisible by 3. let one of them equal 2^x and another one equal 3^y. we need solve eq. 1)2^x+2=3^y 2)2^x+1=3^y 3)2^x-1=3^y 4)2^x-2=3^y 1) 2^x must be odd=>x=0 now we see n+3=3^y and n+1=1=>n=0 contr.no sol. 2)if y=2k 2^x=(3^k-1)(3^k+1) it means 3^k-1=2^a,3^k+1=2^b<=>2^a+2=2^b =>a=1,b=2,x=3 sol. y=2=>n+2=9 or n+3=9 <=>n=6,7 if y=2k+1 .2^x=(3-1)(3^2k+...+1) it's to see that 3^2k+...+1 is odd=>3^2k+...+1=1 =>x=1=y=>n+2=3 or n+3=3 <=>n=-1,0 contr. 3)3^y equal n+2 or n+3 =>y>1=>x must be even.let x=2k 3^y=(2^k-1)(2^k+1) it means 2^k-1=3^a,2^k+1=3^b<=>3^a+2=3^b<=>a=0,b=1,x=2=>n+2=4 or n+3=4<=>n=1,2 4) 2^x must be odd=>x=0 =>3^y=-1 contr. n=1,2,6,7 for n=1 m=1 for n=2 m=2 for n=6 m=30 for n=7 70|m but n+3=10 =>n+3|m contr.=>n=1,2,6
09.12.2009 15:33
I think, only solution is n=1,2 n=6 , m=30 is not possible, because 30 is not divisible by 4.
09.12.2009 21:33
Well, what about n=6, m=60? 60 is divisible by 4, but not by 8. So n=6 IS a solution.