Prove that every two consecutive integers are coprime
Answers
0Consecutive Numbers are coprimenumber-theoryCan anyone help me in proving that two consecutive numbers are co-primes?My approach:Let two consecutive numbers arennandn+1n+1.Assume they are not co-primes.Thengcd(n,n+1)=xgcd(n,n+1)=x, because it can not equal to11,xxis natural andx>1x>1So xx divides nn as well as n+1n+1.Then xx also divides n+1−nn+1−n, by general understanding.Hence xx divides 11 or x=1x=1.But we have assumed x>1x>1.So by contradiction nn & n+1n+1 are co-prime.Is it right or is there any better way to prove that two consecutive numbers are co-prime?share improve this questionasked Dec 6 '16 at 12:41Atul Mishra1,914●10●34editedDec 6 '16 at 13:42Vidyanshu Mishra8,268●4●29●782Your argument is correct: indeed this is the shortest way to prove that two consecutive numbers are coprime. – Crostul Dec 6 '16 at 12:43Crostul is right, your argument is correct. – VincentDec 6 '16 at 12:451It's not really necessary to go for the contradiction. Your argument is almost a direct argument as it stands. Let x=gcd(n,n+1).x=gcd(n,n+1).Then xx divides n+1−n=1n+1−n=1. Therefore x=1x=1. – B. Goddard Dec 6 '16 at 12:512Guys this question does not deserve downvotes. The OP has given his argument and shown his work. What do you expect from him now. +1 by me – Vidyanshu Mishra Dec 6 '16 at 13:41add a comment4 Answersorder by activeoldestvotes3Your proof looks good. Using the method of contradiction is not a bad idea here but you could have skipped that in your prove.Given thatnnand n+1 are two consecutive integers. Now suppose gcd(n,n+1)=pgcd(n,n+1)=p. Then p|n and p|n+1p|n+1. Which implies thatp|n+1−np|n+1−norp|1p|1. There is no number which divides 1 except 1. So p=1p=1or you can say gcd(n,n+1)=p=1gcd(n,n+1)=p=1. Which impliesnnandn+1n+1are coprime.Notice that I have not used contradiction anywhere.share improve this answeranswered Dec 6 '16 at 13:37Vidyanshu Mishra8,268●4●29●783We have n∣n+1m−1. n∣n+1⏞m−1. Your (correct) proof easily generalizes as follows.Generally n∣km−1⇒km−jn=1, n∣km−1⇒km−jn=1, so d∣m,n⇒d∣1, d∣m,n⇒d∣1, so gcd(m,n)=1 gcd(m,n)=1i.e. mod n: m−1 mod n: m−1 exists ⇒gcd(m,n)=1.⇒gcd(m,n)=1.The converse is also true (Bezout gcd identity)Remark We can also use (a single step of) the Euclidean algorithmgcd(km,n)=gcd(jn+1,n)=gcd(1,n)=1⇒gcd(m,n)=1gcd(km,n)=gcd(jn+1,n)=gcd(1,n)=1⇒gcd(m,n)share improve this answeranswered Dec 6 '16 at 15:21Bill Dubuque216k●29●202●667editedApr 13 '17 at 12:21Community♦12Your proof is correct, but there is a simpler one, that doesn't work by contradiction and doesn't need greatest common divisors explicitly.If a primeppdivides nnthen dividingn+1n+1byppleaves a remainder of11, so ppdoes not divide n+1n+1. That means the factorizations of nnandn+1n+1have no prime in common, sonnandn+1n+1are relatively prime.But ... this proof does use unique factorization, which is usually proved by thinking about greatest common divisors. So they are there, behind the scene.share improve this answeranswered Dec 6 '16 at 13:54Ethan Bolker48.9k●5●56●125But the proof doesn't require prime factorizations. It can be presented in a universal way that works in any ring, e.g. see my answer. – Bill Dubuque Dec 6 '16 at 15:26@BillDubuque True, as I note. I've upvoted your answer. But mine may help a beginner think about the problem in a useful way. – Ethan Bolker Dec 6 '16 at 15:34add a comment0Here's a direct proof that preserves generality for all integers.Let n∈Zn∈Z such that n∉[−2,1]n∉[−2,1]. Then suppose exists d∈Zd∈Z such that gcd(n,n+1)=dgcd(n,n+1)=d and d≥1d≥1.Then we know thatd∣nd∣nand d∣n+1d∣n+1, so we have p,q∈Zp,q∈Zsuch that n=d⋅pn=d⋅pandn+1=d⋅pn+1=d⋅p.We can then do the following:nn+1(d⋅q)d⋅q−d⋅pd⋅(q−p)=d⋅p=d⋅p+1=d⋅p+1=1=1since n+1=d⋅qn=d⋅pn+1=d⋅p+1(d⋅q)=d⋅p+1since n+1=d⋅qdAnd therefore we have thatd∣1d∣1. Since we're inZZ, we know11is only divisible by ±1±1(i.e.∀x∈Z∀x∈Z,x∣1x∣1is only true when x=±1x=±1), therefored=±1d=±1and sinced≥1d≥1,d=1d=1.Finally, we have that gcd(n,n+1)=d=1gcd(n,n+1)=d=1