0
$\begingroup$

If $m > n$ and $a,m,n$ are positive, with $m$ not equal to $n$, find the greatest common divisor of $2^{2^m}+1, 2^{2^n}+1$. Please solve this problem using Euclid's algorithm.

I tried to use Euclid's algorithm by first dividing $2^{2^m}+1$ by $2^{2^n}+1$, but I got stuck in the 2nd step while dividing $2^{2^n}+1$ by the difference of $2^{2^m}+1$ and $2^{2^n}+1$.

$\endgroup$

marked as duplicate by Greg Martin, Cesareo, Adrian Keister, José Carlos Santos, Bill Dubuque elementary-number-theory May 15 at 18:10

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.

  • 2
    $\begingroup$ math.stackexchange.com/questions/123524/… $\endgroup$ – lab bhattacharjee May 15 at 5:36
  • 1
    $\begingroup$ There is no such thing as a "greatest common denominator". Two fractions will have a least common denominator. Two integers will have a greatest common divisor. Anyway, do you know what Euclid's Algorithm is? Do you know how to apply it? Where do you get stuck when you try to apply it to this question? We can't help you, if we don't know what you can do, and what you can't do. $\endgroup$ – Gerry Myerson May 15 at 6:13
  • $\begingroup$ As written, the answer is $(a^2)^{n+1}$, obviously. PLease check the statement $\endgroup$ – Hagen von Eitzen May 15 at 6:13
  • $\begingroup$ @Hagen, look at the edit history. A comedy of errors. $\endgroup$ – Gerry Myerson May 16 at 3:19
  • 1
    $\begingroup$ @Garry Thanks for asking. I am now clear on this topic. I am now trying to further improve my understanding on Euclid's algorithm by solving more problems like this. $\endgroup$ – Rohan Kalluraya May 18 at 11:43
0
$\begingroup$

The first step in Euclid's algorithm:

If we let $a_k = 2^{2^k}+1$, and

$$g(m,n)=\sum _{j=1}^{2^{m-n}} (-1)^{j+1}2^{2^m-j 2^n}$$

then

$$a_m=a_ng(m,n)+2$$

The second step would be

$$a_n=2\left(\frac{a_n-1}{2}\right)+1$$

which shows that $a_m,a_n$ are coprime for $m>n>0$

$\endgroup$

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