Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|k$ and $d|k+1$ $\implies$ $d | 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.

share|improve this question
2  
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. –  Old John Nov 7 '12 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 –  alexthebake Nov 7 '12 at 3:57
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. –  Old John Nov 7 '12 at 4:00

3 Answers 3

up vote 2 down vote accepted

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

share|improve this answer

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$

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.