For any natural number $n$, exists $z,x,y\in\mathbb{N}$ such that: $z^n=x^2+y^2$ 
Prove that for any natural number $n$, one can find $z,x,y\in\mathbb{N}$ such that: $z^n=x^2+y^2.$

Here $\mathbb{N}$ denotes all the natural numbers $n\geq1$.
This problem feels like so much general that i don't even know how to start. I don't think that any of the things that i tought is worthy of posting here.
So i'm asking for hints. Can someone give some good ideas on how to start?
 A: For $n$ even take $3\times 5^{\frac{n-2}{2}},4\times 5^{\frac{n-2}{2}},(5\times 5^{n-1})^\frac{1}{n}=5$
For $n$ odd find $k$ such that $n|2k+1$. Then take $2^k,2^k,2^{\frac{2k+1}{n}}$.
A: Begin with $$5=2^2+1^2$$
If $m=a^2+b^2$ with positive integers $a,b$, then $5m=5a^2+5b^2=(2b+a)^2+(2a-b)^2$
WLOG , we have $a\ge b$, so $2a-b$ is positive, so we have a representation again. 
So, with induction, we can easily show that for every $5^n$, there is a solution.
A: Idea: use complex numbers.
Write
$$(a+i b)^ n = x + iy$$
Then we get for the norms
$$(a^2 + b^2)^n = x^2 + y^2$$
Example: for $n=3$ 
$$(a+ib)^3 = a^3 - 3 a b^2 + i ( 3 a^2b -b^3)= x+ i y$$ gives the identity
$$(a^2 + b^2)^3 = (a^3 - 3 a b^2)^2 + (3 a^2 b - b^3)^2$$
You can do this for every $n$. 
A: S is the set of numbers in form $x^2+y^2$ where $x,y\in\mathbb N$. Then
1) If $a,b\in S$ then $ab\in S$. Indeed, $a=x^2+y^2$ and $b=z^2+t^2$ then $ab=(xz+yt)^2+(xt-yz)^2$. 
2) $2=1^2+1^2$, $5=1^2+2^2$, ... then $2^n,5^n, ...\in S$.
These answers your question.
