8
$\begingroup$

Prove that two distinct number of the form $a^{2^{n}} + 1$ and $a^{2^{m}} + 1$ are relatively prime if a is even and have $gcd=2$ if a is odd

My attempt:
If $a$ is even, let $a = 2^{s}k$ for some integers $k, s$
Then, $$a^{2^{n}} + 1 = 2^{2^{n}s}\times k^{2^n} + 1$$ and $$a^{2^{m}} + 1 = 2^{2^{m}s}\times k^{2^m} + 1$$ To prove that they're relatively prime, we need to show that their gcd = 1. And I was stuck here, how could I prove that gcd of two numbers is $1$?

A hint would be sufficient. Thanks.

  • 0
    You don't need to sign your posts; your name/signature is automatically added to the post.2011-02-28
  • 0
    @Arturo Magidin: Thanks, I will next time.2011-02-28
  • 0
    Another minor point: $\gcd(m, n)$ by typing `$\gcd(m, n)$`2015-04-22

3 Answers 3

8

Hint:

Consider the following proof when $a=2$: http://planetmath.org/encyclopedia/FermatNumbersAreCoprime.html

Try adapting it to work for all $a$.

Hint 2: Factor $a^{2^n}-1$.

  • 0
    @Eric Naslund: Thank you.2011-02-28
  • 0
    I don't get it. Why voted down?2011-02-28
  • 1
    +1: No idea why one would downvote this.2011-02-28
  • 0
    @Moron: Funny, someone didn't like either answer!2011-02-28
  • 0
    @Eric: Downvote on my answer is explainable. Earlier I had a mistake, but I edited it, apparently quickly enough that it does not show in the history. Downvote on your answer does not seem explainable though...2011-02-28
  • 0
    @Eric Naslund: I tried to adapt the proof you mentioned, but I could not prove that the gcd must be 2, since $a$ has another variables :(. Could you help?2011-02-28
  • 1
    @Chan: Ok, so we need to do a little more, you are correct. It suffices to consider $$a^{2^n}+1$$ modulo $4$. Since $$a^{2^n}$$ is a square, it is congruent to 0 or 1, and hence is congruent to 1 when $a$ is odd. Then we see $$a^{2^n}+1\equiv 1\pmod{4}$$ so that each term is divisible by 2 but not 4. That is where the $2$ in the $\gcd$ comes from. Use the previous method to show that other primes cannot divide it.2011-03-01
  • 0
    @Eric Naslund: Many thanks. I will bother you again if I'm lost again :P.2011-03-01
  • 0
    @EricNaslund,@Chan: What about the case of a is even?2013-06-29
7

If $x = -1 \mod p$, then $x^{2^n} = 1 \mod p$.

Assume $n \gt m$. So if $p$ divides $x + 1 = a^{2^m} + 1$, then, $a^{2^n} + 1 = x^{2^{n-m}} + 1 = 1 + 1 = 2 \mod p$.

  • 1
    I don't see what this tells us. What am I missing?2011-02-28
  • 0
    @Eric: I have edited the answer.2011-02-28
  • 0
    @Moron: Thanks, that makes it clear. +1 for the edit.2011-02-28
  • 0
    @Moron: What's $p$ in your hint? I tried understand your hint, but I felt lost :(. Thanks.2011-02-28
  • 0
    @Chan: $p$ is any prime which divides $x+1$. Basically we are showing that if $p$ divides $a^{2^m} + 1$, then $p$ cannot possibly also divide $a^{2^n} + 1$, unless $p=2$.2011-03-01
  • 1
    @Moron: Thanks again. But I lost, I knew that $p$ is prime, but I can't find a way to link it to my problem. Furthermore, how does it relates to the parity of $a$?2011-03-01
  • 0
    @Chan: If two number are not relatively prime, there is some prime $p$ which divides both. We showed that that is not possible for $p \gt 2$. If a is odd, then all numbers are divisible by 2.2011-03-01
  • 0
    @Moron: Thank you. I will think more about it.2011-03-01
1

Hint $\ \ \ (A\!+\!1, A^{2K}\!\!+1)\,=\, (A\!+\!1,\ (-1)^{2K}\!+1)\, =\, (A\!+\!1,2).\ $ Put $\ A = a^{\large 2^{\Large N}}\!$ (wlog $\ N < M)$

using $\,\ \ (A\!-\!n,\ \ F(A)\ )\, = \, (A\!-\!n,\ \ F(n) )\ $ for all polynomials $\ F(X)\in \mathbb Z[X],\ A,n\in \mathbb Z$

by $\!\bmod A\!-\!n\!:\ A\equiv n\,\Rightarrow\, F(A)\equiv F(n)\ $ by the Polynomial Congruence Rule, and

also by $\ (B,\ C)\ =\ (B,\ C \bmod B),\, $ modular property of GCD (used in Euclidean algorithm)

Remark $ $ For the general case $\ (a^m+1,a^n+1)\ $ see this answer.

  • 1
    Someone is downvoting all the answers on this thread. +1. This is a more generally applicable answer.2011-02-28
  • 3
    At this point, I think you under evaluate a very important part of mathematics. That is the ability to communicate it to other people. Every answer you down voted was one where I was much clearer to someone wanting to understand the basics. Each answer you write isn't even written in English nicely, is unclear, and not at the level the OP wanted. Having said that, do I think they are _bad_ answers that deserve to be down voted? No, that I reserve for actual things that do not contribute at all mathematically.2011-02-28
  • 4
    At the very least, if you do not like my answers, and think they need to be pushed in a certain direction, please comment and tell me. Whenever you down vote a message box comes up asking you to do so. It is impossible for me understand your reasoning when you do not tell me. I do not see at all what was wrong with most of these answers, and I honestly have no problem with downvotes that are explained, because then whatever problem there is can be improved. As is it resembles that you just do not like the fact that mine are accepted over yours, which is childish.2011-02-28