Proving GCD of (n, n+1) is 1

• smithg86
In summary, the question is whether the greatest common divisor of two successive integers (n, n+1) is always equal to 1, or if they are always coprime. Euclid's Algorithm may be used to prove this, as it is pretty obvious that if m divides n, then n+1 is not divisible by m unless m=1. This property can also be used to prove that there are infinitely many primes. There can be multiple replies to this question due to its trivial nature and the fact that more people may know the answer. If constructing a formal proof, it may take around 50 lines using Peano's axioms and "existential introduction/elimination."

smithg86

is the gcd of two successive integers (n, n+1) always equal to 1? i.e., are two successive integers always coprime? it seems like this is the case, but how would you prove this? (this came up in my logic/proof class, but the professor wouldn't or couldn't prove it - this isn't a HW question.)

yes, i think so.

but how would you prove it to be true?

try Euclid's Algorithm...

Isn't it pretty obvious? suppose m divides n, then n=jm for some j. But then n+1=jm+1 which is not divisible by m (unless m=1). Thus n and n+1 are coprime.

It's neat that you brought that up.

I saw a proof using this property to show that there are infinitely many primes.

how can there be 5 replies to this question?

the more trivial the inquiry the more replies.

If this comes from a logic class, then I'm assuming you need to construct a formal proof starting from Peano's axioms, with the "existential introduction/elimination", etc. This proposition should take about 50 lines to prove, if you're lucky.

mathwonk said:
the more trivial the inquiry the more replies.

Duh! Because more people know the answer.

1. What is the GCD of (n, n+1)?

The GCD of (n, n+1) is 1.

2. How do you prove that the GCD of (n, n+1) is 1?

There are several methods to prove the GCD of (n, n+1) is 1. One method is to use the Euclidean algorithm, which involves repeatedly dividing the larger number by the smaller number and taking the remainder until the remainder is 0. The last non-zero remainder will be the GCD. In the case of (n, n+1), the remainder will always be 1, proving that the GCD is 1.

3. What is the significance of proving the GCD of (n, n+1) is 1?

Proving the GCD of (n, n+1) is 1 is significant because it shows that n and n+1 are relatively prime, meaning they have no common factors other than 1. This has applications in number theory and cryptography.

4. Can the GCD of (n, n+1) be any other number besides 1?

No, the GCD of (n, n+1) can only be 1. This is because n and n+1 are consecutive integers, and the only common factor they can have is 1.

5. How does proving the GCD of (n, n+1) is 1 relate to other mathematical concepts?

Proving the GCD of (n, n+1) is 1 is related to the concept of coprime numbers, which are numbers that have a GCD of 1. It is also related to the fundamental theorem of arithmetic, which states that every positive integer can be uniquely expressed as a product of prime numbers. In the case of (n, n+1), n and n+1 cannot share any prime factors other than 1, further supporting the fact that their GCD is 1.