The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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 


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   
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.