# A short or elegant proof for if $p | n^2$ then $p | n$ when $p$ is prime?

Let $n, p \in \mathbb{Z}^{+}$ such that $p$ is prime. Prove $p | n^2 \Rightarrow p | n$.

What is a short or elegant proof to this? Some ideas are given at the question Prove that $\sqrt 5$ is irrational, but I would like to find a proof that does not need to rely upon the Unique Factorization Theorem or Euclid's Lemma, if possible. (In my particular math course, we haven't reached these results; they are yet to be proven and are inaccessible.)

I tried to start this proof by assuming $$\tag 1 p\mid ab\implies p\mid a \text{ or } p\mid b$$ The statement seems obviously true, however, my course requires a pedantic proof of that statement, and I am lost on finding one.

Euclid's Lemma (see snapshot at end) is given in a chapter of the textbook my class has not yet reached, so we may not assume this without proving it first. (But we may assume everything up to and including chapter 8 in this textbook(table of contents)). So I am trying to find a short proof for (1) $$p\mid ab\implies p\mid a \text{ or } p\mid b$$ that does not require Euclid's or Bezout's lemmas, if possible. If it is possible to show (1), then it seems proving $p | n^2 \Rightarrow p | n$ should be straightforward.

I was sketching out the following proof by $4$ cases.

Let $a, b, p, m, r_1, r_2 \in \mathbb{Z}$ where $p$ is prime. Prove: $$p\mid ab\implies p\mid a \text{ or } p\mid b$$ Assume $p\mid ab$. Then $ab = pm$ for some $m \in \mathbb{Z}^{+}$. (Note: Cases 1. and 2. are totally wrong, and so I may ask about this proof, $p\mid ab\implies p\mid a \text{ or } p\mid b$, in a new question.)

1. $p \not \mid a \implies \dots \implies \dots \implies p \mid b$
2. $p \not \mid b \implies \dots \implies \dots \implies p \mid a$
3. $p \mid a$ and $p \mid b$. Done.
4. $p \not \mid a$ and $p \not \mid b$. We must somehow show this leads to a contradiction. Not sure how to do this.

Euclid's Lemma

-
What's your definition of prime? Can you, at least, divide with remainder? –  fedja Oct 31 '13 at 4:04
@fedja, the definition of prime which I am allowed to assume is: prime is an integer $p \ge 2$ with only positive integer divisors $1$ and $p$. –  T. Webster Oct 31 '13 at 4:28
What do you call Euclid's Lemma which you don't want to rely on? In my book it is precisely your implication$~(1)$, which indeed seems an inevitable stepping stone to the implication of your question. –  Marc van Leeuwen Oct 31 '13 at 8:51
@MarcvanLeeuwen,apologies for the lengthy response. Please see the update. I am intermittently busy with things today, and will read over your answer as soon as I have the chance. –  T. Webster Oct 31 '13 at 18:05

What you want to prove is more generally Euclid's lemma, namely if a prime $p$ divides a product $ab$ then $p$ divides at least one of $a$ and $b$. In fact what one really wants is its generalisation to any finite number of factors (which I don't think carries a name or is even explicitly formulated very often), namely that if a prime $p$ divides a product $a_1a_2\ldots a_k$ then there is some $i$ such that $p\mid a_i$; this follows from the $ab$ case by an immediate induction.

The traditional proof of Euclid's lemma uses the fact that for any (positive) integers $m,n$ one can write $\gcd(m,n)=sm+tn$, for some $s,t\in\Bbb Z$ (called Bezout coefficients for $m,n$). Actually only the existence of $\gcd(m,n)$ for all $m,n$ is necessary, but in the strong sense of being a common divisor that is divisible by any (other) common divisor; this is indicated in the first proof given in the WP article. While such a proof is useful to explain that a counterpart of Euclid's lemma continues to be true in more general algebraic settings where Bezout coefficients no longer need to exist (but $\gcd$s do), I don't think it really provides a simpler proof for Euclid's lemma (in$\def\Z{\mathbf Z}~\Z$), because the fact that in$~\Z$ greatest common divisors in the strong sense exist ultimately depends on the existence of Bezout coefficients anyway.

For the most direct proof from scratch*, I would proceed as follows. Assume $p$ is prime and $p\mid ab$. Let $M=\{\, sp+ta\in \Z_{>0}\mid s,t\in\Z\,\}$, which is a non-empty (since $p\in M$) set of positive integers, and let $d$ be the minimal element of $M$. Any $m\in M$ is divisible by$~d$, because if it were not, then the remainder$~r$ of the division of $m$ by$~d$ would satisfy $r>0$, therefore $r\in M$ (any positive $m_1-qm_2$ is in$~M$, for $m_1,m_2\in M$ and $q\in\Z$), and so the condition $r<d$ (which holds by definition for a remainder after division by$~d$) would contradict the choice of$~d$.

In particular $d$ divides both $p$ and $a$, since $p$ and $|a|$ are elements of$~M$. The fact that $d$ is a positive divisor of$~p$ implies by the definition of prime number that either $d=1$ or $d=p$. In the latter case $p=d\mid a$ and we are done. In the former case let $s,t\in\Z$ be such that $1=d=sp+ta$, which means in particular that $ta\equiv1\pmod p$. Then $p\mid ab$ implies $p\mid tab$, and one has $b=1b\equiv tab\equiv0\pmod p$, so $p\mid b$; we are done for this case too.

Of course this proof is extracted from things that are usually presented in the form of more general statements about Euclidean division, greatest common divisors, and the Euclidean algorithm.

${}$

*I do assume basic facts about division with remainder, and at the end about modular arithmetic (but the latter could be avoided by using explicit witnesses of the modular equivalences used).

-
I found your first paragraph to be the most helpful one; namely that "if a prime $p$ divides a product $a_1a_2\ldots a_k$ then there is some $i$ such that $p\mid a_i$; this follows from the $ab$ case by an immediate induction." For the remaining paragraphs, I would have to assume the fact (which has yet to be proven in my class) that for any $m,n \in \mathbb{Z}^{+}$, one can write $\gcd(m,n) = sm + tn$ for some $s,t \in \mathbb{Z}$. Although I may only need to re-prove Euclid's Lemma, is there any way to prove what you wrote in your first paragraph, without assuming this fact? –  T. Webster Oct 31 '13 at 23:04
@mathStudent I don't quite understand your question. The proof above does not use anything about $\gcd$s, nor even mentions them (but you may _recognise_ the number $d$ as being $\gcd(p,a)$; I explicitly show that it is a common divisor of $p$ and $a$). As for the statement in the first paragraph, the proof as said is by induction, on $k$: for $k=1$ there is nothing to prove, for $k=2$ it is Euclid's lemma which I show in the remaining paragraphs; for $k>2$, since $p\mid a_1(a_2\ldots,a_k)$ one has (EL) either $p\mid a_1$ ($i=1$), or $p\mid a_2\ldots,a_k$ and then induction gives $i\geq2$. –  Marc van Leeuwen Nov 1 '13 at 7:08

The defining property of a prime number is that $$\tag 1 p\mid ab\implies p\mid a \text{ or } p\mid b$$

Thus, if $p\mid a^2$ then $p\mid a$.

ADD I am guessing you define a number $p$ to be prime if the only divisors of $p$ are $1$ and $p$ itself. Euclid's lemma then gives the "true" definition $(1)$ of a prime number. To get this result, you can use the well ordering principle, that any nonempty subset of the positive integers has a least element. Define first

DEF Let $a,b$ be integers. Then the greatest common divisor of $a,b$ is the unique positive integer $d=(a,b)$ such that $d\mid a,b$ and whenever $f\mid a,b$ then $f\mid d$.

Bezout's Lemma then proves both the existence and the uniqueness of $d=(a,b)$, as follows:

PROP Let $a,b$ be integers. Then $(a,b)$ exists, and is unique.

P Consider the set $\Bbb Za+\Bbb Zb=\{xa+yb:x,y\in\Bbb Z\}$. By considering possible cases of the sign of $a,b$, it is seen the set of positive elements of $\Bbb Za+\Bbb Zb$ is nonempty (for example, if $a>0,b<0$ then $a-b>0$ is in the set). Let $d$ be the least positive element of $\Bbb Za+\Bbb Zb$.

First, we show $d$ is a common divisor. Indeed, write $a=qd+r$ and $b=q'd+r'$ with either $r=0,r<d$ and $r'=0,r'<d$. Then $a-dq,b-q'd$ are elements of $\Bbb Za+\Bbb Zb$ (check they have the form $xa+yb$). Since $r<d$ and $r'<d$ is impossible by the definition of $d$, $r=r'=0$ so that $d$ divides both $a,b$.

Now, we show $d$ divides every element of $\Bbb Za+\Bbb Zb$. Indeed, pick an element $m$ in the set. Then $m=qd+r$ with $r<d$ or $r=0$, by the division algorithm, and again $m-qd=r$ is in $\Bbb Za+\Bbb Zb$ so we must have $r=0$. We have shown thus that $\Bbb Za+\Bbb Zb=\{dz:z\in\Bbb Z\}=\Bbb Z d$. If $f\mid a,b$ then $f\mid ax+by$ for any $x,y$. Since $d$ is of this form by construction, $f\mid d$. Thus $d$ is a greatest common divisor. But if $d'$ is another one, by definition $d\mid d'$ and $d'\mid d$ for they both greatest common divisors. Thus $d=\pm d'$; and since they are both positive, by definition, $d=d'$. $\blacktriangle$.

OBS The above (very, very important) result can be stated as

$$\Bbb Za+\Bbb Zb=\Bbb Z(a,b)$$

Now Euclid's lemma comes in easily

LEMMA Suppose that $(a,b)=1$ and $a\mid bc$. Then $a\mid c$.

P By Bezout's lemma, we can write $ax+by=1$ for some integers $x,y$. Then $cax+bcy=c$. Since $a\mid ac$ and $a\mid bc$, $a\mid cax+bcy=c$.

Then, you move onto

LEMMA Let $p$ be a prime. Then $(p,a)=1\iff p\not\mid a$.

P Suppose $p\not\mid a$. Since the only divisors of $p$ are $1,p$, then $(p,a)$ can be either $1$ or $p$. Since $p\not\mid a$, $p$ is not a common divisor of $a$ and $p$; thus $(a,p)=1$. If $p\mid a$ then $(p,a)=p\neq 1$.

THM (Defining property of prime numbers) Let $p>1$ be a positive integer. Then $p$ is prime if and only if for any $a,b$ integers, $p\mid ab\implies p\mid a$ or $p\mid b$.

P Suppose that $p$ is a prime, and assume $p\mid ab$. If $p\mid a$, there is nothing to prove. Assume thus that $p\not\mid a$. The $(p,a)=1$, so Euclid's lemma says $p\mid b$. By symmetry the claim follows by replacing $b$ with $a$. Now suppose $p$ is not prime. Then $p$ has a divisor $1<a<p$, and thus $p=ab$ with $b=p/a$. Then $p\mid ab$, but $p\not\mid a$ and $p\not\mid b$.

-
That was a very fast answer. –  Newb Oct 31 '13 at 4:02
This builds Euclid's Lemma into the definition of prime. True, it is the standard way to do it, except in beginning number theory, which uses another definition. –  André Nicolas Oct 31 '13 at 4:05
@AndréNicolas I am adding something. –  Pedro Tamaroff Oct 31 '13 at 4:16
@PedroTamaroff: I got as far as $$p\mid ab\implies p\mid a \text{ or } p\mid b$$, but did not know how to prove that statement. So this property is defined in the definition of a prime number, or must this property be proven? –  T. Webster Oct 31 '13 at 4:25
@mathStudent The proof of this statement is fairly simple: Either $p \mid a$ or $p \not \mid b$. In the first case, we are done. So assume that $p \not \mid b$. Then you should manage to use Bézout's identity to complete the proof. –  Gamma Function Oct 31 '13 at 4:31

You can hide the usage of the linear representation lemma, if you want. However, division with remainder is a must with this definition. Otherwise, you'll prove a statement that is too general to be true.

Now, let's prove that if $(a,b)=1$ and $a\mid bc$, then $a\mid c$ by induction in $a$.

$a=1$ is straightforward ($1$ divides everything). Assume that $A\ge 2$ and we know the result for $a<A$. Let $(A,b)=1$ and $A\mid bc$. Dividing with remainder, we can assume without loss of generality that $b<A$ (this is nothing but one step in the Euclidean algorithm, so, as I said, we still have it in disguise). Also, since $(A,b)=1$ and $A\ge 2$, the case $b=0$ is impossible. Write $Ak=bc$. Since $(b,A)=1$, $b\mid Ak$, $b<A$, we have $b\mid k$ by the induction assumption. Hence $k=mb$ and $Am=c$, i.e., $A\mid c$.

This uses the absence of divisors of $0$, division with remainder, and the induction axiom (which can be relaxed to the condition that no infinite sequence with strictly decreasing norms exists). Removing any of those makes the proof impossible because you can create a ring in which the statement is false then.

-

$\displaystyle{{n \over p}\,n = \mu}$ where $\mu$ is an integer. If $p \not |\ n$, then $\mu$ is not an integer.

-
This just restates the property. –  Marc van Leeuwen Oct 31 '13 at 5:21
And why do you claim $\mu$ is not an integer? –  Pedro Tamaroff Oct 31 '13 at 6:28
because the product of two integers is an integer. –  mick Nov 1 '13 at 13:33