# GCD and Relative Primes

1. Jul 19, 2011

### Shackleford

I'm not exactly sure how to prove or disprove this statement. Just by looking at the c, I'd say it's not true, but I'm not sure how to show it either way.

If (a,b) = 1 and (a,c) = 1, then (ac,b) = 1.

http://i111.photobucket.com/albums/n149/camarolt4z28/IMG_20110719_192439-1.jpg?t=1311127377 [Broken]

Last edited by a moderator: May 5, 2017
2. Jul 19, 2011

### Dick

If you think it's not true, and it's not. Then just give a counterexample.

Last edited by a moderator: May 5, 2017
3. Jul 19, 2011

### Shackleford

I thought about that. However, how do I quickly find two relative primes? Just pick them? Let me try 3 and 7. Their only common divisor is 1.

4. Jul 19, 2011

### Dick

Sure, try them. (3,7)=1. So let a=3 and b=7. Now pick c.

5. Jul 19, 2011

### SammyS

Staff Emeritus
Consider some of the possible prime factorizations of a, b, and c which are consistent with (a,b) = 1 and (a,c) = 1, and not consistent with (ac,b) = 1, if that's possible.

If (ac,b) > 1 , and (a,b) = 1 , then what's true about (b,c) ?

6. Jul 19, 2011

### Shackleford

In trying to work a counterexample, it would appear that b = c, from your two given statements.

7. Jul 19, 2011

### SammyS

Staff Emeritus
Not necessarily.

8. Jul 19, 2011

### Dick

b=c works, if they are relatively prime to a. That's enough to disprove the statement. But as SammyS said they don't have to be equal to provide a counterexample.

9. Jul 19, 2011

### Shackleford

(3,7) = 1

1 = am + bn
1 = (3)(-2) + (7)(1)

a = 3
b = 7
m = -2
n = 1

(3,5) = 1

a = 3
c = 5
1 = am + cn
1 = (3)(-2) + (5)(1) = -1

Of course, that's not true. Do the m and n have to be the same?

10. Jul 19, 2011

### Dick

No, not at all. (a,b)=1 if am+bn=1 for SOME integers m and n. (a,c)=1 if ak+bl=1 for SOME integers k and l. Of course, m and n don't have to be the same as k and l. I'd suggest you just concentrate on creating a counterexample for now. Use the b=c case, then try and find one where b is not equal to c.

11. Jul 19, 2011

### Shackleford

Well, that's the first important point I wasn't sure about.

If I use (3,7) and (3,7), with

m = -2
n = 1

k = 5
l = -2

1 = acp + bq
1 = (3)(7)(p) + (7)(q)

Of course, that will never work because the two terms are multiples of 7, right?

12. Jul 19, 2011

### Dick

Right. But you are maybe getting carried away with how important the am+bn=1 condition is. You don't need it for this proof. gcd(3,7)=1 because they have no common divisor except 1, since they are both different primes. You know this before you even find the m and n. If you put a=3, b=7 and c=7 then gcd(a,b)=1 gcd(a,c)=1 and gcd(ac,b)=gcd(21,7). That's not 1, is it? That's really all you need to do.

13. Jul 19, 2011

### Shackleford

Oh. Sometimes I get bogged by the thought of needing to use the general cases.

I wrote down (7,9) and (7,3). That should be another counterexample.

(21,9) = 3

14. Jul 19, 2011

### Dick

That also works. No need for the relation 1=am+bn, right?

15. Jul 19, 2011

### Shackleford

Not this time. Sometimes, you need it, though.

I have one more homework problem.

If b is greater than 0 and a = bq + r, prove that (a,b) = (b,r).

I'll give it a shot in a few minutes.

16. Jul 19, 2011

### Staff: Mentor

It might be helpful to write down a few examples using actual numbers, to help you better understand the symbols. The examples can't be used as a proof, but they can be useful for getting your head around the problem.

For example, 35 = 5*6 + 5. Here (a, b) = (35, 5) = 5, and (b, r) = (5, 5) = 5.
For another, 13 = 2*5 + 3. Here (a, b) = (13, 2) = 1, and (b, r) = (2, 3) = 1.