diophantine equation: $x^2 +y^2 = z^n$ [duplicate]

Prove that $x^2+y^2=z^n$ has a solution $(x, y, z)$ in $\mathbb{N}$ for all $n\in\mathbb{N}$

I tried to prove this by induction, but couldn't. ( This was probably because the solution for some $n$ isn't necessarily related to the solution for $n+1$)

I can't seem to see any other way other than induction for proving the statement. Any help/hints on solving this problem, or any alternative approach will be highly appreciated :)

marked as duplicate by Sil, Feng Shao, Arnaud D., nmasanta, Don ThousandOct 3 at 19:45

• Are you allowing $0 \in \mathbb{N}$? If so, there is a theorem that a natural number is the sum of two squares iff primes 3 mod 4 appear only to even powers in its prime factorisation. The result follows immediately from that: you can even get an answer with $z=2$. – Patrick Stevens Nov 29 '15 at 17:42
• artofproblemsolving.com/community/c3046h1049554__ – individ Nov 29 '15 at 17:45
• No, $0\notin\mathbb{N}$ but I do want to know about the theorem you said. Could you provide me the proof? – Aditya De Saha Nov 29 '15 at 17:47

Its easy to find a solution for $n=2$, $3^2+4^2=5^2$. Its also easy to find a solution for $n=3$, $2^2+2^2=2^3$.

Now notice that if $x^2+y^2=z^n$ then $$(x\cdot z)^2+(y\cdot z)^2=x^2\cdot z^2+y^2\cdot z^2=z^2(x^2+y^2)=z^{n+2}$$

Hence by induction it is possible for all $n$.

Edit: Just noticed I skipped the $n=1$ case. $1^2+1^2=2$. Done.

There is a neat trick to this problem that uses complex numbers. Note that $|a+bi|^2=a^2+b^2$. So if $m=a^2+b^2=|a+bi|^2$ and $n=c^2+d^2=|c+di|^2$, then $mn=|(a+bi)(c+di)|^2=|(ac-bd)+i(ad+bc)|^2$. This tells us that the numbers that are sums of two squares are closed under multiplication.

Now, let us start with any pair of numbers, $a,b$. Then $a^2+b^2=n$, or $|a+bi|^2=n$. Taking powers, we have $|(a+bi)^k|^2=n^k$.

• You don't need complex numbers to prove the identity $\left(a^2+b^2\right)\left(c^2+d^2\right)=(ac+bd)^2+(ad-bc)^2$, which proves that the numbers that are sums of two squares are closed under multiplication. – user236182 Nov 29 '15 at 17:54
• You don't need them to prove the identity, but it seems rather arbitrary without invoking complex numbers. I'm not a big fan of formulas that you just have to expand and verify but leave you with no intuition. – Aaron Nov 29 '15 at 17:56
• I would say this is the best answer as it can generate solutions with $x$ and $y$ coprime, which the other two solution cannot. And I think this is the most important thing in this type of problem even though the original problem did not require $x$ and $y$ to be coprime. – cr001 Nov 29 '15 at 18:10
• I wanted to send an answer like this. However that formula (already known by Diophantus before the appearance of the imaginary unit) I realized that if $z=a^2+b^2$ then its power have the "sum of squares" $z^2+0^2$ which is allowable as a sum of squares but not useful to find x and y for the posted equation. – Piquito Nov 29 '15 at 18:46

(No induction necessary) Start with a known pythagorean triplet $(x,y,z),$ for example $(3,4,5).$ If you multiply all three terms in the equation $x^2+y^2=z^2$ by $z^{2n-2},$ the left hand side will still be a sum of squares and the right hand side will be the $n$-th power of the square of the original $z.$

One explicit solution would be $(3.5^{n-1},4.5^{n-1},25)$