Modulus ProofDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/