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.

Question

dape · Answer

What is the condition for a and b being relatively prime?

dape · Answer

Do you know it?

kinggeorge · Answer

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 ?

dape · Answer

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 · Answer

I like that solution more. Mine was a bit more analytic.

anonymous · Answer

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 · Answer

Hmm, I like this solution the best, clear and concise.

kinggeorge · Answer

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 · Answer

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 · Answer

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 · Answer

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 · Answer

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 · Answer

Ah... That's nice :)

kinggeorge · Answer

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 · Answer

no it's fine! i like the discussion!! I just wish i understood it :/

anonymous · Answer

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 · Answer

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 · Answer

I'm in number theory right now along with modern algebra

kinggeorge · Answer

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 · Answer

well thank you!