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

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.

• If $d$ divides both $a$ and $b$, it also divides $a-b$. If $a=n+1$ and $b=n$ have a common factor, it must be a divisor of $1$. – Jack D'Aurizio Sep 7 '16 at 19:15
• By contradiction you've the proof using the Fundamental Theorem of the Arithmetic and dividing, that is the answer of previous users (with two cases: $n=1$ or $n>1$). Also you can think about Erathosthenes sieve, and think what's about the sequence $(kp)_{k\geq 1}$ of multiples of a (fixed) prime (by cases, being $n>1$ if $n=kp$ with $k=1$, or $n=kp$ with $k>1$), then you can deduce easily other proof. I like a lot the Gamma function (see the Motivation), the successor function, the sum of divisor function...is a puzzle. Good luck. – user243301 Sep 7 '16 at 19:57

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$!

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.$$

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.

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$.

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.