Proof of Euclid's lemma using fundamental theorem of arithmetic

Question

I want a proof of Euclid's theorem (if p is prime and p|(a.b) where a and b are integers, then either p|a or p|b) using the fundamental theorem of arithmetic. I already understand the proof assuming p is not |a and using gcd(p,a). I want a proof that rely's on FTofA. Searching on line I can find examples of using Euclid's lemma to prove Fundamental Theorem of Arithmetic but I want to go the other direction, and assuming Fundamental Theorem of Arithmetic, prove Euclid's lemma.

Answer 1

Let $p$ be prime and $a,b$ integers with $p|ab$.

This means that there is an integer $k$ such that $pk=ab$. Writing out the prime factorisations of $a,b$ and $k$, we have left and right of the equal sign a decomposition in prime factors and uniqueness of prime factorisation tells us that $p$ is a prime in the prime factorisation of either $a$ or $b$. In particular, $p|a$ or $p|b$.

Answer 2

Hint $ $ we sketch a proof of the general Euclid's lemma $\rm\,\gcd(a,b)=1,\ a\mid bc\,\Rightarrow\, a\mid c\,$ from here.

$\rm\, a\mid bc\:$ so $\rm\:ad = bc\:$ for some $\rm\:d.\:$ By existence we can factor all four terms into prime factors, and by uniqueness the same multiset of primes occurs on both sides. So all of the primes in the factorization of $\rm\:a\:$ must also occur on RHS, necessarily in the factorization of $\rm\:c,\:$ by $\,\rm \gcd(a,b)\!=\!1$. Thus $\rm\:a\mid c\:$ since all of its prime factors (counting multiplicity) occur in $\rm\:c.\:$

Remark $ $ The inference is (multi)set-theoretic: $\rm\: A\cap B = \{\,\},\ \ A \cup D\,=\, B\cup C\:$ $\:\Rightarrow\:$ $\rm\:A\subset C,\:$ where $\rm\:A =$ multiset of primes in the unique prime factorization of $\rm\:A,\:$ and similarly for $\rm\:B,C,D.$

Well worth knowing (& proving!) is the following primal generalization from primes to composites

Prime Divisor Property $\rm\quad p\ |\ a\:b\ \Rightarrow\ p\:|\:a\ $ or $\rm\ p\:|\:b,\ $ for all primes $\rm\:p\,;\:\: $ more generally

Primal Divisor Property $\rm\ \ \: c\ |\ a\:b\ \Rightarrow\ c_1\, |\: a\:,\: $ $\rm\ c_2\:|\:b\,\ \ \&\,\ \ c = c_1\:c_2,\ $ for all $\rm\:c$

The latter property may be considered to be a generalization of the prime divisor property from atoms (irreducibles) to composites (one easily checks that atoms are primal $\Leftrightarrow$ prime). This way leads to various refinement-based views of unique factorization, e.g. via Schreier refinement and Riesz interpolation, the Euclid-Euler Four Number Theorem (Vierzahlensatz), etc, which prove more natural in noncommutative rings - see Paul Cohn's 1973 Monthly survey Unique Factorization Domains.

Answer 3

It's trivial.

Let $a=\prod p_i^{v_i}$ be the unique prime factorization of $a$ and $b=\prod q_j^{w_j}$ be the unique prime factorization of $b$. So $ab =\prod p_i^{v_i} \prod q_j^{w_j}$ is the unique prime factorization of $ab$.

And if $p|ab$, $p$ must be either one of the $\{p_i\}$ which would mean $p|a$, or $p$ must be one of the $\{q_j\}$ which would mean $p|b$.

But how can you know the Fundamental Theorem of Arithmetic is true in the first place? That is an essential question and can not be ignored.