0
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Your argument is correct: indeed this is the shortest way to prove that two consecutive numbers are coprime. $\endgroup$ – Crostul Dec 6 '16 at 12:43
  • $\begingroup$ Crostul is right, your argument is correct. $\endgroup$ – Vincent Dec 6 '16 at 12:45
  • 1
    $\begingroup$ 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$. $\endgroup$ – B. Goddard Dec 6 '16 at 12:51
  • 2
    $\begingroup$ 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 $\endgroup$ – Vidyanshu Mishra Dec 6 '16 at 13:41
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$$

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Dec 6 '16 at 15:26
  • $\begingroup$ @BillDubuque True, as I note. I've upvoted your answer. But mine may help a beginner think about the problem in a useful way. $\endgroup$ – Ethan Bolker Dec 6 '16 at 15:34
0
$\begingroup$

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{equation}\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}\end{equation}$$ 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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.