Shackleford said: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 said:If you think it's not true, and it's not. Then just give a counterexample.
Shackleford said: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.
Not necessarily.Shackleford said:In trying to work a counterexample, it would appear that b = c, from your two given statements.
Shackleford said:In trying to work a counterexample, it would appear that b = c, from your two given statements.
Dick said:Sure, try them. (3,7)=1. So let a=3 and b=7. Now pick c.
Shackleford said:(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 said: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 said: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 said: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 said: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 said:That also works. No need for the relation 1=am+bn, right?
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.Shackleford said:I have one more homework problem.
If b is greater than 0 and a = bq + r, prove that (a,b) = (b,r).
The Greatest Common Divisor (GCD) of two or more integers is the largest positive integer that divides each of the given integers without a remainder.
GCD can be calculated using the Euclidean algorithm, which involves dividing the larger number by the smaller number, then dividing the remainder by the previous divisor, and so on, until the remainder is zero. The last non-zero remainder is the GCD.
No, the GCD of two numbers can only be as large as the smaller number. For example, the GCD of 12 and 18 is 6, which is smaller than both numbers.
GCD is used in various mathematical concepts, such as fractions, simplifying algebraic expressions, and finding the lowest common denominator. It also has applications in computer science and cryptography.
Two numbers are said to be relatively prime if their GCD is 1. This means that the only positive integer that evenly divides both numbers is 1. For example, 9 and 16 are relatively prime since their GCD is 1, but 9 and 15 are not relatively prime since their GCD is 3.