Question About Greatest Common Divisors (GCD)

[bZNyQ7C2]

I recently learned a simple theorem about GCDs. It's intuitive and quick to prove. My question is whether I can generalize it in a way I will explain below. I did look on the search engines, but I couldn't find the right way to put the question.

Here's the theorem: If \(\displaystyle a|bc\) and \(\displaystyle (a,b) = 1\), then \(\displaystyle a|c\). Intuitively, if a and b have no factors in common, but a and bc do, then the common factor must be between a and c. That's not hard. The mathy proof uses Bezout's identity, which says that for some integers u and v, \(\displaystyle \left( {a,b} \right) = 1 \to au + bv = 1\). We multiply this by c to get \(\displaystyle acu + bcv = c\). But \(\displaystyle a|bc\), so that for some r we have \(\displaystyle bc = ar\). Therefore, \(\displaystyle c = acu + bcv + \left( {ar} \right)v = a\left( {cu + rv} \right) \to a|c\).

That's just a little review.

Here's my question. Still assuming that \(\displaystyle (a,b) = 1\), and given that \(\displaystyle am = bc\) where m is some integer, is it still true that \(\displaystyle a|c\)? Does that extra factor of m prevent a from dividing bc?

I cannot prove this, but I can't find a counterexample either. Suppose a = 3 and b = 7. Then I must find m and c such that \(\displaystyle 3m = 7c\). I can find many such pairs, but none where 3 does not divide c.

No, this is not for HW or any exam. I'm not taking a math class right now. But I'd really appreciate any help.

 

[Steven G]

You mean to say can that extra m prevent a from dividing bc.

If am=bc, then m = bc/a. Since a | b, then a | c

 

[Dr.Peterson]

Still assuming that \(\displaystyle (a,b) = 1\), and given that \(\displaystyle am = bc\) where m is some integer, is it still true that \(\displaystyle a|c\)? Does that extra factor of m prevent a from dividing bc?

Doesn't "\(\displaystyle am = bc\) where m is some integer" mean exactly the same thing as "[MATH]a|bc[/MATH]"? It just tells you the particular multiple of a that bc is.

 

[bZNyQ7C2]

@ Jomo ... I can't just divide out like that. I have no guarantee that bc/a is an integer.

@ Dr Peterson ... what I'm trying to prove is not that a|bc, but that a|c.

I'm concerned with the possibility that m|c. I can't find a case where that happens, but I can't prove that it never does.

 

[bZNyQ7C2]

I think I have it? If m|c then (m,c) is not equal to 1 ... then divide both sides by (m,c) ... this operation does not change the truth set. Then it must be that a|c. Does that sound right?

 

[Steven G]

@ Jomo ... I can't just divide out like that. I have no guarantee that bc/a is an integer.

@ Dr Peterson ... what I'm trying to prove is not that a|bc, but that a|c.

I'm concerned with the possibility that m|c. I can't find a case where that happens, but I can't prove that it never does.

m is an integer which equals bc/a. So you do have that bc/a is an integer.

Dr Peterson showed that a|bc. Combining that with (alb)=1 implies a|c

 

[Dr.Peterson]

@ Dr Peterson ... what I'm trying to prove is not that a|bc, but that a|c.

I'm concerned with the possibility that m|c. I can't find a case where that happens, but I can't prove that it never does.

You already have a theorem that if a|bc and (a,b) = 1, then a|c. So if you are given that am=bc where m is some integer, which implies that a|bc, then you can apply the theorem and conclude that a|c.

To put it another way, the known theorem

If a|bc and (a,b)=1, then a|c.​

and your desired theorem

Still assuming that (a,b)=1, and given that am=bc where m is some integer, then a|c.​

are the very same theorem! You are just stating the condition differently.

Am I missing something in what you've said? The fact that a|bc means that bc = ka for some integer k; knowing that that integer is m doesn't change anything, and in particular, it doesn't matter whether m|c.

 

[bZNyQ7C2]

I guess I was overthinking it. My thought was that if m|c then we already have a common factor, so it would be possible that a does not divide c. That was my thought.