# The rigorousness of this proof about greatest common divisors.

My task is to prove that gcd(n, n+1)=1 for all n>0. It is obvious that 1 is a common divisor of both n and n+1 since $$1|n → 1x=n$$ if x=n, and $$1|n+1 → 1y=n+1$$ if y=n+1.

To prove that 1 is the greatest common divisor, I did as follows:

From the integers n and n+1 the other must be an even integer, and the other an odd integer. Since one of them must be odd, the gcd of the two can't be an even number, because the odd one doesn't have any even divisors. If the gcd of the two were an odd integer greater than 1, for example 3, then $$3|n → 3x=n → n=3x$$ and $$3|n+1 → 3y=n+1 → n=3y-1,$$ and there are no integers x and y such that both of these equations would hold at the same time. This happens with every odd integer larger than 1.

Is the part about the odd integers greater than 1 rigorous enough for a proper proof? I don't think it is; how would you prove this more rigorously? If anyone has any other improvement ideas of any kind, they're more than welcome!

• Seems unnecessarily complex. If $d|a$ and $d|b$ then $d|(a-b)$. Hence, in your case, $d|(n+1-n)\implies d|1$. Thus the only positive common divisor of $n$ and $n+1$ is 1. – lulu Nov 8 '15 at 22:34
• $\gcd(a,b)\le|a-b|$ – JMP Nov 8 '15 at 22:36
• It should be noted that the solution OP has given really is just a long-winded version of the version @lulu and I have given – ASKASK Nov 8 '15 at 22:37
• (obv) for $a\ne b$ – JMP Nov 8 '15 at 22:46

If you know that $a \mid b$ and $a \mid c$ implies $a \mid b \pm c$, then this theorem is easier than you have laid it out to be. Let $a$ be any common divisor of $n$ and $n+1$. Then $a \mid (n+1)-n$, so $a \mid 1$. Do you think you can take it from here?

In regards to the first part, just note that if $ap=b$ and $aq=c$, then $b \pm c = a(p \pm q)$.

"3|n→3x=n→n=3x

and 3|n+1→3y=n+1→n=3y−1, , and there are no integers x and y such that both of these equations would hold at the same time. This happens with every odd integer larger than 1."

I really hate to say this, but if you can state that there are no integers that solve these, you could just have easily have stated "There are no integers other than 1 that divide both n and n+1" and saved yourself a lot of trouble.

In fact, that's the gyst of the matter, the only number that divides both n and n+1 is 1.

So how do you prove that? If you accept that if a|b and a|c then a|(b - c), it is easy, as a|n+1 and a|n implies a|(n+1 -n) = 1. And if a|1 = 1. So gcd(n, n+1) = 1.

If you don't know that if a|b and a|c then a|(b - c). Well you know that if a|n then n = a*m for some m. So $\frac {n+ 1}{a} = m + \frac{1}{a}$. If a > 1 then this is not an integer and $a$ does not divide $n + 1$. So no integer other than 1 divides both n and n + 1. So gcd(n, n+1) = 1.

• Er... no positve integer other than 1 divides both n and n+1..... – fleablood Nov 8 '15 at 22:58

If $$n$$ is even then $$n+1$$ is odd, therefore $$gcd(n,n+1)=1$$ Analogously, if $$n$$ is odd then $$n+1$$ is even, therefore $$gcd(n,n+1)=1$$.