Question

Show that 2^n is incongruent to 1 (mod n) for all n>1.

Thank you very much.

Printable View

- Jan 12th 2007, 02:37 PMJenny202^n is incongruent to 1 (mod n)
Question

Show that 2^n is incongruent to 1 (mod n) for all n>1.

Thank you very much. - Jan 13th 2007, 03:11 PMThePerfectHacker
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.