Given $x^2+y^2=n$ and $2^k\| n$, prove that $2^{k/2}\| \gcd(x,y)$ if $k$ is even, and $2^{(k-1)/2}\| \gcd(x,y)$ if $k$ is odd.

Question

Question: Given three integers $x,y,n$ such that $x^2+y^2=n$ and $2^k\| n$, prove that $2^{k/2}\| \gcd(x,y)$ if $k$ is even, and $2^{(k-1)/2}\| \gcd(x,y)$ if $k$ is odd.

Could anybody please give me a hint?

Note: $a^b\| n$ means that $a^b\mid n$ but $a^{b+1}\not\mid n$

Answer 1

If $2^d\|\gcd(x,y)$, write $x=2^da$, $y=2^db$, where at least one of $a,b$ is odd. Then $$ x^2+y^2=2^{2d}(a^2+b^2)$$ and $a^2+b^2$ is either odd (if $a\not\equiv b\pmod 2$), or is $\equiv 2\pmod 8$ (if both $a$ and $b$ are odd). Hence either $2^{2d}\|n$ or $2^{2d+1}\|n$.