Monday, April 10, 2017

elementary number theory - How do we apply induction to this proof of the Fundamental Theorem of Arithmetic?



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



Proof.




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.


Answer



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


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...