9
$\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$
4
  • 3
    $\begingroup$ Your argument is correct: indeed this is the shortest way to prove that two consecutive numbers are coprime. $\endgroup$
    – Crostul
    Dec 6, 2016 at 12:43
  • $\begingroup$ Crostul is right, your argument is correct. $\endgroup$
    – Vincent
    Dec 6, 2016 at 12:45
  • 3
    $\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, 2016 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$ Dec 6, 2016 at 13:41

4 Answers 4

11
$\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$
4
$\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$
2
  • $\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$ Dec 6, 2016 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$ Dec 6, 2016 at 15:34
3
$\begingroup$

We $ $ have $\,n\mid \color{#c00}{\overbrace{n\!+\!1}^{\large m}}-1.\ $ Your (correct) proof easily generalizes widely 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\,$ (and conversely by Bezout, see here and here)

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

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

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