# Prove that for any integer $k \ne 0$, $\gcd(k, k+1) = 1$

I'm learning to do proofs, and I'm a bit stuck on this one. The question asks to prove for any positive integer $k \ne 0$, $\gcd(k, k+1) = 1$.

First I tried: $\gcd(k,k+1) = 1 = kx + (k+1)y$ : But I couldn't get anywhere.

Then I tried assuming that $\gcd(k,k+1) \ne 1$ , therefore $k$ and $k+1$ are not relatively prime, i.e. they have a common divisor $d$ s.t. $d \mid k$ and $d \mid k+1$ $\implies$ $d \mid 2k + 1$

Actually, it feels obvious that two integers next to each other, $k$ and $k+1$, could not have a common divisor. I don't know, any help would be greatly appreciated.

• Start by assuming that there is a common factor $d$. Then $k=ad$ and $k+1 = bd$ for some integers $a$ and $b$. Now subtract the equations ... or maybe easier: if $d$ divides $k$ and $k+1$, then it divides their difference. Nov 7, 2012 at 3:44
• @OldJohn you said "if $d$ divides $k$ and $k+1$, then it divides their difference" , I thought it was if $a|b$ and $a|c$ then $a|b+c$? Maybe I'm wrong
– atb
Nov 7, 2012 at 3:57
• Yes, $a$ does divide $b+c$, but it also must divide $b-c$, for very similar reasons. Try writing out the details of the first part of my suggestion. Nov 7, 2012 at 4:00

Let $d$ be the $gcd(k, k+1)$ then $k=rd$, $k+1=sd$, so $1=(s-r)d$, so $d |1$.

Hint $\$ Both $\rm\:1+k\:$ and $\rm\:k\:$ are multiples of $\rm\:c = gcd(k,1+k),\:$ and the set of multiples of any integer $\rm\:c\:$ enjoy a special structure: they're closed under subtraction, since $\rm\:ac\! -\! bc = (a\!-\!b)c$.

Said $\rm\: mod\ c\!:\ 1\!+\!k\equiv 0,\,\ k\equiv 0\:\Rightarrow\:1\equiv 0,\:$ i.e. $\rm\:c\:|\:1$

Old John's answer in the comments is better than this, but I'm hoping to provide some intuition...

Look at $k!$ instead of $k$:

• 2 divides $k!$, thus it cannot divide $k!+1$. (2 divides every other integer)
• 3 divides $k!$, thus it cannot divide $k!+1$. (3 divides every third integer)

etc, up to and including "$k$ divides $k!$...".

Now look back at $k$: Well, if $2$ divides $k$, then it cannot divide $k+1$ (2 divides every other integer). If $3$ divides $k$, then it cannot divide $k+1$. Etc, until you reach "does $k$ divide $k$?".

Let $$d=\gcd(k.k+1)$$, then $$d\mid k+1-k=1$$. So $$d=\pm 1$$.