Thread: Show a^n = 1 (mod 2^n+2) if a odd.

I know I have to use induction. The n=1 is simple:
a^2 = (2j+1)^2 = 4j^2 + 4j + 1 = 1 mod 8 = 1 mod 2^3

Then we assume for a^n that the claim is true.

However I'm not sure on the inductive step.

This is a HW assignment and help would be much appreciated. Thanks!

SOLVED:

Note a^n -1 = [(a^n-1) - 1][(a^n-1) + 1]
The left term is divisible by 2^n+2 by inductino and the right term is divisible by 2. Thus their product is divisible by 2^n+3.