The following is a proof of the Fundamental Theorem of Arithmetic.

Assume that an integer $a\ge2$ has factorizations

$a=p_1\cdots\ p_m$ and $a=q_1\cdots\ q_n$,

where the $p$'s and $q$'s are primes. Then $n=m$ and the $q$'s may be reindexed so that $q_i=p_i$ for all $i$. Hence, there are unique distinct primes $p_i$ and unique integers $e_i>0$ with

$a=p_1^{e_1}\cdots\ p_n^{e_n}$.


We prove the theorem by induction on $l$, the larger of $m$ and $n$. If $l=1$, then the given equation is $a=p_1=q_1$, and the result is obvious. For the inductive step, note that the equation gives $p_m|q_1\cdots\ q_n$. By Euclid's lemma, there is some $i$ with $p_m|q_i$. But $q_i$, being a prime, has no positive divisors other than $1$ and itself, so that $q_i=p_m$. Reindexing, we may assume that $q_n=p_m$. Canceling, we have $p_i\cdots\ p_{m-1}=q_1\cdots \ q_{n-1}$. By the inductive hypothesis, $n-1=m-1$ and the $q$'s may be reindexed so that $q_i=p_i$ for all i.

So far, I think that we say that $l$ is the larger of $m$ and $n$ because at the beginning of the proof, we don't know if $m$ and $n$ are equal. But why does it have to be the largest? Also, even though I understand that both forms of induction are essentially the same, it's kind of hard to follow how we can say that $q_i=p_i$ for all $i$ from our inductive hypothesis. It would be nice if someone could possibly spell out the steps of the induction in a more detailed fashion.

  • $\begingroup$ What do you mean by "both forms of induction"? $\endgroup$ – Eric Wofsey Nov 10 '17 at 21:13
  • $\begingroup$ strong induction and weak induction $\endgroup$ – K.M Nov 10 '17 at 21:14
  • $\begingroup$ This proof uses weak induction, not strong induction. $\endgroup$ – Eric Wofsey Nov 10 '17 at 21:14
  • $\begingroup$ If possible, I would like a more detailed explanation as to how the proof uses weak induction. $\endgroup$ – K.M Nov 10 '17 at 21:15
  • 2
    $\begingroup$ Weak induction proves that if true for $m$ then true for $m+1$. If being true for $m$ implies true for $m+1$ then being true for all values of $m$ and lower will imply true for $m+1$. Because being true for all values of $m$ and lower must imply it is true for $m$. If a proof needs you use it is true for $m$ and lower values it is strong. If it only needs to use it is true for $m$ it is weak. If a weak proof works, then it can be made strong by just stating "as well as assuming true for m, we assume it is true for all lesser values... we won't use the fact... but we can assume it." $\endgroup$ – fleablood Nov 10 '17 at 23:01

Note that the theorem says that $n=m$ and that the $q$'s may be reindexed so that $q_i=p_i$ for all $i$. It does not say that $q_i=p_i$ for all $i$.

The induction hypothesis is that this is true if the larger of $m$ and $n$ is $l-1$ (weak induction). The proof shows that if the larger of $m$ and $n$ is equal to $l$, then $p_m=q_n$ after reindexing. Cancelling $p_m=q_n$ we are left with the identity $$p_1\cdots p_{m-1}=q_1\cdots q_{n-1}.$$ The larger of $m-1$ and $n-1$ is $l-1$, so the induction hypothesis tells us that $n-1=m-1$ and that after reindexing we have $q_i=p_i$ for all $i$ up to $m-1$. Hence $n=m$ and after reindexing we have $q_i=p_i$ for all $i$.

| cite | improve this answer | |

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.