Proof that a prime can't divide a multiplication of two reminders of it Let $p$ be a prime number.
Let $r_1$, $r_2$ be integers such that $1\leq r_1 < p$ and $1 \leq r_2 < p$.
How to prove that $p \nmid r_1r_2$?
I know one way to prove this. It can be proved by the fact that $p \nmid r_1$ and $p \nmid r_2$ (because $r_1 < p $ and $r_2 < p$) and  by Euclid's lemma that says that $p \mid ab \Rightarrow p\mid a\vee p \mid b$.
I'm asking if there is a simpler proof for this that proved this without using this lemma.
Another (related) question:
Let $p$ be a prime number and let $a$ be some integer.
I want to prove that $p \mid a^2 \Rightarrow p \mid a$.
I can prove this by proving $p \nmid a \Rightarrow p \nmid a^2$ by: $p \nmid a \Rightarrow a = pq+r $for some $q,r$ integers. Than, $a^2=(pq+r)(pq+r)=p(pq^2+2qr)+r^2$. Now, I can use the proof in my first question to prove that $p \nmid r^2$ and thus $p\nmid a^2$. I want to know if there is a simpler proof to what I prove in question 2.
 A: Below are a few proofs of Euclid's Lemma: $ $ prime $\,p\mid ab\,\Rightarrow\,p\mid a\,$ or $\,p\mid b,\, $ which, for variety, are all a bit different from the standard Bezout-based proof.
$(1)\ $ By little Fermat, $\,{\rm mod}\ p\!:\ a\not\equiv 0\,\Rightarrow\, 1\equiv a^{p-1}\!\equiv a\,a^{p-2}\Rightarrow\,a^{p-2}\!\equiv a^{-1},$ therefore if $\,ab\equiv 0\,$ then scaling by $\,a^{-1}$ yields $\,b\equiv 0,\,$ hence $\,p\mid ab,\ p\nmid a\,\Rightarrow\,p\mid b.\,$
$(2)\ $ Use Gauss's algorithm, to deduce,  $\,{\rm mod}\ p\!:\ a\not\equiv 0\,$ is invertible. Finish as in $\,(1).$
More generally it is the special case $\,c = p\,$ prime below, since $\,(p,a)=1\iff p\nmid a$
$(3)\ $ Theorem $\,\ (c,a) = 1,\ c\mid ab\ \Rightarrow\ c\mid b$
Proof $\ $ The set $\,S$ of naturals $\,n\,$ such that $\,\color{#c00}{c\mid nb}\,$ is closed under subtraction  and contains $\, a,c\,$ therefore its least positive element $\,\color{}{d\mid a,c}\,$ so $\,(a,c)=1\,\Rightarrow\,\color{}{d=1}\in S\ $ so $\ \color{#c00}{c\mid d b} = b$
A: $r_1 r_2$ has a prime factorization. By uniqueness of this factorization, it is equal of the factorization of $r_1$ times the factorization of $r_2$.  So, $p|r_1 r_2$ implies $p$ appears as one of the prime factors of $r_1r_2$, which implies $p$ is a prime factor of $r_1$ or $r_2$.  Thus $p$ divides $r_1$ or $r_2$.  This is impossible: if $p$ divides a positive integer, then that positive integer must be  $\geq p$.
A: Suppose you know that $1\le r_1<p$ and $1\le r_2<p$ implies $p\nmid r_1r_2$. Now, suppose $p\mid ab$. Write $a=q_1p+r_1$ and $b=q_2p+r_2$, with $0\le r_1<p$ and $0\le r_2<p$. Then
$$
ab=q_1q_2p^2+(q_1r_2+q_2r_1)p+r_1r_2
$$
and so
$$
p\mid r_1r_2
$$
By hypothesis, we must either have $r_1=0$ or $r_2=0$.
This shows that what you want to prove is actually equivalent to Euclid's lemma.
