View Single Post
2007-06-27, 04:26   #4
MatWur-S530113

Apr 2007
Spessart/Germany

2·34 Posts

Quote:
 Originally Posted by maxal 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}$).

greetings,

Matthias