GCD Even/Odd ProofDate: 10/26/2001 at 04:37:33 From: paras Subject: Perfect square Hello Dr. Maths, Please help me in solving the following question: If m > n and a,m,n are positive, with m not equal to n, prove that the greatest common denominator of (a^2^m+1, a^2^n+1) = 1 if a is even, and 2 if a is odd. Thanks for the help. Date: 10/26/2001 at 14:31:12 From: Doctor Rob Subject: Re: Perfect square Thanks for writing to Ask Dr. Math, Paras. Suppose that d > 0 divides both a^(2^m) + 1 and a^(2^n) + 1. Then GCD(d,a) = 1. Then d divides their difference, d | a^(2^m) + 1 - [a^(2^n) + 1], d | a^(2^n)*[a^(2^m-2^n) - 1], because m > n, so 2^m > 2^n. Since GCD(d,a) = 1, d | a^(2^m-2^n) - 1. But since d divides a^(2^n) + 1, d | a^(2^[n+1]) - 1. That implies that d | GCD[a^(2^m-2^n) - 1, a^(2^[n+1]) - 1]. Then it is fairly easy to see that this implies d | a^GCD[2^m-2^n, 2^(n+1)] - 1. Now GCD[2^m-2^n, 2^(n+1)] = 2^n, because m > n, and so 2^(m-n) - 1 is odd. Thus d | [a^(2^n) + 1] - [a^(2^n) - 1] = 2. Thus d = 1 or 2. I think you can fill in the details and reasons, and finish from here. - 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-2013 The Math Forum
http://mathforum.org/dr.math/