0
$\begingroup$

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.

  • 1
    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.2012-11-07

3 Answers 3

2

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

2

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$

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