Modulus Proof

Date: 04/16/2001 at 01:52:27
From: Ooi Chin Wah
Subject: Number theory

Can you please show me why m^(2^n) = 1 mod(2^(n+2)) when m is an odd 
integer? 

Thanks.

Date: 04/16/2001 at 12:22:16
From: Doctor Rob
Subject: Re: Number theory

Thanks for writing to Ask Dr. Math.

This is most easily proved by induction. It is false for n = 0, so you 
must assume that n >= 1.

Start with m^2 = 1 (mod 8). That works because

     (2*k+1)^2 = 8*(k*[k+1]/2) + 1

Now assume it is true for a certain value of n:

     m^(2^n) = 1 + r*2^(n+2)

Square both sides to increase the exponent on the left to 2^[n+1], and 
see what happens on the right after you expand. Notice that 
2*n + 4 > n + 3 for all n >= 1.

You finish.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/