1
$\begingroup$

I am having trouble trying to understand the uniqueness part of the proof. It uses induction on n (n is claimed to have a unique factorization of primes).

Here is my understanding so far:

Let $n$ be an integer such that $n>1$. Then $n=p_{1}p_{2}\cdots p_{k}$, with $p_{1},p_{2},...,p_{k}$ being primes, is a unique factorization of $n$.

Proof: (Uniqueness) (proof by induction) The base case states that for $n=2$, $n$ is a product of primes, which is true ($2$ is prime).

Now assume this is true for integers $m$ with $1\leq m < n$.

This is the part I don't understand. Why is $m \geq 1$ when $1$ cannot be written as a product of primes?

and $n=p_{1}p_{2}\cdots p_{k} = q_{1}q_{2}\cdots q_{l}$ with $p_{1}\leq p_{2}\leq \cdots \leq p_{k}$ and $q_{1}\leq q_{2}\leq \cdots \leq q_{l}$

Again, I am lost. Why is $n$ written in such a way when the inductive hypothesis uses $m$? Is it because the inductive step uses $n$ still and the fact for $m$ is used implicitly?

Then $p_{1} |q_{i}$ for some $1\leq i \leq l$ and $q_{1} |p_{j}$ for some $1\leq j \leq k$. Since all $p_{j}$ and $q_{i}$ are prime, their only divisors are $1$ and itself. Therefore, $p_{1} =q_{i}$ and $q_{1}=p_{j}$. Since $p_{1} \leq p_{j} = q_{1} \leq q_{i}=p_{1}$, $p_{1}=q_{1}$.

I understand this part of the proof.

Then by inductive hypothesis, $n'=p_{2}\cdots p_{k} = q_{2}\cdots q_{l}$.

Is this because, since $p_{1}=q_{1}$, they are cancelled out creating a new integer $n'$? And so does this induction continue until $p_{k}=q_{l}$, which will ultimately lead to $1=1$?

This proof by induction is very brief for me to understand and digest right away.

$\endgroup$
1
$\begingroup$

This is the part I don't understand. Why is $m\ge1$ when $1$ cannot be written as a product of primes?

In a technical sense, $1$ is a product of primes - it's the empty product (and the empty set $\varnothing$ is vacuously a set of primes, in the sense that it does not contain an element which is not prime), but you might as well just assume the author instead wrote $2\le m< n$ (except for the small caveat of how the proof functions when $n$ itself is prime).

Again, I am lost. Why is $n$ written in such a way when the inductive hypothesis uses $m$? Is it because the inductive step uses $n$ still and the fact for $m$ is used implicitly?

This is how induction always works: after you assume your base case ($2$) and your inductive hypothesis (all $m<n$), you then explore the claim for the value of $n$ itself. Here, we've assumed the claim (unique factorization) is true for all $m<n$, and now we're going to see if the claim holds as well for the number $n$.

So we write two factorizations for $n$, and show they must in fact be the same factorization (in such a way that will use the inductive hypothesis).

Is this because, since $p_1=q_1$, they are cancelled out creating a new integer n′n′?

Yes.

And so does this induction continue until $p_k=q_l$, which will ultimately lead to $1=1$?

Essentially, yes. Logically, this is a strong induction proof (which is why our inductive hypothesis involved all integers $m$ less than $n$, not just one), so we seem to be applying our inductive hypothesis to the value $m=n'$ in order to conclude the two factorizations of $n'$ are the same.

$\endgroup$
  • $\begingroup$ Oh, I see now about there being an empty product. I never think about the vacuous cases! Thank you for explaining about the inductive hypothesis part, you made it very clear to understand! Now I know why they did what they did. Thank you for taking the time to let me know. $\endgroup$ – numericalorange Jan 20 '18 at 17:56

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.