View Single Post
Old 2007-06-26, 10:58   #3
maxal
 
maxal's Avatar
 
Feb 2005

3748 Posts
Default

Quote:
Originally Posted by MatWur-S530113 View Post
if and only if n^{n-1} is divisible by (floor((n-1)/2))^2 then there is a non-negative Integer k with n=2^k+2
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.
maxal is offline   Reply With Quote