3

For $a, m, n \in \mathbb{N}$, prove that $$\gcd(a^{2^m} + 1, a^{2^n} + 1) = \begin{cases} 1, & \text{if $a$ is even}\\ 2, & \text{if $a$ is odd} \end{cases}$$ given $m \ne n$.

My attempt:

Let $\gcd(a^{2^m} + 1, a^{2^n} + 1) = d$. Let $p$ be a prime factor of $d$. Clearly, $p \nmid a \implies \gcd(p,a) = 1$. $\tag*{}$ But, $ \ \ \ a^{2^m} \equiv -1 \pmod{p} \\ \implies a^{2^{m+1}} \equiv 1 \pmod{p} \\ \implies \text{ord}_p(a) = 2^{m+1}$ $\tag*{}$ But by similar logic, $\text{ord}_p(a) = 2^{n+1}$ $\implies m = n$ $\tag*{}$ Therefore, no such prime exists. $\implies d = 1$.

But obviously, there's something wrong with this, as, for an odd $a \text{, } 2 \mid d$.

After some head-scratching, I realized that $-1 \equiv 1 \pmod{2}$. And for all odd positive integers, $\text{ord}_2(a) = 1$.

So my question is, while working with orders, do I need to treat $\text{ord}_2(x)$ as an exception? I just can't figure a general working rule for it.

Edit: Just to calrify, $\text{ord}_p(a) = 2^{m+1} \text{ because, }\text{ord}_p(a) \mid 2^{m+1} \text{ but, } \text{ord}_p(a) \nmid 2^{m}$.

Bill Dubuque
  • 265,059
  • 37
  • 279
  • 908
Nick Larry
  • 148
  • 8
  • 1
    Knowing that $a^k\equiv 1 \pmod p$ does not tell you that the order of $a\pmod p$ is $k$. $k$ could be a multiple of the order. – lulu Sep 13 '22 at 14:03
  • I didn't think it was necessary to mention as it is easy to see here that $\text{ord}_p(a) \mid 2^{m+1} \text{ but, } \text{ord}_p(a) \nmid 2^{m} \implies \text{ord}_p(a) = 2^{m+1}$, and similarly for $n$. I'll edit it in. – Nick Larry Sep 13 '22 at 14:07
  • Yes, that's good. And it does indeed show that no odd prime can divide the gcd. But, as you remark, the argument breaks down when $p=2$, so you still have to rule out the case where the gcd is divisible by $4$. – lulu Sep 13 '22 at 14:11
  • Yes, but I can't figure at what step in the solution, does it imply that either $p = 2$ or $m = n$. – Nick Larry Sep 13 '22 at 14:14
  • Maybe we can do something like: $\text{ord}_p(a) \mid 2^{m+1} \text{ and, } \text{ord}_p(a) \mid 2^{n+1} \text{ but, } \text{ord}_p(a) \nmid 2^{m} \text{ and, } \text{ord}_p(a) \nmid 2^{n} \implies \text{ either } m = n \text{ or } -1 \equiv 1 \pmod{p} \implies p = 2$. – Nick Larry Sep 13 '22 at 14:16
  • 1
    If $p$ is odd then I agree you have shown that the order is simultaneously $2^{n+1}$ and $2^{m+1}$ which forces $n=m$ as you say. However, your argument breaks down for $2$. There we only know that, say, $a^{2^{n}}+1$ is even which only tells us that $a$ is odd. – lulu Sep 13 '22 at 14:18
  • @DavidC.Ullrich It is given that $m \ne n$. – Nick Larry Sep 13 '22 at 14:28
  • To prove that $d$ does not contain more than one factor of $p = 2$, we can again argue that order of $a$ modulo $d$ would make $m = n$ if $d \ne 2$. – Nick Larry Sep 13 '22 at 15:39
  • The argument implicitly uses the **Order Test** as [here](https://math.stackexchange.com/a/1876919/242) in the first linked dupe. Of course you do need to pay attention to cases where the general argument degenerates (here when $-1\equiv 1)\ \ $. – Bill Dubuque Sep 13 '22 at 18:05

0 Answers0