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

Math Amateur
Gold Member
MHB
Messages
3,920
Reaction score
48
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 $$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 ... ... :
View attachment 5950
 
Physics news on Phys.org
Peter said:
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)$$.
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 $|$.
 
Evgeny.Makarov said:
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 $$p$$ is prime and $$p \mid ab$$, then either $$p \mid a$$ or $$p \mid b$$ BUT ... I am having trouble seeing exactly how this applies ... what is $$p, a$$ and $$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
 
Last edited:
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).
 
Peter said:
Now Euclid;s Lemma states that if $$p$$ is prime and $$p \mid ab$$, then either $$p \mid a$$ or $$p \mid b$$ BUT ... I am having trouble seeing exactly how this applies ... what is $$p, a$$ and $$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$.

Peter said:
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$.
 
I asked online questions about Proposition 2.1.1: The answer I got is the following: I have some questions about the answer I got. When the person answering says: ##1.## Is the map ##\mathfrak{q}\mapsto \mathfrak{q} A _\mathfrak{p}## from ##A\setminus \mathfrak{p}\to A_\mathfrak{p}##? But I don't understand what the author meant for the rest of the sentence in mathematical notation: ##2.## In the next statement where the author says: How is ##A\to...
The following are taken from the two sources, 1) from this online page and the book An Introduction to Module Theory by: Ibrahim Assem, Flavio U. Coelho. In the Abelian Categories chapter in the module theory text on page 157, right after presenting IV.2.21 Definition, the authors states "Image and coimage may or may not exist, but if they do, then they are unique up to isomorphism (because so are kernels and cokernels). Also in the reference url page above, the authors present two...
When decomposing a representation ##\rho## of a finite group ##G## into irreducible representations, we can find the number of times the representation contains a particular irrep ##\rho_0## through the character inner product $$ \langle \chi, \chi_0\rangle = \frac{1}{|G|} \sum_{g\in G} \chi(g) \chi_0(g)^*$$ where ##\chi## and ##\chi_0## are the characters of ##\rho## and ##\rho_0##, respectively. Since all group elements in the same conjugacy class have the same characters, this may be...
Back
Top