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.

  • $\begingroup$ You mean the Fundamental Axiom of Arithmetic if you haven't proven Euclid's Lemma yet. $\endgroup$ – fleablood Aug 11 '19 at 23:37
  • $\begingroup$ Trivial: Let $a=\prod p_i^{v_i}$ be the unique factorization of $a$ and $\prod q_j^{w_j}$ be the unique factorization of $b$. So $ab =\prod p_i^{v_i} \prod q_j^{w_j}$ and as $p|ab$, $p$ must be one of $\{p_i\}$ in which case $p|a$ or $p$ must be one of $\{q_i\}$ in which case $p|b$. That was trivial. BUT you can't know that the fundamental theorem of arithmetic is true if you haven't prove Euclid's Lemma first. $\endgroup$ – fleablood Aug 11 '19 at 23:40

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


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.

  • $\begingroup$ Note: in a completely rigorous proof one should be sure to explicitly mention existence and uniqueness of prime factorizations in every place that it is used. $\endgroup$ – Bill Dubuque Aug 11 '19 at 16:19

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.

  • $\begingroup$ I didn't check the proof, but even the wikipedia entry on the fundamental theorem offers a proof without Euclid's lemma. That being said, how does your answer differ from mine? $\endgroup$ – EpsilonDelta Aug 12 '19 at 5:15
  • $\begingroup$ Alternatively, this theorem follows from Jordan-Holder's theorem but this might be overkill. $\endgroup$ – EpsilonDelta Aug 12 '19 at 7:20
  • $\begingroup$ FTA need not be proven with Euclid's lemma but Euclid's lemma is always simpler and more fundamental than FTA which is really a generalization of EL. This is like using trigonometry to prove Euclid's 5 postulate. $\endgroup$ – fleablood Aug 12 '19 at 14:41
  • $\begingroup$ I was just referring to your comment above : "By (E) at least one of the respective sub sigma algebras must be infinite." $\endgroup$ – EpsilonDelta Aug 13 '19 at 12:36
  • $\begingroup$ This is the best explanation of the 3. Thank you. $\endgroup$ – theEigenBreath Aug 14 '19 at 2:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.