Greatest common divisor

In summary, if (a,c)=1 and (b,c)=1, then (ab,c)=1 can be proven using the theorem that (m,n)=1 if and only if mx+ny=1 for some integers x, y. By multiplying the given equations and rearranging the resulting equation, it can be shown that (ab,c)=1.
  • #1
j9mom
31
0

Homework Statement


if (a,c)=1 and (b,c)=1 prove that (ab,c)=1


Homework Equations



I know that (a,c)=1 says that au+cv=1 and bs+ct=1 prove abq+cr=1


The Attempt at a Solution



I set au+cv=bs+ct now I don't know what to do
 
Physics news on Phys.org
  • #2
do you know the theorem that if d|ab, then d|a or d|b?
 
  • #3
Yes I did learn that, but how do I use that?
 
  • #4
So, I should prove by contradiction. If some other number divides ab then it must divide a or b but it does not divide either so it (ab,c) must = 1
 
  • #5
aPhilosopher said:
do you know the theorem that if d|ab, then d|a or d|b?

That's false. 6|(3*4) but 6 doesn't divide 3 or 4. You had better say the word 'prime' at some point.
 
  • #6
So if I let x equal a prime number greater than 1 I can prove by contradiction that it either divides a or b and since it doesn't there is the contradiction
 
  • #7
Wait... x is a prime number greater than 1 that divides c
 
  • #8
Dick said:
That's false. 6|(3*4) but 6 doesn't divide 3 or 4. You had better say the word 'prime' at some point.

You're right. Thanks for the correction
 
  • #9
Thanks
 
  • #10
j9mom said:
Wait... x is a prime number greater than 1 that divides c

Slow down. Can you state your reasoning in complete sentences? (a,c)=1 means a and c have no common prime divisors. Now continue.
 
  • #11
j9mom said:
Wait... x is a prime number greater than 1 that divides c

you don't need to specify 'greater than 1' because 1 isn't prime.


so if d|(ab, c), then there exists some prime p such that p|ab.
 
  • #12
Let x = a prime number greater than 1 that divides c. Assume (ab,c)=x. Based on the theorem we know that x|a or x|b. However, based on the given that (a,c)=1 and (b,c)=1, we know that x does not divide a and x does not divide b. Hence there is a contradiction and x cannot be a prime number greater than 1. Since we know there is no prime number less than 1, x must equal 1
 
  • #13
that doesn't look quite right. strike the first sentence and let p|x where p is prime. Go from there. It's mostly good though. The problem is that (ab, c) might not be prime.
 
  • #14
Did not see your next post, but that is right, so I can simplify by answer to x cannot be a prime number that divides c, so x must equal 1
 
  • #15
A philospher: my x equals a prime number that divides c.
 
  • #16
j9mom said:
Let x = a prime number greater than 1 that divides c. Assume (ab,c)=x. Based on the theorem we know that x|a or x|b. However, based on the given that (a,c)=1 and (b,c)=1, we know that x does not divide a and x does not divide b. Hence there is a contradiction and x cannot be a prime number greater than 1. Since we know there is no prime number less than 1, x must equal 1

Why are you rushing this? Think about it. You can't assume BOTH x|c AND (ab,c)=x without justifying it. Look, start from this: If (ab,c) is not 1, then let x be a prime that divides (ab,c). Go from there. SLOWLY.
 
  • #17
Ok, but can I leave x as a prime number that divides c but is simply a common divisor not necessarily the greatest common divisor. Then I still can say it does not divide a or b so must be 1
 
  • #18
Ok let me start again.
 
  • #19
Dick said:
You can't assume BOTH x|c AND (ab,c)=x without justifying it.

Yes you can. By definition. What can't be assumed is that (ab, c)=x and that x is prime.
 
  • #20
Ok: Let x be a prime number such that divides (ab,c). Now this means that x must divide c and must divide either a or b. Now I can say here is the contradiction, we know x does not divide a or b so x cannot divide (ab,c). Therefore x must equal 1
 
  • #21
that's the idea. looks good.
 
  • #22
except your prof might get mad about you claiming that x = 1 since you've already assumed that it's prime. Most people exclude 1 from the list of primes.
 
  • #23
aPhilosopher said:
Yes you can. By definition. What can't be assumed is that (ab, c)=x and that x is prime.

On that, you are right. Oh, I see you've both already finished. Sorry to be so slow.
 
  • #24
So I will just say x cannot divide (ab,c) Simce x is an arbitrary prime number then it holds for all prime numbers. Therefore (ab,c)=1
 
  • #25
Hope I'm not sidetracking you too much (ignore me if I am), but I wanted to say here's an idea for a very slick proof using your original idea.

You originally used the theorem that (m,n)=d implies mx+ny=d for some integers x, y. Even though the converse is not true in general, it is true that for the special case d=1, this is an "if and only if."

That is, (m,n)=1 if and only if mx+ny=1 for some integers x, y. If you have this theorem, then you can give a nice solution to your problem.

So, if (a,c)=1 and (b,c)=1 prove that (ab,c)=1.

You know au+cv=1 and bs+ct=1 for some integers u, v, s, and t.

Now multiply those two equations and put into the form ab(some integer) + c(big mess)=1, where big mess is an integer.
 

What is a greatest common divisor?

A greatest common divisor, also known as a greatest common factor, is the largest positive number that divides two or more numbers without leaving a remainder.

How do you find the greatest common divisor?

The easiest method to find the greatest common divisor is to list all the factors of each number and then identify the largest number that appears in each list. Another method is to use the Euclidean algorithm, which involves dividing the larger number by the smaller number and repeating the process until the remainder is 0.

What is the greatest common divisor used for?

The greatest common divisor is used in many mathematical concepts, such as simplifying fractions, finding equivalent fractions, and solving equations involving fractions. It is also used in computer science, particularly in finding the smallest common multiple and reducing fractions in programming.

Can the greatest common divisor be larger than the smaller number?

No, the greatest common divisor must always be smaller than or equal to the smaller number. This is because any number that divides both numbers must also divide the smaller number, making it the largest possible common factor.

What is the difference between greatest common divisor and least common multiple?

The greatest common divisor is the largest number that divides two or more numbers without leaving a remainder, while the least common multiple is the smallest number that is a multiple of two or more numbers. The two concepts are related, as the greatest common divisor can be used to find the least common multiple.

Similar threads

  • Calculus and Beyond Homework Help
Replies
2
Views
923
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
2K
  • Calculus and Beyond Homework Help
Replies
18
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
11
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
515
  • Calculus and Beyond Homework Help
Replies
3
Views
999
  • Calculus and Beyond Homework Help
Replies
2
Views
154
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
Back
Top