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
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.

(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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search