Undergrad Fundamental Theorem of Arithmetic - Bhattacharya et al

[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:

In the above text we read the following:" ... ... So let $p_1 \neq q_1$. For definiteness, let $p_1 \gt q_1$. Then

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

By the induction hypothesis either $q_1 = p_i$ for some $i = 2, \ ... \ , s$ or

$q_1 | (p_1 - q_1)$. ... ... "I do not follow how

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

leads to

either $q_1 = p_i$ for some $i = 2, \ ... \ , s$ or $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 ... ... :

 

[PeroK]

The basis of this proof is that, if the FTA does not hold, then there must be a least whole number that has a non-unique prime factorisation. He's assuming that

$n = p_1 \dots p_s = q_1 \dots q_t$

is that whole number. And that any whole number less than $n$ must, therefore, have a unique prime factorisation.

I would change the proof slightly. If the two prime factorisations are different, then we know that they have no primes in common (otherwise we could cancel the common prime). In particular, this means that (without loss of generality) $p_1 > q_1$ and $q_1$ is distinct from all the $p's$.

Now, a bit of algebra gives:

$n > m = (p_1 -q_1)p_2 \dots p_s = q_1(q_2 \dots q_t - p_2 \dots p_s)$

Now, this number $m$ is less than $n$ so must have a unique prime factorisation. In particular, $q_1$ must appear in the prime factorisation of $(p_1 -q_1)p_2 \dots p_s$.

And, as we know $q_1$ is distinct from the $p's$ (*) it must appear in the prime factorisation of $(p_1 -q_1)$ and so, in fact, $p_1 = q_1$, which is a contradiction. You might want to prove this last bit yourself.

(*) note also that $p_2 \dots p_s < n$ so has a unique prime factorisation and cannot have an alternative factorisation involving $q_1$.

 

[Math Amateur]

Thanks for the help PeroK ... much appreciated...

... just working through your post now ...

Thanks again,

Peter

 

[Math Amateur]

The basis of this proof is that, if the FTA does not hold, then there must be a least whole number that has a non-unique prime factorisation. He's assuming that

$n = p_1 \dots p_s = q_1 \dots q_t$

is that whole number. And that any whole number less than $n$ must, therefore, have a unique prime factorisation.

I would change the proof slightly. If the two prime factorisations are different, then we know that they have no primes in common (otherwise we could cancel the common prime). In particular, this means that (without loss of generality) $p_1 > q_1$ and $q_1$ is distinct from all the $p's$.

Now, a bit of algebra gives:

$n > m = (p_1 -q_1)p_2 \dots p_s = q_1(q_2 \dots q_t - p_2 \dots p_s)$

Now, this number $m$ is less than $n$ so must have a unique prime factorisation. In particular, $q_1$ must appear in the prime factorisation of $(p_1 -q_1)p_2 \dots p_s$.

And, as we know $q_1$ is distinct from the $p's$ (*) it must appear in the prime factorisation of $(p_1 -q_1)$ and so, in fact, $p_1 = q_1$, which is a contradiction. You might want to prove this last bit yourself.

(*) note also that $p_2 \dots p_s < n$ so has a unique prime factorisation and cannot have an alternative factorisation involving $q_1$.

PeroK,

Thanks again for your help ...

BUT ... I need help to show that $q_1$ appearing in the prime factorization of $(p_1 -q_1)$ leads to $p_1 = q_1$ ... ...

Can you help further ...

Peter

 

[PeroK]

PeroK,

Thanks again for your help ...

BUT ... I need help to show that $q_1$ appearing in the prime factorization of $(p_1 -q_1)$ leads to $p_1 = q_1$ ... ...

Can you help further ...

Peter

Yes, but if you can't do something simple like that for yourself, then you are going to struggle.

$p_1 - q_1 = rq_1$ for some $r$

$p_1 = (r+1)q_1$

(That itself could be taken to be the contradiction, as you have an alternative prime factorisation for $p_1$)

Or, to continue:

$r = 0$ and $p_1 = q_1$

You need to get used to doing this for yourself. You can't learn number theory by letting Bhattacharya (or me) just spoon feed you all the steps.

 

[Math Amateur]

Thanks again for your help,

Peter