Proof of Euclid's lemma using fundamental theorem of arithmetic 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.
 A: 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$.
A: Hint $ $ For the general Euclid's lemma $\rm\,\gcd(a,b)=1,\ a\mid bc\,\Rightarrow\, a\mid c\,$ below is a sketch from here.
$\rm\ a\mid bc\:$ so $\rm\:ad = bc\:$ for some $\rm\:d.\:$ Thus by existence, we can factor all four terms into prime factors. 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 to composites (one easily checks that atoms are  primal $\Leftrightarrow$ prime). This leads to various "refinement" views of unique factorizations, 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.
A: 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.
