I was messing around the expression $\gcd(a^n+b^n, |a - b|)$, and I found that when you fix $a$ and $b$ and increase $n,$ the expression would always be constant. (Shown below)
For example, Let $a = 4$ and $b = 100$.
When $n = 1,$ $\gcd(104, 96) = 4$
but when $n = 2, 3, \ldots,$ $\gcd(4^n+100^n, 96)$ is always $8$
Another example, let $a = 518$ and $b = 712$.
When $n = 1, 2, 3, 4, 5, \ldots$
$\gcd(\cdots)= 28, 56, 112, 224, 224, \ldots$
Can someone help with why this is true? (Or provide any counter example? Can't seem to find any with $a, b < 10^3$)
Thank you.
This question was taken from a programming competition that ran in 2018 https://www.codechef.com/AUG18B/problems/GCDMOD
Without loss of generality, set $b>a$.
Then $\gcd(a^n+b^n,|a-b|)=\gcd(a^n+b^n,b-a)$.
But we know that $b^n-a^n=(b-a)(b^{n-1}+ab^{n-2}+\dots+a^{n-2}b+a^{n-1})$, so $b-a|b^n-a^n$, and $\gcd(b^n-a^n,b-a)=b-a$.
Thus $a^n+b^n=2a^n+k(b-a)$ for some integer $k$, so by Euclid's algorithm, $\gcd(a^n+b^n,b-a)=\gcd(2a^n,b-a)$, which eventually becomes constant as a result of the following:
Let $v_p(n)$ be the $p$-adic evaluation of $n$ (for $p$ prime), namely $k$ such that $p^k$ is a factor of $n$, but $p^{k+1}$ is not. Then consideration of prime factorisation tells us that for all $a,b,p$, $v_p(\gcd(a,b))$ is the minimum of $v_p(a),v_p(b)$.
Eventually, for big enough $n$, $v_p(2a^n)$ is either big (as $n$ is big) or fixed at $0$ (or $1$ if $p=2$). In the former case, $v_p(\gcd(2a^n,b-a))=v_p(b-a)$, so is constant; and in the latter case, $v_p(2a^n),v_p(b-a)$ are both constant, so $v_p(\gcd(2a^n,b-a))$ is constant.
Thus eventually $v_p(\gcd(2a^n,b-a))$ is constant for all $p$; so $\gcd(2a^n,b-a)$ is constant.