anonymous
  • anonymous
Suppose a and b are integers that divide the integer c. If a and b are relatively prime, show that ab divides c. Show, by example, that if a and b are not relatively prime, then ab need not divide c.
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
katieb
  • katieb
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
dape
  • dape
What is the condition for a and b being relatively prime?
dape
  • dape
Do you know it?
KingGeorge
  • KingGeorge
We start with the assumption. Namely, \(c=a\cdot x\) and \(c=b\cdot y\) for some integers \(x,y\). Since \(a,b\) are coprime, we know that every prime divisor of \(c\) must be in either \(x\) or \(y\). So \(xy\ge c\). Now consider \(c^2=abxy\). Since \(xy\ge c\), we know that \(ab\le c\), and hence, \(ab\) must divide \(c\). Make sense @kdekle ?

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

dape
  • dape
You could also argue that since \(a, b\) divides \(c\) we have \(c=ax=by\), so \(a\) is a also a factor in \(by\). Since \(a, b\) are relatively prime, i.e. their greatest common divisor is 1, \(a\) must divide \(y\). In other words, there is an integer \(z\) such that \(az=y\), but if we put this into our first equation we get \(abz=by=c\), which means that \(ab\) divides \(c\).
KingGeorge
  • KingGeorge
I like that solution more. Mine was a bit more analytic.
anonymous
  • anonymous
Since my maths department always puts "You may not assume existence or uniqueness of prime decomposition without proof" on their papers, here's an alternative proof: Since a, b are coprime, by definition their highest common factor is 1. Then by Bezout's lemma (or whatever you call it) there are integers \(\lambda, \mu\) such that \[\lambda a + \mu b = 1. \tag{\(\star\)} \]Now a|c and b|c, so there are integers \(s,t\) such that \[c=sa,\ c=tb.\]Multiplying \((\star)\) by \(c\), we have \[c= \lambda ac + \mu bc = \lambda a(tb) + \mu b(sa) = ab(\lambda t + \mu s)\]so ab|c. The above proofs are way more intuitive though.
dape
  • dape
Hmm, I like this solution the best, clear and concise.
KingGeorge
  • KingGeorge
If you've done it in class, I think you should be allowed to use unique prime decomposition unless otherwise stated. Also, if I remember a particular homework problem from my most recent algebra class, Bezout's Lemma (or something very similar) is essentially equivalent to prime decomposition. I'll need to check on the details of that.
anonymous
  • anonymous
I kinda understand what ya'll are saying. I think @dape has one that I understand the best but thank you all for your help
anonymous
  • anonymous
Well, the thing with Bezout's lemma is that it can be proved without prime decomposition (we did it just be working the Euclidean algorithm backwards). My department always took a stance for some reason that prime decomposition (existence and uniqueness) needed to be proved if used in exams. I'm not sure why to be honest, nor do I think it's common practise. It's possibly because our proof of unique prime decomposition required the use of Bezout's Lemma, and it was sort of regarded as "cheating" to use it. I still think using prime decomposition is far more intuitive...
anonymous
  • anonymous
In fact, come to think of it, our proof of unique prime decomposition used this very thing we just proved! So it wouldn't have been allowed for us to go back and prove this with prime decomposition...
KingGeorge
  • KingGeorge
I've hunted it down in my textbook. Turns out it is not Bezout's Lemma I meant, but the Euclidean algorithm that guarantees prime decomposition. Without getting into the details, since the algorithm exists and works, \(\mathbb{Z}\) is a Euclidean domain, so it's a unique factorization domain, and we're done.
anonymous
  • anonymous
Ah... That's nice :)
KingGeorge
  • KingGeorge
I think I'll use that proof if I ever have to deal with not being able to assume unique decomposition :P Sorry for invading your question @kdekle :(
anonymous
  • anonymous
no it's fine! i like the discussion!! I just wish i understood it :/
anonymous
  • anonymous
Well, you could go and learn some number theory :-) Or perhaps one day you'll look back at this and see you understand all of it!
dape
  • dape
Basically, the theorem you posted can be used to later prove the fundamental theorem of arithmetic, which ensures unique decomposition of numbers into primes, a result that KingGeorge used in his proof. But as KingGeorge discussed you can start from other facts to show unique prime decomposition.
anonymous
  • anonymous
I'm in number theory right now along with modern algebra
KingGeorge
  • KingGeorge
Well, you'll probably understand almost everything said here soon enough. Euclidean Domains and Unique Factorization Domains come early on in Ring Theory (which is usually included in these algebra classes).
anonymous
  • anonymous
well thank you!

Looking for something else?

Not the answer you are looking for? Search for more explanations.