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$
$\endgroup$
2
-
$\begingroup$ You mean the Fundamental Axiom of Arithmetic if you haven't proven Euclid's Lemma yet. $\endgroup$– fleabloodAug 11, 2019 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$– fleabloodAug 11, 2019 at 23:40
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
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$.
$\begingroup$
$\endgroup$
1
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.
answered Aug 11, 2019 at 16:17
-
$\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$ Aug 11, 2019 at 16:19
$\begingroup$
$\endgroup$
5
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$– J. De RoAug 12, 2019 at 5:15
-
$\begingroup$ Alternatively, this theorem follows from Jordan-Holder's theorem but this might be overkill. $\endgroup$– J. De RoAug 12, 2019 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$ Aug 12, 2019 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$– J. De RoAug 13, 2019 at 12:36
-
$\begingroup$ This is the best explanation of the 3. Thank you. $\endgroup$ Aug 14, 2019 at 2:28