Proving primes divide each other Suppose $a,b,p\in\mathbb Z$ with $p$ prime.  Prove that if $p\mid a$ and $p \mid a^2 + b^2$, then $p \mid b$.
I am starting with the fact that $a=p$t with $t\in\mathbb Z$ and $p= (a^2+b^2)\cdot x$ with $x\in\mathbb Z$. I set them equal to each other in hopes that is would give me something that could give me $p\mid b$.
 A: Hint.  Here is an outline proof, see if you can provide reasons and fill in the details.  Given that $p$ is prime, $p$ divides $a$ and $p$ divides $a^2+b^2$:
(1) show that $p$ divides $a^2$;
(2) show that $p$ divides $b^2$;
(3) show that $p$ divides $b$.
A: Saying "$p$ divides $a$" (or, symbolically, $p|a$), means $a=pt$, for some integer $t$.  (Not the other way around, like you have it.)
There might be a more obvious approach, but I would first show that $p|x \iff p|x^2$.  This is a direct proof one way, and a trivial proof by contradiction the other way.
Second, I'd show that $p|(x-y) \wedge p|x \implies p|y$.
Substituting $a^2+b^2$ for $x$ and $a^2$ for $y$ in the above should yield the result you want.
A: Use the following facts (valid for any number,  not primes). I will use the symbol $n$ instead of $p$ to avoid any connotation of it being a prime. Only in the last step you need the primality condition.


*

*If $n$ divides $a$ then it divides any multiple of $a$, in particular it divides $a^2$.

*If $n$ divides sum of two quantities, and it divides one of them, then it divides the other also, i.e. if $n$ divides $A+B$ and it also divides $A$ then it divides $B$.


I am stating the above two in the general form, as these facts are used often.
Now to your problem, using $1$ and $2$, you have $p | b^2$.
Now the most important property of prime numbers is that whenever a prime divides product of two numbers, it has to divide one of them (this is often used to implicitly define primes!)
So since $p$ divides $b$ times $b$,  $p$ divides $b$.
