I Clarifications needed for an exercise in Hungerford's abstract algebra

  • I
  • Thread starter Thread starter elias001
  • Start date Start date
  • Tags Tags
    Abstract algebra
elias001
Messages
363
Reaction score
24
Let ##R## be a UFD. If ##a\mid bc## and ##1_R## is a gcd of ##a## and ##b,## prove that ##a\mid c.##

Solution: Let ##\text{gcd}(a,b)=1_R##, then ##(a,b)\sim 1_R.## Then there exists ##x,y\in R## so that ##ax+by=1_R##. So ##c(ax+by)=c## for some ##c\in R.## Since ##a\mid bc,## implies ##bc=ad## for some ##d\in R.## Then ##c(ax+by)=(ca)x+(bc)y=(ca)x+(ad)y=a(cx+by)=c.## This implies ##a\mid c.##

[Hungerford's soluion:]

For some ##d,bc=ad.## if ##a=r_1r_2\cdots r_k,d=z_1z_2\cdots z_n, b=p_1p_2\cdots p_s,## and ##c=q_1q_2 \cdots q_t,## with each ##p_i, q_i, r_i, z_i## irreducible, then ##p_1p_2\cdots p_sq_1q_2\cdots q_t=r_1r_2\cdots r_kz_1z_2\cdots z_n.## So each ##r_i## is an associate of ##p_j## or ##q_j.## But ##r_i## cannot be an associate of any ##p_j## (otherwise ##r_i## would divide the gcd ##1_R## of ##a## and ##b,## which implies that the irreducible ##r_i## is a unit).

Question: I am not exactly sure what Hungerford did. The solution I posted is what I did, I mean as soon as one is given a gcd to two numbers, and the given assumption, the solutions almost screams out automatically after applying the little algebra required from the definition of gcd.
 
Last edited:
Physics news on Phys.org
elias001 said:
Let ##R## be a UFD. If ##a\mid bc## and ##1_R## is a gcd of ##a## and ##b,## prove that ##a\mid c.##

Solution: Let ##\text{gcd}(a,b)=1_R##, then ##(a,b)\sim 1_R.## Then there exists ##x,y\in R## so that ##ax+by=1_R##. So ##c(ax+by)=c## for some ##c\in R.## Since ##$a\mid bc,$## implies ##bc=ad## for some ##d\in R.## Then ##c(ax+by)=(ca)x+(bc)y=(ca)x+(ad)y=a(cx_by)=c.## This implies ##a\mid c.##

[Hungerford's soluion:]



Question: I am not exactly sure what Hungerford did. The solution I posted is what I did, I mean as soon as one is given a gcd to two numbers, and the given assumption, the solutions almost screams out automatically after applying the little algebra required from the definition of gcd.
The problem with your solution is, that you used Bézout's lemma, which allows us to write ##1_R=ax+by.## But Bézout's lemma is proven for Euclidean rings. Euclidean rings are unique factorization domains, but not the other way around. Here is a nice list of what implies what:
https://en.wikipedia.org/wiki/Unique_factorization_domain

Hence we may not use Bézout's lemma for arbitrary unique factorization domains. However, what we may use is exactly this: writing any element as a unique (up to units) product of irreducible elements ##r_i,p_j,q_k,## which is what Hungerford's proof uses.
 
@fresh_42 is it a theorem that states in an UFD, bezout's theorem cannot be used. There is a theorem/exercise in Hungerford and other books about existence of Bezout iff sum of two principal ideals are principal. I would like a book reference about in what circumstances Bezout holds inn UFD for future reference. Also, if we have the gcd of two integers and can't use Bezout's theorem, that feels weird. Also i am replying to a few of your posts right now. Sorry for taking so lon
 
Last edited:
elias001 said:
@fresh_42 is it a theorem that states in an UFD, bezout's theorem cannot be used. I am not doubting you. I would like a book reference for future reference. Also, if we have the gcd of two integers and can't use Bezout's theorem, that feels weird. Also i am replying to a few of your posts right now. Sorry for taking so long.
It is not about whether it cannot be used. The question is whether it can be used! And the lemma requires a Euclidean ring because you need a form of Euclidean algorithm to arrive at the formula ##1_R=ax+by.## And an arbitrary unique factorization domain does not possess this property.

For example, ##R=\mathbb{Z}[x]## has the unique factorization property, but there is no way to write
$$
1=p(x)\cdot x^2 +q(x)\cdot (x+1)
$$
with integer polynomials ##p(x),q(x).##
 
elias001 said:
@fresh_42 is it a theorem that states in an UFD, bezout's theorem cannot be used. I am not doubting you. I would like a book reference for future reference. Also, if we have the gcd of two integers and can't use Bezout's theorem, that feels weird. Also i am replying to a few of your posts right now. Sorry for taking so long.
The integers are a Euclidean ring, so you can use Bézout on integers.

But Hungerford's statement isn't about integers.
 
@fresh_42 how do algebraists keep track of which domains allows for which properties to hold. ED, PID, UFD. They all seem all to be very similar. Is like if you meet an eastern European, how does one tell if they are Polish, Ukrainian or Russian just from the language they speak. They all sound very similar.
 
I look it up if in doubt, e.g. on the page I linked to. If a ring is Euclidean, then things are easy, since you have everything else, except a field. You could try to prove those inclusions, which helps. By the time you get a kind of sense of what implies what. I only get occasionally confused with PID ⊂ UFD.

Two facts are important:

Euclidean means that we can write ##a=q\cdot b +r## with ##0\le |r| < |b|.## This is a division of ##a## by ##b## without the necessity to invert ##b.## However, it needs a function ##r\mapsto |r|## that "evaluates" whether the remainder ##r## of the "division" is smaller than the number ##b## by which we divide. In the integers, we can take the absolute value, in a polynomial ring we have ##|r|=\deg(r)## to "measure" them. So the Euclidean property comes closest to a real division, and that simplifies things a lot because we can iterate this division (##b=q'\cdot r + r'## with ##|r'|<|r|##) and end up with a smallest remainder at the end because the "measure" gets smaller with each step.

The other important fact to know is that prime ideals are a generalization of prime integers, and principal ideals are those generated by one element only, a generalization of the greatest common divisor of all ideal elements. It is also helpful to remember that the definition of a prime number, which we all learned at school, is false: "A prime number is only divisible by ##1## and itself." This phrase has at least three problematic issues. Firstly, it defines irreducibility and not primality. It only works because these two terms are equivalent over the integers. But this equivalence had to be proven! Secondly, it ignores that we can also divide by ##-1,## which is the other unit in the integers. And thirdly, it doesn't explain why we do not consider units not prime.

You can view the integers as a typical ring. And the other ones result from taking away some properties. In most cases, you get an example if you consider ##R\in \{\mathbb{Q},\mathbb{Z},\mathbb{Z}_{n},\mathbb{Z}[\sqrt{d}] M(n,\mathbb{F})\}## or their polynomial rings.

A personal note: don't be so focused on units. They are simply disturbances that prevent us from calling something unique. If ##a\,|\,b## and ##u## is a unit then ##(a\cdot u)\,|\,b## or ##a\,|\,(b\cdot u).## That is why we have to deal with them when speaking about primality, irreducibility, and divisibility. They become more important in rings like ##\mathbb{Z}_n## if ##n## isn't prime, or in matrix rings. But for now, they are only nasty factors ruining uniqueness.
 
@fresh_42 I just look over the question and Hungerford's solution again. Why is ##\text{gcd}(a,b)=1_R## relevant. Since ##a\mid bc\Rightarrow \exists d\in R(bc=ad),## then ##a\mid c.## Am I missing something here? Also where in the question does it says that ##a## is not an associate of ##b## or of ##c##?
 
Look at an example. Say we have ##a=6## and ##b=10.## Then ##\operatorname{gcd}(6,10)=2.## Next, we choose ##c=3.## Then ##a=6\,|\,b\cdot c=10\cdot 3 =30=6\cdot 5## but ##a=6\,\nmid\,c=3.##

You should really try to figure out such examples yourself, because it is important to get used to the terms you use. Another reason I don't like AIs. They pretend to think for you.

Can you construct a similar example for integer polynomials?
 
  • #10
@fresh_42 I think the argument in Hungerford should go more like this: if ##\text{gcd}(a,b)=1_R\;(*)##, and ##\exists d\in R(ad=bc)##, then ##a## and ##b## are not associate of each other; otherwise, that would mean ##c## is an unit element, that would imply ##a\mid b## and ##b\mid a## which contradicts ##(*)##.
 
Last edited:
  • #11
elias001 said:
@fresh_42 wait wait, I think i see it. In Hungerford's text, there is a theorem that states: one of the two condiditions for an integral domain ##R## to be an UFD is that if and only if whenever ##x## is an irreducible element in ##R## and ##x|mn## then ##x| m## or ##x|n##.
This is the definition of a prime element. So what he actually says here is that irreducible elements are prime elements in rings with a unique factorization. (I'm not sure about the converse. I have found a ring with a prime element that is not irreducible, but I haven't checked whether it is a UFD.)
elias001 said:
So if ##\text{gcd}(a,b)=1_R##, and ##\exists d\in R(ad=bc)##, then ##a## and ##b## are not associate of each other; otherwise, that would mean ##c## is an unit element, that would imply ##a\mid b## which contradict ##\text{gcd}(a,b)=1_R##. With the exact same reasoning, ##d## is not an associate to either ##b## or ##c##. This would mean that both ##a## and ##d## are both non unit elements and hence both are irreducible elements of ##R##. By the stated theorem in Hungerford's text, we have ##a\mid c##. Is my argument correct?
Not quite.

a) ##a## is allowed to be a unit. In that case, we simply won't have anything to prove, but it is not ruled out.
b) ##d=b## is also a possibility. So ##d## and ##b## can be associated. You don't have to care about ##d## if you use the factorization of the given elements, which is what Hungerford does. I don't see a shortcut to his argument.
 
  • #12
elias001 said:
@fresh_42 I think the argument in Hungerford should go more like this: if ##\text{gcd}(a,b)=1_R\;(*)##, and ##\exists d\in R(ad=bc)##, then ##a## and ##b## are not associate of each other; otherwise, that would mean ##c## is an unit element, that would imply ##a\mid b## and ##b\mid a## which contradicts ##(*)##.
This only shows that if ##a## and ##b## were associated, then all elements ##a,b,c## would be units. This is not Hungerford's statement, only a very specific case. You still have to make sure that all divisors of ##a## are gathered in ##c,## possibly more.
 
  • #13
@fresh_42 i just edited my post. I just don't see from his argument how I can conclude that ##a\mid c##. Also, i dont know how to show that ##b## is an unit element. That would make ##a## an irreducible element with ##c## being a non-unit element. Then the conclusion should follow.
 
  • #14
elias001 said:
@fresh_42 i just edited my post. I just don't see from his argument how I can conclude that ##a\mid c##. Also, i dont know how to show that ##b## is an unit element. That would make ##a## an irreducible element with ##c## being a non-unit element. Then the conclusion should follow.
##a## is neither irreducible nor a non-unit. Both are possible.

If ##a## is a unit, then there is nothing to show. Otherwise, every divisor of ##a## has to be a divisor of ##c,## but why?

Say we have ##a=2## and ##b=1+\sqrt{-5}.## Then ##\operatorname{gcd}(a,b)=1.## Now we have
$$
a=2\,|\,b\cdot \left(1-\sqrt{-5}\;\right)=\left(1+\sqrt{-5}\;\right)\cdot \left(1-\sqrt{-5}\;\right)=6=2\cdot 3
$$
but ##a\,\nmid\,c=\left(1-\sqrt{-5}\;\right).##
 
  • #15
@fresh_42 in Hungerford's solution it states that all the ##r_j##s are factors of ##a## are not units elements because each of the ##r_j## can not be an associate to any of the ##p_j##s which themselves are factors of ##b##. So ##a## can not be an unit element. Doesn't this imply that if none of the factors of ##b## can be divided by factors of ##a##, then the factors of ##c## can be divided by factors of ##a##. So ##c|a##?
 
  • #16
elias001 said:
@fresh_42 in Hungerford's solution it states that all the ##r_j##s are factors of ##a## are not units elements because each of the ##r_j## can not be an associate to any of the ##p_j##s which themselves are factors of ##b##. So ##a## can not be an unit element. Doesn't this imply that if none of the factors of ##b## can be divided by factors of ##a##, then the factors of ##c## can be divided by factors of ##a##. So ##c|a##?
He only left out the trivial case if ##a## is a unit, since there is nothing to do. But the statement itself allows that case.

Look at my example! The ring in question is ##R=\mathbb{Z}[\sqrt{-5}].## If you do not use the UFD property, then this ring says that the statement would be false. Hence, you need the UFD property; hence, there is no shortcut to Hungerford's proof. You have to control all possible divisors.
 
  • #17
@fresh_42 how can ##a## be an unit, and why does that matter? Also, the condition that##(a,b)=1## automatically means ##a## can't be an unit?
 
  • #18
elias001 said:
@fresh_42 how can ##a## be an unit, and why does that matter? Also, the condition that##(a,b)=1## automatically means ##a## can't be an unit?
Forget about it. It is only the trivial case. If ##a=c=1## and ##b## anything, then the statement is still true. And there is no line in Hungerford's proof that wouldn't work for ##k=0.##
 
  • #19
@fresh_42 if ##k=0##, then we only have ##r_0##. Then ##a=r_0## and ##a## is still a non unit and ##a## would still divide ##c## since it doesn't divide any of the factors of ##b.## Am I correct in my reasoning?
 
Last edited:
  • #20
elias001 said:
@fresh_42 if ##k=0##, then we only have ##r_0##. Then ##a=r_0## and ##a## is still a non unit and ##a## would still divide ##c## since it doesn't divide any of the factors of ##b.## Am I correct in my reasoning?
No. ##a=r_1\cdots r_k## and if ##k=0## we have an empty product, so ##a## is associated to ##1.##
 
  • #21
@fresh_42 I rewritten the proof using property of the gcd without much reference to unit elements.

Let ##a=u{p_1}^{m_1}{p_2}^{m_2}\cdots {p_k}^{m_k}, b=v{q_1}^{n_1}{q_2}^{n_2}\cdots{q_k}^{n_k},c=w{p_1}^{k_{1}}{p_2}^{k_{2}}\ldots,{p_t}^{k_{t}},## and all the ##p_i##s,##q_i##s are prime integers and the exponents ##m_i,k_i, n_i## are all non negative integers for ##i=1,2,\ldots,t,## with ##u,v,w## being unit elements of ##R.##

So given ##a\mid bc,\text{gcd}(a,b)=1_R,## then ##a=u{p_1}^{m_1}{p_2}^{m_2}\cdots {p_k}^{m_k}{q_1}^{0}{q_2}^{0}\cdots{q_k}^{0}=bc=v({p_1}^{0}{p_2}^{0}\cdots {p_k}^{0}{q_1}^{n_1}{q_2}^{n_2}\cdots{q_k}^{n_k})\cdot(w{p_1}^{k_{1}}{p_2}^{k_{2}}\ldots,{p_t}^{k_{t}}),## that means ##\text{min}(m_i,0)=\text{min}(0,n_i)=0_R.##

But ##a\mid bc## also means ##bc=v({p_1}^{0}{p_2}^{0}\cdots {p_k}^{0}{q_1}^{n_1}{q_2}^{n_2}\cdots{q_k}^{n_k})u^{-1}\cdot(w{p_1}^{c_{1}}{p_2}^{c_{2}}\ldots,{p_t}^{v_{t}}),## and ##c_i=k_{i}-{m_i}> 0,i=1,2,\ldots,t.##

We can let ##m=wu^{-1}{p_1}^{k_{1}-{m_1}}{p_2}^{k_{2}-{m_2}}\ldots,{p_t}^{k_{t}-{m_t}},## then ##\text{min}(m_i,k_i)\neq 0_R.## for ##i## from ##1## to ##t,## which implies ##a\mid c.##

I did not comment on your example of qudratic integers because Hungerford covers that topic in the following section and in the topics on fields. In the section where the question is from, there were no mentions to qudaratic integers. Also when you mentioned about ##k=0##, it was confusing for me since I thought the ##r_k##s are allow to have index from zero onwards. Actually, the entire proof was confusing and complicated, since hungerford should have given a direct proof having to do with prime factorization and use the equivalent definition of gcd without making reference to unit elements.
 
Last edited:
  • #22
elias001 said:
@fresh_42 I rewritten the proof using property of the gcd without much reference to unit elements.

Let ##a=u{p_1}^{m_1}{p_2}^{m_2}\cdots {p_k}^{m_k}, b=v{q_1}^{n_1}{q_2}^{n_2}\cdots{q_k}^{n_k},c=w{p_1}^{k_{1}}{p_2}^{k_{2}}\ldots,{p_t}^{k_{t}},## and all the ##p_i##s,##q_i##s are prime integers and the exponents ##m_i,k_i, n_i## are all non negative integers for ##i=1,2,\ldots,t,## with ##u,v,w## being unit elements of ##R.##
I wouldn't carry the units all the way through the proof. That is why we speak of associated elements, which means "equal up to units". Also, using the letter ##p## for the irreducible elements in the factorization of ##a## and ##c## is confusing. There is a reason Hungerford used ##r## and ##q## instead. We need to show that each of those in ##a## is associated with some in ##c.## Using ##p## for both seems like using the result for the proof.
elias001 said:
So given ##a\mid bc,\text{gcd}(a,b)=1_R,## then ##a=u{p_1}^{m_1}{p_2}^{m_2}\cdots {p_k}^{m_k}{q_1}^{0}{q_2}^{0}\cdots{q_k}^{0}=bc=v({p_1}^{0}{p_2}^{0}\cdots {p_k}^{0}{q_1}^{n_1}{q_2}^{n_2}\cdots{q_k}^{n_k})\cdot(w{p_1}^{k_{1}}{p_2}^{k_{2}}\ldots,{p_t}^{k_{t}}),## that means ##\text{min}(m_i,0)=\text{min}(0,n_i)=0_R.##
No. You cannot simply assume ##a=bc.## I assume your second equality sign should have been an AND. Furthermore, ##m_i,n_i## are natural numbers, integers. Their minimum is thus also an integer, and not ##0_R.##
elias001 said:
But ##a\mid bc## also means ##bc=v({p_1}^{0}{p_2}^{0}\cdots {p_k}^{0}{q_1}^{n_1}{q_2}^{n_2}\cdots{q_k}^{n_k})u^{-1}\cdot(w{p_1}^{c_{1}}{p_2}^{c_{2}}\ldots,{p_t}^{v_{t}}),## and ##c_i=k_{i}-{m_i}> 0,i=1,2,\ldots,t.##
This makes no sense. We have ##ad=bc## for some ##d\in R.## Where is it? Where is even ##a##? And why did you multiply by ##u^{-1}?##
elias001 said:
We can let ##m=wu^{-1}{p_1}^{k_{1}-{m_1}}{p_2}^{k_{2}-{m_2}}\ldots,{p_t}^{k_{t}-{m_t}},## then ##\text{min}(m_i,k_i)\neq 0_R.## for ##i## from ##1## to ##t,## which implies ##a\mid c.##
Reread Hungerford's argument. You don't have to deal with all the irreducible factors in one step, and show the divisor. All we need is that ##r_i## (in your "bad" notation ##p_i^{m_i}##) has to be associated with a ##q_j## (in your notation ##p_j^{k_j}##, which is why it is "bad", since you cannot distinguish between irreducible elements by their powers!).

If you want to formally gather all ##r_i## afterward, you would get something like ##r_i=u_i\cdot q_{j(i)}.## However, this is an unnecessary complication of notation, and we haven't even addressed the different powers.
Please also note that Hungerford didn't use powers. They are irrelevant! You just may not exclude ##r_i=r_j,## but we do not need the irreducible factors to be different. If all are equal, so what? Duplicates are allowed, and it simplifies the argument a lot if we don't have to bother with powers.
elias001 said:
I did not comment on your example of qudratic integers because Hungerford covers that topic in the following section and in the topics on fields.
That is a bit surprising since this topic has nothing to do with fields. ##\mathbb{Z}\left[\sqrt{-5}\right]## is the standard example of a ring that isn't a unique factorization domain. We have been talking about extensions or quotient rings ##\mathbb{Z}\left[\sqrt{-5}\right]\cong \mathbb{Z}[x]/\bigl\langle x^2+5 \bigr\rangle ## before.
elias001 said:
In the section where the question is from, there were no mentions to qudaratic integers. Also when you mentioned about ##k=0##, it was confusing for me since I thought the ##r_k##s are allow to have index from zero onwards. Actually, the entire proof was confusing and complicated, since hungerford should have given a direct proof having to do with prime factorization and use the equivalent definition of gcd without making reference to unit elements.
##k=0## is only the extreme instance of logic. We have the conventions
$$
\sum_{i\in\emptyset} a_i=0\quad\text{ and }\quad \prod_{i\in\emptyset} a_i=1.
$$
This makes the product ##a=r_1r_2\cdots r_0## empty, since the index ##0## at the end signals that we didn't even start to count, so ##a=\prod_{i\in\emptyset} r_i=1## or a unit if you like. The rest of Hungerford's argument is then also empty. No ##r_i## means no case. It is trivially true since empty statements are true, or as I like to say: "The members of the empty set have purple eyes."
 
  • #23
@fresh_42 the proof I rewrote the proof from is adapted from lemma 2.61 in the following screenshots, second and third pages, In it, the author made use of lemma 2.58. In Hubgerford, there are the corresponding theorems to lemma 2.58 and lemma 2.59. As you can see, lemma 2.61, the author just made use of prime factorization, and he only used the corresponding assumption that ##a\mid bc## and the factors within all three integers ##a,b,c##. If my effort in rewriting caused any lack of clarity, that is solely my fault. Also when gcd(a,b)=1, then the prime factorization of a, b, with their respective prime factors ##p_i^{e_i}, p_i^{f_i}##, then min(##e_i, f_i##)=0, which is what i tried to include. If you have trouble reading the pages, let me know. i will try to make it more clear or type out the relevant portion. I also attached a pdf of the three pages.

In my earlier replies, not sure if i changed or deleted it. I said that if we have ##a\mid bc## and gcd(a,b)=1, then the factors of ##a## don't appear in ##b## and so must appear in ##c##, hence ##a\ mid c##. I mean i could ask one of the LLMs to wrote out Lemma 2.61 in mathematical notations, but I want to try it out myself first i mean, I only do that unless I find the notations confusing or unclear, or just plain unintutitive to use in the sense of the precise notation doesn't really convey what I think it conveys in plain English.

(CMS Treatises in Mathematics) Steven H. Weintraub - Factorization_ Unique and Otherwise-A. K...webp
(CMS Treatises in Mathematics) Steven H. Weintraub - Factorization_ Unique and Otherwise-A. K...webp
(CMS Treatises in Mathematics) Steven H. Weintraub - Factorization_ Unique and Otherwise-A. K...webp
 

Attachments

Last edited:
  • #24
@fresh_42 Here is the typed up version of what is in the screenshots in post 23,

##\textbf{Lemma 2.58:}## Let ##R## be a UFD, and let ##\alpha, \beta## be non zero elements of ##R##. Then ##\alpha## divides ##\beta## if and only if

(1) every prime ##p## that divides ##\alpha## also divides ##\beta,## and

(2) For every such prime ##p,## if ##p^e## is the highest power of ##p## dividing ##\alpha## and if ##p^f## is the highest power of ##p## dividing ##\beta##, then ##f\geq e.##

##\textbf{Lemma 2.61:}## Let ##R## be a UFD, and let ##\alpha## be a non zero elements of ##R.## Let ##\beta_1## and ##\beta_2## be elements of ##R## and suppose that ##\alpha## divides ##\beta_1\beta_2.## If ##\alpha## and ##\beta_1## are relatively prime, then ##\alpha## divides ##\beta_2.##

##\textit{Proof:}## Since ##\alpha## and ##\beta_1## are relatively prime, they have no common factors. Thus we have prime factorizations ##\alpha=p_1^{e_1}\cdots p_k^{e_k},\beta_1=q_1^{g_1}\cdots q_l^{g_l}.## Now we are assuming that ##\alpha## divides ##\beta_1\beta_2##, so by ##\textbf{Lemma 2.58}## we see that the prime factorization of ##\beta_1\beta_2## must include ##p_1^{f_1}\cdots p_k^{f_k}## with ##f_i\geq e_i,## for each ##i##. But the prime factorization of ##\beta_1\beta_2## is the product of the prime factorization of ##\beta_1## and the prime factorization of ##\beta_2.## Since ##p_1^{f_1}\cdots p_k^{f_k}## does not appear in the prime factorization of ##\beta_1##, it must appear in the prime factorization of ##\beta_2##, and hence ##\alpha## divides ##\beta_2.##

When trying to express al the english sentence using mathematical notations, I was trying to make sure i got all the technical details correct.
 
Back
Top