Prove that (n!+1) is not divisible by any natural number between 2 and n.

Question

I tried this question solving by mathematical induction. But no luck Is there is any easy way to prove that?

Answer 1

Hint: If $k|m$ and $k> 1$ then $k\not \mid m+1$.

Pf: Do we need to prove it? If $m = bk$ for some integer $b$ then $m+1 = bk + 1$ and $\frac {m+1}k = b + \frac 1k$ which is not an integer.

And if $2\le k \le n$ then $n! = 1*2*........ * n = \prod_{j:1\le j \le n} j$. So $k$ is between $2.... n$ then it is one of the factors of $n!$.

FORMAL ANSWER (don't read this)

if $2\le k \le n$ then $k$ is a factor of $n! = 1*2*.....*n$. And so $\frac {n!}k$ is an integer. Lets call $\frac {n!}k :=M$. Then $n! = Mk$. So $n!+1 = Mk + 1$ and $\frac {n!+1}k = \frac {Mk+1}k = M + \frac 1k$. But $k > 1$ so $\frac 1k$ is not an integer. So $M + \frac 1k$ is not an integer. So $k\not \mid n! + 1$.

Or a single-line unbelievably short proof:

$n!$ is divisible by all natural number $2$ to $n$ and $1$ is not divisible by any. So $n!+1$ is not divisible by any.

QED

Answer 2

I never want to say don't use induction but... you shouldn't.

But I never want to say don't so:

BASE CASE: $n=2$

$2! + 1=3$. and $2\not \mid 3$.

INDUCTION STEP:

If $k!+1$ is not divisible but any natural number between $2$ and $k$.

Then $(k+1)! + 1 = k!(k+1) + 1= k\cdot k! + k! + 1= k\cdot k! + (k!+1)$. Now any natural number between $2$ and $k$ will divide* $k\cdot k!$ but will not divide $k!+1$ so it will not divide $k\cdot k! + (k!+1)$.

And $k+1$ does divide $k!(k+1)$ but does not divide $1$. SO $k+1$ does not divide $k!(k+1) + 1$.

So no natural number between $2$ and $k+1$ will divide $(k+1)!$. So that is the induction step.

......

SO it can be proven by induction. And it wasn't as hard as I thought it would be. But it wasn't what I'd call easy.

There is a much easier and direct prove that is based on the same idea:

$n!$ is divisible by all natural numbers between $2$ and $n$ and $1$ is not. So $n! + 1$ is not. End of proof. QED.