# Prove that $\gcd\left(n^{a}+1, n^{b}+1\right)$ divides $n^{\gcd(a, b)}+1$

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. 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\,.$$

• Does this answer your question? Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$ – Exodd May 23 at 8:06
• The argument of the proof is identical – Exodd May 23 at 8:33
• 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. – Aravind May 23 at 8:44
• Comments are not for extended discussion; this conversation has been moved to chat. – 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$$.

Done!

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.