Can you prove this statement for any values of a and b?

[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

 

[Dick]

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

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

 

[Shackleford]

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

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.

 

[Dick]

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.

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

 

[SammyS]

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) ?

 

[Shackleford]

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

 

[SammyS]

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

Not necessarily.

 

[Dick]

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

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.

 

[Shackleford]

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

(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?

 

[Dick]

(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?

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.

 

[Shackleford]

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.

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?

 

[Dick]

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?

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.

 

[Shackleford]

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.

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

 

[Dick]

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

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

 

[Shackleford]

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

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.

 

[Mark44]

I have one more homework problem.

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

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.