Problem 579

Let $a$ be an integer. Show that 5 divides $a^{2}$ if and only if 5 divides $a$.

We can slightly generalize Euclid's lemma:

Theorem 5 (Generalized Euclid's Lemma).

Let $p$ be a prime and $a_{1}, a_{2}, \ldots, a_{n}$ be integers. If $p$ divides $a_{1} \cdot a_{2} \cdots a_{n}$, then it divides one of $a_{1}, a_{2}, \ldots, a_{n}$.

Proof. We will prove this generalization by applying Euclid's lemma multiple times. If a prime $p$ divides $a_{1} \cdot a_{2} \cdots a_{n}$, then by Euclid's lemma, $p$ divides either $a_{1}$ or $a_{2} \cdot a_{3} \cdot \ldots a_{n}$. In the first case, we are done. In the second case, we apply Euclid's lemma again in the same manner. We then have that $p$ divides either $a_{2}$ or $a_{3} \cdot a_{4} \cdots a_{n}$. In the first case, we are done; in the second case, we repeat the same reasoning. If we repeat this reasoning enough times, we will eventually be done.

This reasoning can be made more rigorous using induction.