# Greatest common divisor proof

1. Apr 20, 2017

### knockout_artist

Hi,
==================================================
question :Prove:
If(a,b)= l and if ( "(a,b)=1" mean greatest common divisor of integers and b is 1 )
c|a (c divides a)
and
d|b (d divides b )
then
(c,d)= 1. ( "(c,d)=1" mean greatest common divisor of integers and b is 1 ) <-- this need to be proved.
========================================
(Is that following a good proof ?)
========================================
Then there are 2 sets A and B.
divisors of a ∈ A <-- do this need be proved too?
divisors of b ∈ B

A ∩ B = 1

since
c ⊂ A
d ⊂ B

c ∩ b = 1 which is what we are looking for.
===========================================

Thank you.

2. Apr 20, 2017

### Math_QED

You are correct when you say you can consider the sets $A,B$ containing the divisors of $a$, resp. $b$. You don't need to prove that. You know that such a set always exists.

However, when you write $A \cap B = 1$, this is bad notation. You either write $A \cap B = \{1\}$ or $|A \cap B | = 1$. I don't know what exactly you mean by this, but either way you must explain why this is true.

You also wrote $c \cap d = 1$ which doesn't make sense as $c,d$ are elements and not sets.

3. Apr 20, 2017

### knockout_artist

Then there are 2 sets A and B.
divisors of a ∈ A
divisors of b ∈ B

A ∩ B = {1} <-- this is just restating the fact that 'a' and 'b' has only gcd which is "1" I am trying to say the divisor set A and divisor set be B has only one common element with is "1"

c ∈ A <--because 'c' divide 'a' that means its part of 'A' set of all the divisor of a
d ∈ B < -- same reason as above

if
C ={ all the divisor of c }
D ={ all the divisor of d }

C ⊂ A because a is one of the multiples of c. is this need to proved ?
D ⊂ B same reason as above.

we know A ∩ B = {1}
since C ⊂ A and D ⊂ B

C ∩ D ={1}
Which means the only common divisor of c and d is '1'

4. Apr 20, 2017

### Staff: Mentor

You can prove it, but I guess your course did that earlier already - it is one of the basic features of divisibility.

5. Apr 20, 2017

### knockout_artist

So I have proved it properly ?

Thank you.

6. Apr 20, 2017

### Staff: Mentor

I'm not the person grading your homework. I think it is okay, but I cannot know if the person grading your homework wants to see more steps in between.

I moved the thread to our homework section, by the way.

7. Apr 20, 2017

### knockout_artist

Its not home work, I am judging my self before taking a analysis course. That will be my first ever math course.
This problem is from the book I will be using.
That is why I was keen to know.
Thank you.

8. Apr 20, 2017

### mathwonk

i would just show directly that if x divides both c and d, then x also divides both a and b, hence x = ±1.

9. Apr 20, 2017

### UsableThought

Curious - what's the name/author of the book?

10. Apr 20, 2017

### knockout_artist

Introduction to Analytic Number Theory
by Tom M. Apostol
https://www.amazon.com/Introduction...sr=8-1-fkmr0&keywords=number+analysis+apostol

BTW, what I posted is not how this book deals with things.
I once read a book, a few chapters, "introduction to topology".
So I remembered some set language.

In t Apostol's book I have read only few pages, I tried this problem from Apostol's book because It looked like it could have been done, before reading stuff from the book.

Last edited by a moderator: May 8, 2017