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≠0, gcd.
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.
Answer
Let d be the gcd(k, k+1) then k=rd, k+1=sd, so 1=(s-r)d, so d |1.
No comments:
Post a Comment