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.

  • 2
    $\begingroup$ 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. $\endgroup$ – Old John Nov 7 '12 at 3:44
  • $\begingroup$ @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 $\endgroup$ – atb Nov 7 '12 at 3:57
  • 1
    $\begingroup$ 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. $\endgroup$ – Old John Nov 7 '12 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$?".


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.