Greatest common divisor

  • Thread starter j9mom
  • Start date
  • #1
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
 

Answers and Replies

  • #2
243
0
do you know the theorem that if d|ab, then d|a or d|b?
 
  • #3
31
0
Yes I did learn that, but how do I use that?
 
  • #4
31
0
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
Dick
Science Advisor
Homework Helper
26,263
619
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
31
0
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
31
0
Wait... x is a prime number greater than 1 that divides c
 
  • #8
243
0
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
31
0
Thanks
 
  • #10
Dick
Science Advisor
Homework Helper
26,263
619
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
243
0
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
31
0
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
243
0
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
31
0
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
31
0
A philospher: my x equals a prime number that divides c.
 
  • #16
Dick
Science Advisor
Homework Helper
26,263
619
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
31
0
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
31
0
Ok let me start again.
 
  • #19
243
0
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
31
0
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
243
0
that's the idea. looks good.
 
  • #22
243
0
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
Dick
Science Advisor
Homework Helper
26,263
619
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
31
0
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
392
0
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.
 

Related Threads on Greatest common divisor

  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
2
Views
892
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
19
Views
5K
Replies
11
Views
4K
Replies
0
Views
1K
  • Last Post
Replies
8
Views
1K
Replies
7
Views
2K
Top