6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Jack D'Aurizio Sep 7 '16 at 19:15
  • $\begingroup$ 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. $\endgroup$ – user243301 Sep 7 '16 at 19:57
8
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.