View Single Post
Old 2007-06-27, 04:26   #4
MatWur-S530113's Avatar
Apr 2007

2·34 Posts

Originally Posted by maxal View Post
Consider two cases:

1) n is even then m=floor((n-1)/2)=\frac{n-2}{2}.
We have n=2m+2 and 0\equiv n^{n-1}\equiv (2m+2)^{2m+1}\equiv 2^(2m+1)\pmod{m}, implying that m=2^k for some k. Therefore, n=2*2^k+2=2^(k+1)+2.

2) n is odd then m=floor((n-1)/2)=\frac{n-1}{2}.
We have n=2m+1 and 0\equiv n^{n-1}\equiv (2m+1)^{2m}\equiv 1\pmod{m}, implying that m=1 and n=3=2^0+2.
Many thanks for your reply. But 2 things I don't understand:

1) if 0\equiv 2^{2m+1}\pmod{m} why does this imply that m=2^k for some k? (Probably I miss an easy thought...)

2) if n is even I still don't see why n must have the form n=2^k+2, if n^{n-1} is divisible by m^2=(\frac{n-2}{2})^2 (not only by m=\frac{n-2}{2}).


MatWur-S530113 is offline   Reply With Quote