Proof About Greatest Common Divisors

  • Thread starter daneault23
  • Start date
  • Tags
    Proof
In summary, the assertion that there exist distinct positive integers a and b such that for all natural numbers n we have (a,n)=1 or (b,n)=1 is false. This can be disproven by considering the cases where a and b are not equal to 1, and finding a counterexample where (a,n) and (b,n) are not equal to 1 for some natural number n. Additionally, the assertion is only true when either a or b (not both) equals 1. The book may have been misleading in asking to disprove the assertion when in reality it is true.
  • #1
daneault23
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.
 
Physics news on Phys.org
  • #2
daneault23 said:
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
Have you considered the cases n= a and n= b?
 
  • #4
HallsofIvy said:
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
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
daneault23 said:
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
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
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
verty said:
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
 

What is a greatest common divisor (GCD)?

A greatest common divisor (GCD) is the largest positive integer that divides two or more integers without a remainder. It is also known as the greatest common factor (GCF) or highest common factor (HCF).

How do you find the GCD of two numbers?

The most common method to find the GCD of two numbers is by using the Euclidean algorithm. This involves dividing the larger number by the smaller number, and then using the remainder as the new divisor in the next step. This process is repeated until the remainder is 0, and the last non-zero remainder is the GCD.

What is the proof for the existence of a GCD?

The proof for the existence of a GCD is based on the fundamental theorem of arithmetic, which states that every integer can be expressed as a unique product of prime numbers. This allows us to find the common factors between two numbers and determine the largest one, which is the GCD.

Can the GCD be negative?

No, the GCD is always a positive integer. This is because a negative number can never be a factor of a positive number. However, the GCD of two negative numbers is the same as the GCD of their absolute values.

What is the relationship between GCD and LCM?

The GCD and the least common multiple (LCM) are related by the following formula: GCD(a,b) * LCM(a,b) = a * b. This means that if we know the GCD and one of the numbers, we can easily find the LCM, and vice versa. Additionally, the GCD and LCM are always smaller and larger than the numbers being compared, respectively.

Similar threads

  • Calculus and Beyond Homework Help
Replies
2
Views
902
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
439
  • Calculus and Beyond Homework Help
Replies
5
Views
978
  • Calculus and Beyond Homework Help
Replies
1
Views
522
  • Calculus and Beyond Homework Help
Replies
1
Views
434
  • Calculus and Beyond Homework Help
Replies
4
Views
853
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
482
  • Calculus and Beyond Homework Help
Replies
3
Views
451
Back
Top