# Consecutive Numbers are coprime

Can anyone help me in proving that two consecutive numbers are co-primes?

My approach:

Let two consecutive numbers are $n$ and $n+1$.

Assume they are not co-primes.

Then $\gcd(n,n+1)=x$, because it can not equal to $1$, $x$ is natural and $x\gt1$

So $x$ divides $n$ as well as $n+1$.

Then $x$ also divides $n+1-n$, by general understanding.

Hence $x$ divides $1$ or $x=1$.

But we have assumed $x\gt 1$.

So by contradiction $n$ & $n+1$ are co-prime.

Is it right or is there any better way to prove that two consecutive numbers are co-prime?

• Your argument is correct: indeed this is the shortest way to prove that two consecutive numbers are coprime. – Crostul Dec 6 '16 at 12:43
• Crostul is right, your argument is correct. – Vincent Dec 6 '16 at 12:45
• It's not really necessary to go for the contradiction. Your argument is almost a direct argument as it stands. Let $x=\mbox{gcd}(n,n+1).$ Then $x$ divides $n+1-n =1$. Therefore $x=1$. – B. Goddard Dec 6 '16 at 12:51
• Guys this question does not deserve downvotes. The OP has given his argument and shown his work. What do you expect from him now. +1 by me – Vidyanshu Mishra Dec 6 '16 at 13:41

Your proof looks good. Using the method of contradiction is not a bad idea here but you could have skipped that in your prove.

Given that $n$ and n+1 are two consecutive integers. Now suppose $gcd(n,n+1)=p$. Then p|n and $p|n+1$. Which implies that $p|n+1-n$ or $p|1$. There is no number which divides 1 except 1. So $p=1$ or you can say $gcd(n,n+1)=p=1$. Which implies $n$ and $n+1$ are coprime.

Notice that I have not used contradiction anywhere.

We  have $\,n\mid \color{#c00}{\overbrace{n\!+\!1}^{\large m}}-1.\$ Your (correct) proof easily generalizes as follows.

Generally $\,n\mid \,k\:\color{#c00}m-1\,\Rightarrow\, k\,m-j\,n = 1,\$ so $\,\ d\mid m,n\,\Rightarrow\, d\mid 1,\$ so $\ \gcd(m,n) = 1$

 i.e. $\ {\rm mod}\,\ n\!:\,\ m^{-1}\,$ exists $\,\Rightarrow\, \gcd(m,n) = 1.\,$ The converse is also true (Bezout gcd identity)

Remark $\$ We can also use (a single step of) the Euclidean algorithm

$$\gcd(km,n) = \gcd(jn\!+\!1,n) = \gcd(1,n) = 1\,\Rightarrow\, \gcd(m,n) = 1$$

Your proof is correct, but there is a simpler one, that doesn't work by contradiction and doesn't need greatest common divisors explicitly.

If a prime $p$ divides $n$ then dividing $n+1$ by $p$ leaves a remainder of $1$, so $p$ does not divide $n+1$. That means the factorizations of $n$ and $n+1$ have no prime in common, so $n$ and $n+1$ are relatively prime.

But ... this proof does use unique factorization, which is usually proved by thinking about greatest common divisors. So they are there, behind the scene.

• But the proof doesn't require prime factorizations. It can be presented in a universal way that works in any ring, e.g. see my answer. – Bill Dubuque Dec 6 '16 at 15:26
• @BillDubuque True, as I note. I've upvoted your answer. But mine may help a beginner think about the problem in a useful way. – Ethan Bolker Dec 6 '16 at 15:34

Here's a direct proof that preserves generality for all integers.

Let $$n \in \mathbb{Z}$$ such that $$n \notin [-2, 1]$$. Then suppose exists $$d \in \mathbb{Z}$$ such that $$\gcd{(n, n+1)} = d$$ and $$d \geq 1$$.

Then we know that $$d \mid n$$ and $$d \mid n+1$$, so we have $$p, q \in \mathbb{Z}$$ such that $$n = d\cdot p$$ and $$n+1 = d\cdot p$$.

We can then do the following: \begin{aligned} n&=d \cdot p \\ n+1&=d \cdot p + 1 \\ (d \cdot q) &=d \cdot p +1 && \text{since } n+1=d\cdot q \\ d\cdot q -d\cdot p &= 1 \\ d\cdot(q-p)&=1 \end{aligned} And therefore we have that $$d \mid 1$$. Since we're in $$\mathbb{Z}$$, we know $$1$$ is only divisible by $$\pm 1$$ (i.e. $$\forall x \in \mathbb{Z}$$, $$x \mid 1$$ is only true when $$x = \pm 1$$), therefore $$d = \pm 1$$ and since $$d \geq 1$$, $$d=1$$.

Finally, we have that $$\gcd{(n, n+1)} = d = 1$$

BOOM