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

4 Answers 4

15
$\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$ Commented 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$ Commented Dec 6, 2016 at 15:34
4
$\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$
1
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .