# Can Euclid's Division Algorithm and/or Fundamental Theorem of Arithmetic implies this property of prime numbers

There is an exercise on page 44 of Amann's book Analysis, Vol I which stuck me so much. I quoted it here:

Ex7: Let $p\in\mathbb{N}$ with $p>1.$ Prove that $p$ is a prime number if and only if, for all $m,n\in\mathbb{N},$ $$p\mid mn\implies p\mid m \quad \text{or} \quad p\mid n.$$

Since this exercise occurs only after the Euclid's Division Algorithm (Page 34, Amann, Analysis Vol 1) and the Fundamental Theorem of Arithmetic (Page 36), I can not use the result of greatest common divisor of $m$ and $n,$ because that concerns the definition of the negative numbers, which is not coming into being in that section. Therefore, I ask the following question:

Can Euclid's Division Algorithm and/or Fundamental Theorem of Arithmetic implies Ex7? Or in another word, Can we prove Ex7 by only using Euclid's Division Algorithm and/or Fundamental Theorem of Arithmetic?

• Please elaborate on why you think that you cannot use gcds or FTA when you already have learned about those? – Bill Dubuque Aug 2 '14 at 2:03
• One can get by without negative numbers. Euclid did. – André Nicolas Aug 2 '14 at 2:09
• I have said that. Since in that section (Section 5, Chapter 1 of Amann's Book Analysis, even the definition of negative integers is not introduced, we can not use the result that there exist $u,v\in\mathbb{Z}$ such that gcd(m,n)=$mu+nv,$ for $m$ and $n$ may be negative. – azc Aug 2 '14 at 2:11
• @AndréNicolas, Do you mean that the integers $u,v$ in the expression of $\text{gcd}(m,n)=mu+nv$ can be chosen to be nonnegative? – azc Aug 2 '14 at 2:18
• No they cannot. But one can sneak around it by showing that if the numbers we start off with are positive, then there exist integers $u$ and $v$ such that $\gcd(m,n)+um=vn$. – André Nicolas Aug 2 '14 at 2:23

## 2 Answers

It seems you seek a proof avoiding negative integers. One direction is easy. If $\,p = ab,\, a,b>1\,$ is composite then $\,p\mid ab\,$ but $\,p\nmid a,b.\,$ Below are a handful ways to prove the less trivial converse.

$(1)\ \,$ By FTA, if $\, pk =ab,\,$ then comparing the unique prime factorizations arising from both sides we deduce that $\,p\,$ occurs among the prime factors of $\,a\,$ or $\,b,\,$ so $\,p\mid a\,$ or $\,p\mid b.$

Alternatively we can directly employ the Division Algorithm as below.

$(2)\ \$The set $S$ of naturals $\,n\,$ such that $\,\color{#c00}{p\mid nb}\,$ is closed under subtraction $> 0$ and contains $\, a,p\,$ therefore its least positive element $\,\color{#0a0}{d\mid a,p}.\,$ Since $\,\color{#a0f}{d\mid p\ \ \rm prime},\,$ either $\,\color{#a0f}{d=p}\,$ so $\ \color{#0a0}{p=d\mid a},\,$ or $\,\color{#a0f}{d=1}\in S\$ thus $\ \color{#c00}{p\mid d b = b},\$ i.e. $\,\ p\mid \color{}a\,$ or $\ p\mid \color{}b.$

$(3)\ \,$ If gcds are known, then we know the gcd $\, (p,a)\,$ exists, so we can rewrite the proof as

$$p\mid pb,ab\,\Rightarrow\, p\mid(pb,ab)\overset{\color{brown}{\rm(D\,L)}}= (p,a)b = b\ \ {\rm if}\ \ \,(p,a)= 1,\ \ {\rm i.e.}\ \ p\nmid a$$

where we used $\,\color{brown}{\rm(DL)}$ = gcd Distributive Law. Compare this to the analogous proof using the gcd Bezout Identity i.e. $\, (p,a)=1\,$ so $\,jp\!+\!ka = 1\,$ for $\,j,k\in\Bbb Z,\,$ hence

$\qquad\qquad\qquad\ \ p\mid pb, ab\,\Rightarrow\, p\mid jpb,kab\,\Rightarrow\, p\mid (jp\!+\!ka)b = b$

This answer precisely highlighst the analogy between the gcd, Bezout and ideal form of this version of Euclid's Lemma. Since the 2nd and 3rd prooofs of the Distributive Law in the linked post use only positive integers, this provides another approach.

$(4)\ \$ One can present $(3)$ more constructively as Gauss's Algorithm, which is a special case of the Euclidean algorithm when one of the arguments is prime. It iterates $\,p\mid ab\,\Rightarrow\,p\mid (p\ {\rm mod}\ a)b,\,$ producing smaller and smaller multiples of $\,b\,$ divisible by $\,p\,$ till, by induction, we reach $\,b.\,$ This is more intuitive in fractional form.

$(5)\ \,$ Finally another more brute-force approach is to simply eliminate all use of negative numbers in any proof, e.g. by transforming equations to use only positive numbers. But this introduces greater complexity, and tends to obfuscate the arithhmetical essence of the matter.

• In part (1) of your answer, you said that: By FTA, if pk=ab, then comparing the unique prime factorizations arising from both sides we deduce that p occurs among the prime factors of a or b, so p∣a or p∣b. But I do not understand why $p$ must occurs among the prime factors of $a$ or $b$, without using the result to be proved? – azc Aug 2 '14 at 4:34
• @azc By FTA there exists a well-defined set of prime factors $\,P(n)\,$ of $\,n.\,$ Therefore $\tag*{}$ $\quad pk=ab\,\overset{\rm FTA}\Rightarrow\, P(pk) = P(ab)\,\overset{\rm FTA}\Rightarrow\,\{p\}\cup P(k) = P(a)\cup P(b)\,\Rightarrow p\in P(a)\,\ {\rm or}\,\ p\in P(b)$ $\tag*{}$ hence $\,p\mid a\,$ or $\,p\mid b$. – Bill Dubuque Aug 2 '14 at 5:07

OK this is my first answer so don't hold it against me.

I would prove this in two steps.

1. Assume that $\,p$ is the prime and prove that the formula holds. This is by contradiction. If formula would not hold i.e. there exist $\,m,n$ such that $\,p\,\,\mid\,\,mn\,\wedge\,p \nmid m \wedge p \nmid n$, then there would exist factors greater than 1 of $\,m$ and $\,n$, call them $\,m_1$ and $\,n_1$ such that $\,p\,\,\mid\,\,m_1n_1$. Now you can repeat the process and see that $\,m$ and $\,n$ either have infinitely many factors or there exist some factor of either $m$ or $n$ which $p$ divides. Which is contradiction.

2. Assume that the formula holds. Again use contradiction. So assume $\,p$ is not prime. So there exist some factors greater than 1, $\,p_1$ and $\,p_2$ of $\,p$. The formula must hold for $\,m = p_1$ and $\,n = p_2$ so:

$\,p_1p_2\,\,\mid\,\,p_1p_2\,=>\,p_1p_2\,\,\mid\,\,p_1\,\,\,\vee \,\,\,p_1p_2\,\,\mid\,\,p_2$

Again this is contradiction. So we have proven both sides of equivalence.

• Your username has been flagged as objectionable. I tend to agree. Could you use a nicer name, please? – robjohn Aug 3 '14 at 7:29