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

Question

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?

Answer 1

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?).

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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$

Answer 6

Related to 727 answer.

Theorem: For any integers $x,a,b$, $(a,b) = (a,b+ax)$.

(See the proof in theorem 1.9 in Niven's "An introduction to the theory of numbers".)

Then, for the particular case that $a=n$ and $b=n+1$, choose $x=-1$ to get:

$$ (n,n+1)=(n,1)=1. $$

Answer 7

Suppose $n$ $\in \mathbb{Z}$ $s.t$ $n = 1$. Obviosuly, $gcd(n,n+1) = gcd(1,n+1) = 1$. Now, suppose $n$ $\in$ $\mathbb{Z}$ $s.t$ $n$ $\gt$ $1$. By the division algorithm, we have $$\ (n+1) = nq + r$$ $$0 \le r \lt n$$In particular $$\ (n+1) = n(1) +1$$ which gives us $$ gcd(n+1,n) = gcd(n,1) =1$$ $\mathbb{Q.E.D}$

Answer 8

Take $n$ and $n-1$, if they have a common prime $p$ then from $n-(n-1)$ we can write $$n-(n-1)=p\cdot\left(\dfrac{n}{p}-\dfrac{n-1}{p}\right)=p\cdot\dfrac{n-n+1}{p}=p\cdot\dfrac{1}{p}$$ and that implies p divides 1, absurd, because p is prime. $quod$ $erat$ $demonstrandum$