Show that if m does not = n then

gcd((a^2)^n) + 1, ((a^2)^m + 1) = 1, if a is even

and 2, if a is odd.

Printable View

- Nov 5th 2009, 01:19 PMsirellwoodgcd odd and even proof
Show that if m does not = n then

gcd((a^2)^n) + 1, ((a^2)^m + 1) = 1, if a is even

and 2, if a is odd. - Nov 6th 2009, 06:46 AMMedia_ManFormulation?
Not sure if this question is formulated correctly. I am reading:

For all $\displaystyle m\neq n, gcd(a^{2m}+1,a^{2n}+1)=\begin{cases}1 & \text{a even} \\2 & \text{a odd} \\ \end{cases}$

This would mean that for a even, any two elements in the sequence $\displaystyle c(a)_k=a^{2k}+1$ should be relatively prime without exception: $\displaystyle c(2)=\{5,17,65,257,1025,4097,16385,...\}$. As you can see, the conjecture is simply wrong. - Nov 7th 2009, 03:57 AMMedia_ManExponents not Associative
Theorem: WLOG, for $\displaystyle

m> n, \gcd(a^{2^m}+1,a^{2^n}+1)=\begin{cases}1 & \text{a even} \\2 & \text{a odd} \\ \end{cases}

$

Proof: Start by noticing $\displaystyle a^{2^n}+1|a^{2^m}-1$ -- see proof at http://www.mathhelpforum.com/math-he...s-2-n-1-a.html. So we can rewrite as $\displaystyle \gcd(kx+2,k)$, for $\displaystyle k=a^{2^n}+1$ and some x. It can be easily seen that k has the opposite parity of a. So if a is even, k is odd, and $\displaystyle \gcd(kx+2,k)=1$. If a is odd, k is even, and $\displaystyle \gcd(kx+2,k)=2$. QED