# Proof About Greatest Common Divisors

1. May 17, 2013

### daneault23

1. The problem statement, all variables and given/known data
Disprove the following assertion: "There exist distinct positive integers a and b such that for all natural numbers n we have (a,n)=1 or (b,n)=1."

2. Relevant equations
(a,n)=1 and (b,n)=1 means greatest common divisor of a and n is 1, and of b and n is 1, respectively.

3. The attempt at a solution

This was my attempt at a solution. My teacher said it was wrong. Not really sure why.

Suppose there exists such a and b that are natural numbers where a isn't equal to b, a and b aren't equal to 1, where for all n that are natural numbers we have (a,n)=1 or (b,n)=1. Since a isn't equal to 1, we have that there's a prime divisor of a, i.e. p1=P. Since b isn't equal to 1, we have that there's a prime divisor of b, i.e. p2=P. Take n=p1*p2. Then p1 divides (a,n) where (a,n)>1, and p2 divides (b,n) where (b,n)>1 which is a contradiction.
1. The problem statement, all variables and given/known data

2. Relevant equations

3. The attempt at a solution

2. May 17, 2013

### Fightfish

If there is a prime divisor p1 of a, then wouldn't (a, p1) = p1?

3. May 17, 2013

### HallsofIvy

Staff Emeritus
Have you considered the cases n= a and n= b?

4. May 17, 2013

### daneault23

In those cases then (a,n) and b,n)=n wouldn' they? In our book it gives a hint that says "try finding the smallest such counterexample when a=2 and b=5. How does this suggest that we construct a counterexample in general?"

If a=2 and b=5, then (a,n)=1 if and only if n was an odd number (aka not a multiple of 2). If b=5, (b,n)=1 if and only if n wasn't divisible by 5. I'm just confused. I don't see how the hint helps me.

5. May 17, 2013

### daneault23

Aha I somewhat got it. Not sure how to actually prove it though. The assertion only works for a=b=1 because any number larger than 1 has a natural number associated with it which share a greatest common divisor. For example, let a=10. Then n could be 10 also and then (a,n,)=10

6. May 17, 2013

### verty

What is (b,n) when n = 10?

7. May 17, 2013

### daneault23

Nevermind guys I got it. The assertion is actually true when either a or b (not both) equals 1. The book tricked me by saying disprove the assertion when is reality the assertion is really true.

let's say a=1 then (a,n)=1 and it doesn't matter what positive integer b is (as long as its not 1), then the assertion holds.

8. May 17, 2013

### verty

Hmm, perhaps the question should have been,

Disprove: There exist integers 1 <= a < b such that, for every natural number n, (a,n) = 1 or (b,n) = 1.

But, daneault23, you answered the question as posed so good job.

9. May 17, 2013

### daneault23

Tricky books these days lol