Problem
NT-B2-M01-P017 Even Powers and a Sum
#17
★★★★★ Level 5 of 5
Let \( \gcd(x,y)=1 \). Find \( \gcd(x+y,x^{2k}+y^{2k}) \), where \(k\) is a positive integer.
Modulo \(x+y\), replace \(x\) by \(-y\). Then handle parity separately.
Let \(d\) be the gcd. Modulo \(x+y\), \(x\equiv-y\), hence \(x^{2k}+y^{2k}\equiv2y^{2k}\pmod d\). Since \( \gcd(y,x+y)=1 \), the common divisor \(d\) divides \(2\). Therefore only \(1\) and \(2\) are possible. If \(x,y\) are both odd, then \(x+y\) and \(x^{2k}+y^{2k}\) are even, so the gcd is \(2\). If one is even and the other is odd, then \(x+y\) is odd, so the gcd is \(1\).
The difficulty is proving not only divisibility by \(2\), but also the absence of larger powers of two.