Prove that consecutive integers are always coprime

Question

I'm wondering if the proof below is strong enough to prove that consecutive integers are always coprime.

Let $a$ and $(a+1)$ be our $2$ numbers, and suppose $a$ has $k$ that divides it, then we have $a\equiv 0 \bmod(k)$ , and adding $1$ to each side gives us $a+1\equiv 1\bmod(k)$. And since we can do this to every divisor of $a$ they can never share the same divisor.

That shows that no divisor of $a$ is a divisor of $a+1$. But how do you show that no divisor of $a+1$ is a divisor of $a$? — fleablood, Oct 13 '19 at 06:04

score 4 · Accepted Answer · edited Oct 15 '19 at 16:51

4

Hagen von Eitzen's comment:

Let $k (\not =1)$ be a common divisor of $a+1$ and $a$.

Then

$k$ divides $(a+1)-a$ (why?).

Since $(a+1)-a =1$, $k$ divides $1$, a contradiction.

P.S. A similar argument can be used to prove that there are infinitely many primes.

edited Oct 15 '19 at 16:51

J. W. Tanner

60,406

answered Oct 13 '19 at 06:17

Peter Szilas

20,344
2
17
28

For the why part apply $k\mid b\iff kc=b$ for some integer $c$. E.g $kr=a$ and $ks=a+1$ so that $ (a+1)-a=(s-r)k=tk$ which implies $k\mid 1$. – pshmath0 Oct 13 '19 at 06:37
Pixel.Yes. Try to argue that there are infinitely many primes using a similar argument. – Peter Szilas Oct 13 '19 at 06:45

score 1 · Answer 2 · answered Oct 13 '19 at 06:06

You can elaborate your answer more properly using $\text{ 'Fundamental Theorem Of Arithmetic' }$.

Let The prime factorization of a number $A$ be : $$ A = p_0^{a_0}.p_1^{a_1}p_2^{a_2}p_3^{a_3}.....p_n^{a_n}$$

Then $A+1$ would be : $$ A+1 = p_0^{a_0}.p_1^{a_1}p_2^{a_2}p_3^{a_3}.....p_n^{a_n} + 1$$

Since when divided by any $ p \space \space (p|A)$ , it will always leave the remainder $1$ , we can conclude that $A $ and $A+1$ are always co-prime.

Prove that consecutive integers are always coprime

2 Answers2