Fundamental Theorem of Arithmetic - Bhattacharya et al - Ch. 2, Section 1

[Math Amateur]

I am reading the book, Basic Abstract Algebra by P.B. Bhattacharya, S.K. Jain, and S.R. Nagpaul ... ... and am currently focused on Chapter 2: Integers, Real Numbers and Complex Numbers ...

I need help with an aspect of the proof of the Fundamental Theorem of Arithmetic in Section 1.3 ... ... The Fundamental Theorem of Arithmetic and its proof as presented by Bhattacharya et al reads as follows:View attachment 5948
View attachment 5949In the above text we read the following:" ... ... So let \(\displaystyle p_1 \neq q_1\). For definiteness, let \(\displaystyle p_1 \gt q_1\). Then\(\displaystyle n \gt (p_1 - q_1) p_2 \ ... \ p_s = p_1p_2 \ ... \ p_s - q_1p_2 \ ... \ p_s \)\(\displaystyle = q_1q_2 \ ... \ q_t - q_1p_2 \ ... \ p_s = q_1 (q_2 \ ... \ q_t - p_2 \ ... \ p_s)\)By the induction hypothesis either \(\displaystyle q_1 = p_i\) for some \(\displaystyle i = 2, \ ... \ , s\) or

\(\displaystyle q_1 | (p_1 - q_1)\). ... ... "I do not follow how \(\displaystyle n \gt (p_1 - q_1) p_2 \ ... \ p_s = p_1p_2 \ ... \ p_s - q_1p_2 \ ... \ p_s
\)\(\displaystyle = q_1q_2 \ ... \ q_t - q_1p_2 \ ... \ p_s = q_1 (q_2 \ ... \ q_t - p_2 \ ... \ p_s)\)leads to either \(\displaystyle q_1 = p_i\) for some \(\displaystyle i = 2, \ ... \ , s\) or \(\displaystyle q_1 | (p_1 - q_1)\). ... ...
Can someone slowly and clearly explain exactly how the above follows ...Hope someone can help ... ...

Peter

======================================================The above refers to what Bhattacharya et al call the Second Principle of Induction ... this principle reads as follows in their text ... ... :
View attachment 5950

 

[Evgeny.Makarov]

I do not follow how \(\displaystyle n \gt (p_1 - q_1) p_2 \ ... \ p_s = p_1p_2 \ ... \ p_s - q_1p_2 \ ... \ p_s
\)\(\displaystyle = q_1q_2 \ ... \ q_t - q_1p_2 \ ... \ p_s = q_1 (q_2 \ ... \ q_t - p_2 \ ... \ p_s)\)leads to either \(\displaystyle q_1 = p_i\) for some \(\displaystyle i = 2, \ ... \ , s\) or \(\displaystyle q_1 | (p_1 - q_1)\).

This follows by the Euclid's lemma.

Alternatively, a number that is smaller than $n$ was represented in two ways:
\[
(p_1 - q_1) p_2 \ ... \ p_s=q_1 (q_2 \ ... \ q_t - p_2 \ ... \ p_s)\qquad(*)
\]
where $p_1-q_1$ and $q_2 \ ... \ q_t - p_2 \ ... \ p_s$ are in turn factored into primes by induction hypothesis. Again by induction hypothesis, both factorizations in (*) should be the same, so either $q_1$ is one of $p_2,\dots,p_s$ or $q_1$ occurs in the factorization of $p_1-q_1$, i.e., divides $p_1-q_1$.

Hint: when $|$ is used as a binary relation, as in $q_1\mid(p_1-q_1)$, or in the set-builder notation, as in $\{x\mid x^2<2\}$, use [m]\mid[/m] to typeset it in LaTeX. This command produces proper spaces on both sides of $|$.

 

[Math Amateur]

This follows by the Euclid's lemma.

Alternatively, a number that is smaller than $n$ was represented in two ways:
\[
(p_1 - q_1) p_2 \ ... \ p_s=q_1 (q_2 \ ... \ q_t - p_2 \ ... \ p_s)\qquad(*)
\]
where $p_1-q_1$ and $q_2 \ ... \ q_t - p_2 \ ... \ p_s$ are in turn factored into primes by induction hypothesis. Again by induction hypothesis, both factorizations in (*) should be the same, so either $q_1$ is one of $p_2,\dots,p_s$ or $q_1$ occurs in the factorization of $p_1-q_1$, i.e., divides $p_1-q_1$.

Hint: when $|$ is used as a binary relation, as in $q_1\mid(p_1-q_1)$, or in the set-builder notation, as in $\{x\mid x^2<2\}$, use [m]\mid[/m] to typeset it in LaTeX. This command produces proper spaces on both sides of $|$.

Thanks Evgeny ... but I need some further help ...Regarding your first explanation ... ...


You write: " ... This follows by the Euclid's lemma. ... ... "
Now Euclid;s Lemma states that if \(\displaystyle p\) is prime and \(\displaystyle p \mid ab\), then either \(\displaystyle p \mid a\) or \(\displaystyle p \mid b\) BUT ... I am having trouble seeing exactly how this applies ... what is \(\displaystyle p, a\) and \(\displaystyle b\) in our case and how does Euclid's Lemma lead to the conclusion ...
Regarding your second explanation ... ...


You write:

" ... ... both factorizations in (*) should be the same, so either $q_1$ is one of $p_2,\dots,p_s$ or $q_1$ occurs in the factorization of $p_1-q_1$, i.e., divides $p_1-q_1$. ... ..."
Yes, I see both factorizations should be the same ... but if $q_1$ is one of $p_2,\dots,p_s$, how exactly does this ensure that the factorizations are the same ...Indeed I have the same problem with $q_1$ occurring in the factorization of $p_1-q_1$ ... ... how exactly does this ensure that the factorizations are the same ...Hope you can help ... sorry to be a bit slow on the uptake ... ...:( ... ...

Peter

 

[Deveno]

Another way to see this is by inducting on the *number* of primes in the factorization.

So if a number can be factored as, say, $k < n$ primes, we assume the factorizations are "the same" (up to a re-ordering of the prime elements).

Now if $a = p_1^{k_1}\cdots p_n^{k_n} = q_1^{r_1}\cdots q_m^{r_m}$

and $p_i = q_j$ for any pair $i,j$, by re-ordering the $p$'s and $q$'s, we can arrange it so that $i = j = 1$.

Then we can consider $a/p_1$, which by our induction hypothesis has a unique factorization.

So the only case left to consider is $p_i \neq q_j$ for *every* pair $i,j$. In particular, then, $p_1 \neq q_1$.

Clearly, $p$ divides the product of $p$'s, and so it must divide the product of $q$'s. Thus it must divide $q_j^{r_j}$ for some $j$, and thus must divide $q_j$. (this is where Euclid's Lemma is applied, twice).

But this cannot happen, because $p_i \mid q_j \iff p_i = q_j$ since these are primes. This is what makes primes so useful.

Now Bhattacharya takes a slightly different approach, which will be a bit clearer if we look at the case where we have a factorization into two primes.

So suppose $a = p_1p_2 = q_1q_2\cdots q_m$, and we know that $p_1 > q_1$ (so we don't have to worry about signs).

Then $b = (p_1 - q_1)p_2 = p_1p_2 - q_1p_2 > 0$, and $a > b$. Now $p_2 \mid b$, and since $b < a$, we must have that $p_1 - q_1$ is a product of primes.

On the other hand, we also have $b = a - q_1p_2 = q_1q_2\cdots q_m - q_1p_2 = q_1(q_2\cdots q_m - p_2)$, so that $q_1$ divides $b$.

By Euclid's Lemma, either $q_1 \mid p_2$ (and this leads to $q_1 = p_2$, and thus $m = 2$, with $p_1 = q_2$ and we are done), or $q_1 \mid p_1 - q_1$, and since $q_1 \mid q_1$, this implies $q_1 = p_1$, a contradiction of our stipulation $p_1 > q_1$.

With a factorization into more than two primes, the argument is essentially the same, but there's a lot more "fussing about" with subscripts (Euclid's Lemma also implies if $p\mid abc$ then $p$ divides one of $a,b$ or $c$, by repeated application).

 

[Evgeny.Makarov]

Now Euclid;s Lemma states that if \(\displaystyle p\) is prime and \(\displaystyle p \mid ab\), then either \(\displaystyle p \mid a\) or \(\displaystyle p \mid b\) BUT ... I am having trouble seeing exactly how this applies ... what is \(\displaystyle p, a\) and \(\displaystyle b\) in our case and how does Euclid's Lemma lead to the conclusion

We established that
\[
n \gt (p_1 - q_1) p_2 \ ... \ p_s = p_1p_2 \ ... \ p_s - q_1p_2 \ ... \ p_s=\\
q_1q_2 \ ... \ q_t - q_1p_2 \ ... \ p_s = q_1 (q_2 \ ... \ q_t - p_2 \ ... \ p_s)
\]
In particular,
\[
(p_1 - q_1) p_2 \ ... \ p_s=q_1 (q_2 \ ... \ q_t - p_2 \ ... \ p_s).
\]
This means that $q_1$ divides the left-hand side. Now we apply the Euclid's lemma as you stated it by putting $p=q_1$, $a=p_1 - q_1$ and $b=p_2\dots p_s$. By the lemma, either $q_1\mid (p_1-q_1)$ or $q_1\mid (p_2\dots p_s)$. In the latter case, we apply the Euclid's lemma repeatedly until we find $p_i$ such that $q_1\mid p_i$, which means $q_1=p_i$.

You write:

" ... ... both factorizations in (*) should be the same, so either $q_1$ is one of $p_2,\dots,p_s$ or $q_1$ occurs in the factorization of $p_1-q_1$, i.e., divides $p_1-q_1$. ... ..."
Yes, I see both factorizations should be the same ... but if $q_1$ is one of $p_2,\dots,p_s$, how exactly does this ensure that the factorizations are the same

It does not have to ensure that the factorizations are the same. We already know that they are the same as a result of applying the inductive hypothesis to $(p_1 - q_1) p_2\dots p_s$.