# Prove $\gcd(n, n + 1) = 1$ for any $n$

Let $n \in \mathbb Z$ be even. Then $n + 1$ is odd. So, $2$ doesn't divide $n + 1$. Thus there's no even number for which $\gcd(n, n+1)$ is not $1$. I am not sure how to show it for odd numbers. Is there a better way to prove the statement?

• Note that an even number can still have a factor in common with an odd number, e.g., $6$ and $9$. In other words, showing that $2$ doesn't divide $n+1$ isn't a valid argument that $n$ and $n+1$ have no common factors. – Théophile Aug 8 '15 at 2:27

Let $a$ and $b$ be integers.

Any integer that divides both $a$ and $b$ must also divide their difference (can you see why this is?).

• Let $n = ak$ and $n + 1 = aj$. Then $n - n - 1 = -1 = a(k - j)$. But $a$ doesn't divide $-1$? – user259324 Aug 8 '15 at 2:35
• You're going at it a little backwards. We want find a divisor $d$ of the difference $a-b$ first, and then use the fact I posted to conclude that $d$ must also divide $a$ and $b$. (For your particular problem we can set $a = n+1$ and $b = n$.) – 727 Aug 8 '15 at 2:45
• Also just an FYI, the fact I posted is the basis of the Euclidean Algorithm, which is an ancient, simple, and efficient method to compute the GCD of two integers. en.wikipedia.org/wiki/Euclidean_algorithm – 727 Aug 8 '15 at 2:48
• $1 = aj$ for some $j$. So $a$ can't be anything other than $1$ which divides both $n, n + 1$. Like that? – user259324 Aug 8 '15 at 2:49
• $d|a, d|b \to d|(a - b)$. Since $a - b = n + 1 - n = 1$, $d|1$. Then $d$ must be $1$? – user259324 Aug 8 '15 at 3:03

Suppose $\gcd(n,n+1)=d>1$ for some $n\in\mathbb{N}$. Then by Bezout's identity, there are $a,b\in\mathbb{Z}$ such that $$an+b(n+1)=d\Rightarrow (a+b)n+b=d$$.....

Edit: This is far too complicated for no reason. The real solution is the one given: $d|n$ and $d|n+1$ implies $d|(n+1)-n\Rightarrow d|1$ so $d=\pm 1$.

• $d$ is congruent to $0$ mod what? – miniparser Aug 8 '15 at 4:57
• Yes that was a mistake. I don't know where my head's been today. – Moya Aug 8 '15 at 5:06

I would personally just say the following. Say $n$ has a divisor $q$, for which $\frac{n}{q} = p, p \in \mathbb{Z}$. Then if we divide $n+1$ by $q$ we obtain $\frac{n+1}{q} = p + \frac{1}{q}$, thus for all $q \ne 1$ (since the $\gcd(1,q)=1$), $n+1$ will not be divisible by $q$.

Therefore $\gcd(n, n+1) =1$.

Suppose $gcd(n,n+1)=d >0$ $$\to \left.\begin{matrix} d|n\\ d|n+1 \end{matrix}\right\}\Rightarrow d|(n+1)-(n)\Rightarrow d|1\\\frac{1}{d} \in \mathbb{Z}\Rightarrow d=\pm1 \overset{d>0}{\rightarrow} d=1$$

multiples of $n+1$:$\space n+1,2n+2,3n+3,...,(n-1)(n+1)=(n-1)n+(n-1),n(n+1),n(n+2),...$

least common multiple with $n$ must be $n(n+1)$ otherwise $n$ cannot divide it.

$lcm(n,n+1)=n(n+1)$; $\space gcd(a,b)={{ab}\over{lcm(a,b)}},\space a,b\in \mathbb{Z}; \space\space\space gcd(n,n+1)={{n(n+1)}\over{n(n+1)}}=1$

Theorem: For any integers $x,a,b$, $(a,b) = (a,b+ax)$.
Then, for the particular case that $a=n$ and $b=n+1$, choose $x=-1$ to get:
$$(n,n+1)=(n,1)=1.$$