Thursday, 28 November 2013

number theory - Prove that for any integer kne0, gcd(k,k+1)=1



I'm learning to do proofs, and I'm a bit stuck on this one.
The question asks to prove for any positive integer k0, 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

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

How to find \lim_{h\rightarrow 0}\frac{\sin(ha)}{h} without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...