Proof About Greatest Common Divisors

  • Thread starter daneault23
  • Start date
  • #1
32
0

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.

Homework Statement





Homework Equations





The Attempt at a Solution

 

Answers and Replies

  • #2
954
117
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?
 
  • #3
HallsofIvy
Science Advisor
Homework Helper
41,847
965
Have you considered the cases n= a and n= b?
 
  • #4
32
0
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.
 
  • #5
32
0
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
verty
Homework Helper
2,182
198
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?
 
  • #7
32
0
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
verty
Homework Helper
2,182
198
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
32
0
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
 

Related Threads on Proof About Greatest Common Divisors

Replies
7
Views
2K
  • Last Post
Replies
5
Views
1K
Replies
2
Views
1K
Replies
11
Views
4K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
895
  • Last Post
Replies
24
Views
3K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
19
Views
5K
Top