Prove that $\sqrt{3}$ is not a rational number There is a similar question however that question asks why $3 |p^2$. Here the question is about $ 3 | p^2 \rightarrow 3 | p$. 
It is a simple exercise (1.2.1) from Abbot's "Understanding Analysis". 
$\nexists p,q \in \mathbb{N} : \left(\dfrac{p}{q}\right)^2 = 3$ 
$p$ and $q$ have no common factors, otherwise they would cancel each other out.
Contradiction:
$p^2 = 3q^2$ 
The troublesome part for me is 

From this, we can see that $p^2$ is a multiple of 3 and hence $p$ must
  also be a multiple of 3.

Why is that?
The proof goes on with 
$p = 3 r$
$q^2 = 3r^2 \rightarrow q = 3 \lambda$. 
It concluses now that $q$ and $p$ have common factors, which invalidates the original statement. 
How can I prove $p^2 = 3q^2 \rightarrow p = 3 r$? If this is not true, then I don't see how the contradiction proves the statement, since it only invalidates it for such $p,q$ that have common factors. 
What if $p^2 = 3q^2$ and $p \ne 3 r$? 
 A: If $p^2=3m$ for some $m\in \mathbb Z$, then $p=3k$ for some $k\in \mathbb Z$. Suppose otherwise. By Division Algorithm, $p=3k+1$ or $p=3k+2$. Squaring $p$, we get either $9k^2+6k+1$ or $9k^2+12k+4$ which are both not multiples of $3$, contradicting the assumption. Thus, $p$ has to be a multiple of $3$.
A: The usual articulation of the result you ask about is Euclid's lemma. Changing your notation slightly, Euclid's lemma says that if $p$ is prime, $a$ and $b$ are integers, and $p$ divides $ab$, then $p$ divides $a$ or $p$ divides $b$. Particularly, if $p$ divides $a^{2}$, then $p$ divides $a$.
Of course, if $p = 3$ it's also fine to do case by case analysis based on the division algorithm for integers.
A: Alright, let me explain troublesome part.
Notice, we have $$p^2=3q^2\tag 1$$ shows that the $p^2$ is divisible by $3$ which shows that $p$ is also divisible by $3$  (by fundamental theorem)
Hence, we have $$p=3m\tag 2$$ where, $m$ is some integer 
Now, substituting $p=3m$ in (1), we get $$(3m)^2=3q^2$$$$\iff 3m^2=q^2$$ 
now, from above equation,  we conclude that $q^2$  is divisible by $3$ which shows that $q$ is also divisible by $3$ (by fundamental theorem) 
then we have $$q=3n\tag 3$$ 
Now, from (2) & (3), we find that $p$ & $q$ have a common factor $3$ which is a contradiction.
