Proof About Greatest Common Divisors

[daneault23]

Homework Statement

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."

Homework 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.

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.

 

[Fightfish]

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.

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

 

[HallsofIvy]

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

 

[daneault23]

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

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.

 

[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

 

[verty]

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

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

 

[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.

 

[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.

 

[daneault23]

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.

Tricky books these days lol