Proof of $5|p^2 \implies 5|p$ for all $p \in \mathbb{N}$

Question

One of the proofs that we've covered in class uses the fact that $5|p^2 \implies 5|p$ where $p$ is a natural number. I've come up with a proof using the contrapositive, but was wondering if a direct proof exists.

Answer 1

(Expanding on my comment)

Hint: Consider the unique prime factor decomposition ($p_i$ are prime numbers, $n_i\in \mathbb{N}_{>0}$) of $p$

$$p=p_1^{m_1}\cdot\dots\cdot p_n^{m_n}$$

then $p^2$'s prime factor decomposition is (why?)

$$p^2=p_1^{2m_1}\cdot\dots\cdot p_n^{2m_n}$$

but if $5\mid p^2$ then there exists $p_i=5$ (why?). Conclude.

Answer 2

Euclid's Lemma states that if a prime number $q\mid ab$, then either $q\mid a$ or $q\mid b$. The only possible factorization of $p^2$ in this context sets $a=b=p$. Thus if $q=5$ divides $ab=p^2$, then either $5\mid p(=a)$ or $5\mid p(=b)$, in either case showing $5\mid p$.

Answer 3

This is a direct application of Euclid's lemma that states if $q$ is prime and $q|ab$ then either $p|a$ or $p|b$. So if $5$, which is prime, divides $p^2 = p*p$ then either $5|p$ or .... $5|p$. So $5|p$.

======

If Euclid's Lemma is not intuitive obvious (which it should be if you play with it for a half an hour) then we can use the unique prime factorization that any natural number $p$ has a unique prime factorization $p =\prod q_i^{a_i}$ where $q_i$ are the unique and distinct prime factors of $p$ then $p^2 = \prod q_i^{2a_i}$ and the prime $5$ divides the product of primes $\prod q_i^{2a_i}$ if and only if $5$ is one of the $q_i$. But that would mean $5$ divides $\prod q_i^{a_i} = p$.

(But that's actually circular as we need Euclid's Lemma to prove the Unique Prime Factorization theorem in the first place.)

The direct proof of Euclid's Lemma is (to me) surprisingly difficult. Bezout's Identity says if $a$ and $b$ are natural numbers that have no factors in common then we can find $n$ and $m$ (one positive one negative) where $na + mb =1$. Bezout's Lemma is one of those surprising (to me) cases where a more advance concept, prime $q|jk\implies q|j$ or $q|k$, is much more obvious and intuitive (to me), that a more basic concept, that it is possible for $na + mb = 1$ (which to me is not obvious at all.)

Bezout's lemma is derived from Euclid's algorithm (not to be confused with Euclid's Lemma) that if:

$b > a$ then we can find $b = k*a + r; 0\le r < a$ and as $b$ and $a$ have no factors in common then $a$ and $r$ can't have any factors in common either (because that factor would be a factor of $b$.)

So we can do it again and get $a = j*r + s$. .... and again to get $r = v*s + t$ and so on. As these numbers always get smaller this prosess must end with a $\alpha = h*\beta + 0$. But as $\alpha$ and $\beta$ have no prime factors in common it must be that $\beta = 1$ (that's the only way $\beta|\alpha$ while being relatively prime to $\alpha$.

So if you combine all those manipulations together to get back to the original values of $a,b$ you get an $na + mb = 1$.

Example: If $a = k*b +r$ and $a = j*r + s$ and $r = v*s + 1$ we can work backwards to get:

$1 = r - v*s = r - v*(a - j*r) = (a-k*b) - v*(a - j*(a-k*b)) = a - k*b - v*a + v*j*a - v*j*k*b= (1-v+vj)*a + (-k-vjk)*b$ so if $m = 1-v+vj$ and $n = -k-vjk$ then $ma + nb = 1$.

.....

Phew. So to use Bezout's Lemma to prove Euclid's Lemma that if $q$ is prime and $q|ab$ then either $q|a$ or $q|b$.

Pf: Assume $q|ab$ and $q$ is prime. If $q|a$ we are done. So let's assume $q\not\mid a$. Then we want to prove it must be that $q|b$.

If $q\not \mid a$ and $q$ is prime then $q$ and $a$ must have no common prime factors. So be Bezout's Lemma there exist $m,n$ so that

$nq + ma = 1$

So $nqb + mab = b$

But $q|ab$ so $ab = kq$ for some integer $k$.

So $nqb + m(ab) = nqb + m(kq) = q(nb + mk) = b$.

And $q|b$.

So that proves Euclid's lemma.

.....

The prime factorization theorem follows directly.

If $n = ab$ is composite you can factor $a$ and $b$ until you can't factor any further and then you will have a prime factorization. The only question is , is it unique. That is is it possible that $n = \prod q_i$ and $n = \prod r_j$ where $q_i $ and $r_i$ are prime (possibly repeated) but the $q_i$ and $r_j$ are different sets?

The answer is no. As $q_1|n = \prod r_i$ so $q_1|r_j$ for some $r_j$. But $r_j$ is prime so $q_1 = r_j$. Then do the same thing with $\frac n{q_1} = \prod_{i\ne 2} q_i= \prod_{l\ne j} r_l$.

Repeat until .... done.

======

That's a lot to learn in one sitting, but these should become universal truths in your mind as obvious as "The sky is blue".

Euclid's Lemma: If $q$ is prime and $q|ab$ then either $q|a$ or $q|b$.

Prime factorization theorem: Every natural number has a unique prime factorization where $n = q_1^{a_1}*....*q_n^{a_n}$ where $q_i$ are the unque prime factors of $n$.

Bezout's Lemma: If $\gcd(a,b) = 1$ then there exist integers $n,m$ so that $na + mb = 1$.

Euclid's Algorithm: A method of finding those $m,n$ in Bezout's Lemma by successivley dividing and taking remainders and repeating until it ends.