Avoiding negative integers in proof of Fundamental Theorem of Arithmetic

Question

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?

Answer 1

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 highlights the analogy between the gcd, Bezout and ideal form of this version of Euclid's Lemma. Since the 2nd and 3rd proofs 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 arithmetical essence of the matter.

Answer 2

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.