Question
Show that 2^n is incongruent to 1 (mod n) for all n>1.
Thank you very much.
First you can prime decompose for it is larger than 1.
Then by relative primeness the congruences simplifies.
In that case, the problem simplifies to showing,
Where, .
Now, if is even there is nothing to prove because if it were the case that,
we have,
while , a contradiction.
Thus, for an odd prime and .
There are 2 cases either 2 is a primitive root or it is not.
1)2 is a primitive root. Then divides . But that cannot be because is even for and is odd. A contradiction.
2)If 2 is not a primitive root then by Gauss' theorem since it has a primitive root. Call it . Thus, for .
Let the order of 2 be . Thus,
.
Since is a primitive root, . If is even then there is nothing to prove because that would imply that the order divides which is a contradiction for it is odd. Now if is odd by Euclid's lemma we have . Thus, is even that means implies is a quadradic residue of and therefor a quadradic residue of , in that case must be even because primitive roots are quadradic residues if and only if for even indexes. Thus, the order of 2 is even contrary to our assumption that the order was odd. Hence in all cases can never be congruence to 1.