Let $a$ and $b$ be positive integers. Prove that $\operatorname{gcd}\left(n^{a}+1, n^{b}+1\right)$ divides $n^{\operatorname{gcd}(a, b)}+1$.

My work -

I proved this for $n=2$ but I am not able to prove this for all $n$ (if anyone wants I can give my proof for $n=2$).

More Observation.

If $a$ and $b$ are both odd, then $d=\gcd(a,b)$ is an odd positive integer. Therefore, $$n^a+1=(n^d+1)\left(n^{d(a-1)}-n^{d(a-2)}+\ldots-n^d+1\right)$$ and $$n^b+1=(n^d+1)\left(n^{d(b-1)}-n^{d(b-2)}+\ldots-n^d+1\right),$$ whence $n^d+1$ divides both $n^a+1$ and $n^b+1$. That is, $n^d+1$ divides $\gcd(n^a+1,n^b+1)$. However, we can perform Euclidean algorithm as follows.

Without loss of generality, let $a\geq b$.

Case I: $a\geq 2b$. We have $$n^a+1=(n^{b}+1)\left(n^{a-b}-n^{a-2b}\right)+(n^{a-2b}+1)\,.$$ We can replace $(a,b)$ by $(a-2b,b)$, and perform more reduction steps.

Case II: $b<a<2b$. We have $$n^{a}+1=(n^b+1)n^{a-b}-\left(n^{a-b}-1\right)$$ and $$n^b+1=\left(n^{a-b}-1\right)n^{2b-a}+(n^{2b-a}+1)\,.$$ Thus, we can replace $(a,b)$ by $(b,2b-a)$ and perform more reduction steps.

Case III: $a=b$. Then, the reduction steps end.

Note that, at each step, the difference between $a$ and $b$ never increases. (Observe that, we cannot perform the steps in Case II infinitely many times, as the smaller value between $a$ and $b$ always decreases.) Therefore, the process has to stop when both numbers become the same odd integer $s$, which is an integer combination of $a$ and $b$. However, $d$ divides any integer combination of (the starting values of) $a$ and $b$. Thus, $d$ divides $s$. The Euclidean algorithm above shows that $n^s+1$ is the greatest common divisor of $n^a+1$ and $n^b+1$. Thus, $s=d$, so in the case $a$ and $b$ are odd, $$\gcd(n^a+1,n^b+1)=n^{\gcd(a,b)}+1\,.$$

  • 6
    $\begingroup$ Does this answer your question? Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$ $\endgroup$ – Exodd May 23 at 8:06
  • 5
    $\begingroup$ The argument of the proof is identical $\endgroup$ – Exodd May 23 at 8:33
  • 4
    $\begingroup$ And it can also likely be directly applied; eg: the gcd must divide $n^{2a}-1$ and $n^{2b}-1$, so it divides $n^{2gcd(a,b)}-1$. Factorize this and note that the gcd with the first factor is 1 or 2. $\endgroup$ – Aravind May 23 at 8:44
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – quid Jul 19 at 16:33

Let $\mathrm{WLOG}$ $a>b$. For any prime $p$ let $v_p(m)$ denotes the maximum exponent of $p$ in the canonical prime factorisation of $m$. We need to show that $$v_p(\mathrm{gcd}(n^a+1,n^b+1))\leq v_p(n^{\mathrm{gcd}(a,b)}+1)$$ For all primes $p$. If $v_p(n^{\mathrm{gcd}(a,b)}+1)=0$, then it's your exercise why $p$ doesn't divide $\mathrm{gcd}(n^a+1,n^b+1)$. Now let $$v_p(\mathrm{gcd}(n^a+1,n^b+1))=\alpha\,.$$ Then $p^{\alpha}\mid (n^a+1)$ and $p^{\alpha}\mid(n^b+1)$. Therefore, $$p^{\alpha}\mid n^a-n^b= n^b(n^{a-b}-1)\,.$$ Since $p>1$, $\mathrm{gcd}(n,p)=1$. Then, $p^{\alpha}\mid (n^{a-b}-1)$. Similarly we get, $$p^{\alpha}\mid (n^{a-b}-1)+(n^b+1)=n^b(n^{a-2b}+1)\,.$$

Then as before, $p^{\alpha}\mid(n^{a-2b}+1)$.

In this way you can reach $\mathrm{gcd}(a,b)$ in the exponent like we get gcd of two integers by Euclidean algorithm.

Hence finally you will conclude that $p^{\alpha}\mid (n^{\mathrm{gcd}(a,b)}+1)$. Hence $v_p(n^{\mathrm{gcd}(a,b)}+1)\geq \alpha$.


| cite | improve this answer | |

Suppose that for some prime $p$ and positive integer $k$ we have $p^k$ divides both $n^a+1$ and $n^b+1$. Then, we need to prove that $p^k$ divides $n^{\gcd(a,b)}+1$. Denote $d=\gcd(a,b)$. Here, we will consider two cases:

Case 1. $p=2$. In this case, if $a$ or $b$ is even, then $k=1$ (because $m^2+1$ can't be divisible by 4) and $n$ should be odd. So, $n^d-1$ is divisible by $p^k=2$, as desired.

If both $a$ and $b$ is odd, then $\gcd(n^a+1, n^b+1)=n^d+1$ (it's similar to Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$) and in particular, $2^k\mid n^d+1$.

Case 2. $p>2$. In this case, note that $p^k$ divides $$n^{2a}-1=(n^a-1)(n^a+1)$$ and $$n^{2b}-1=(n^b-1)(n^b+1)\,,$$ so $p^k$ divides $n^{2d}-1=(n^d-1)(n^d+1)$. Note that $p$ can't divide both $n^d-1$ and $n^d+1$ (because $p>2$). Hence, it's sufficient to prove that $n^d-1$ can't be divisible by $p^k$. Indeed, if $n^d\equiv 1\pmod {p^k}$, then $$n^a\equiv n^b\equiv 1\pmod {p^k}\,.$$ However, by our assumption we have $n^a\equiv n^b\equiv -1\pmod {p^k}$, so due to $p^k>2$ we get a contradiction. Thus, $p^k$ divides $n^d+1$ as desired.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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