Avoiding negative integers in proof of Fundamental Theorem of Arithmetic

Solution 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.