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.
Best Answer
Let $d$ be the $gcd(k, k+1)$ then $k=rd$, $k+1=sd$, so $1=(s-r)d$, so $d |1$.