0
$\begingroup$

Taken from An Introduction to the Theory of Numbers by Niven et al:

Prove that if $m\gt n$ then $a^{2^n}+1$ is a divisor of $a^{2^m}-1$. Show that if $a,m,n$ are positive with $m\ne n$, then:

$gcd(a^{2^m}+1,a^{2^n}+1)=1$ (if $a$ is even) or $2$ (if $a$ is odd)

I just got that since $a^{2^m}-1$ is divisible by $a^{2^n}+1$ it is equal to $x(a^{2^m}+1)$ for some integer $x$. But that's all I got.

P.S.: Sorry, but I'm extremely poor in Number Theory and related problem-solving. If you could suggest some methods to get better, I'd be highly obliged. And a final request, please make the answer simple such that I understand it. Thanks a lot!

$\endgroup$

marked as duplicate by Bill Dubuque divisibility Jul 26 at 16:37

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

Since a$^{2^m}$ is even, $a^{2^m}$- 1 is the difference of squares. So we have $$ a^{2^m} - 1=(a^{2^{m-1}}-1)(a^{2^{m-1}}+1)$$.

Notice the first term is again a difference of squares. Continue in a similar process and you will find that $a^{2^n}+1$ is a factor.

Whenever you see a expression that can be factored, you should generally do that to find factors.

$\endgroup$
  • $\begingroup$ Thanks sir! Any tips for improving at number theory(contest maths)? $\endgroup$ – Sen47 Jul 26 at 16:22
  • $\begingroup$ This wasn’t really a question in number theory. $\endgroup$ – Lubin Jul 26 at 16:47

Not the answer you're looking for? Browse other questions tagged or ask your own question.