Prime factors. Why does $n$ and $n+1$ have no prime factors in common.

Question

Could anyone explain to me why $n$ and $n+1$ share no prime factors. I have found some formal proofs online but unfortunately didn't really understand them.

I accept that it is the case eg: $24 = 2\cdot2\cdot2\cdot3$

$25 = 5\cdot5$

$26 = 2\cdot13$

$27 = 3\cdot3\cdot3$

I found this question in a school text book and it was asking to explain why so I assumed there must be an easy explanation (rather than a formal proof).

Thanks, any help would be greatly appreciated.

Answer 1

Suppose you have a prime $p$ such that $p$ divides $n$ and $n+1$. Then, $p$ must divide their difference. I.e., $p$ divides $(n+1)-n=1$, which is impossible: no prime divides $1$!

Answer 2

If the prime p divides n, the division n/p leaves remainder 0. Then the division (n+1)/p must leave remainder 1, i.e., p does not divide n+1. I hope this helps.

Answer 3

If $p|n$ and $p|n+1$ then $\frac np$ and $\frac {n+1}p = \frac np + \frac 1p$ are both whole numbers. So $\frac 1p$ is a whole number. So $p = 1$. So only $1$ divides both $n$ and $n+1$.

....or.... if $n = k*p$ and $n+1 = j*p$ then $1 = (n+1)-n = j*p-k*p = (j-k)*p$. So $\frac 1p = j-k$ is an integer. That's only possible if $p = 1$.

Answer 4

It might help to point out that multiplication distributes over addition; that is to say, for any three values $m, k, p$,

$$ p(k+m) = pk+pm $$

So suppose you had two numbers $n$ and $n+1$ that had a common factor $p$, so that

$$ n = pk $$

$$ n+1 = pk' $$

where we may assign $k' = k+m$; that is, $k' = k$ adjusted by some value $m$. Now, what might $m$ be? We observe that the distributive property tells us that $p(k+m) = pk+pm$. If we subtract

$$ n = pk $$

from

$$ n+1 = p(k+m) = pk+pm $$

we get

$$ 1 = pm $$

But $1$ factors only into itself, so both $p$ and $m$ must then equal $1$. Since $1$ is not a prime, we find that $n$ and $n+1$ cannot have any prime factor in common.

Answer 5

Looking at just the positive integers, what do you think is the smallest prime? If you answer $1$, we have a problem. But if you answer $2$, then we can move forward.

Suppose $n$ is divisible by $2$. What are the two numbers nearest to $n$ that are also divisible by $2$? Obviously $n - 2$ and $n + 2$. Clearly $n - 2 < n - 1 < n < n + 1 < n + 2$.

Now suppose that $n$ is also divisible by some positive odd prime $p$. What are the two numbers nearest to $n$ that are also divisible by $p$? That's right, $n - p$ and $n + p$. Since $p > 2$, we can now say $$n - p < n - 2 < n - 1 < n < n + 1 < n + 2 < n + p.$$