6. Zadatak

Označimo sa $n!$ umnožak prvih $n$ prirodnih brojeva.

Ako je $n\geq3$ neparan broj, zbroj prvih $n$ prirodnih brojeva je umnožak prirodnih brojeva $n$ i $\frac{n+1}{2}$.

Budući da je $\frac{n+1}{2}<n$, slijedi da $\frac12(n+1)$ dijeli $(n-1)!$, odnosno $n\cdot\frac{n+1}{2}$ dijeli $n!$.

Za $n=1$, $n!=1$ je djeljiv s $\frac{n(n+1)}2=1$.

Tvrdnja vrijedi za sve neparne prirodne brojeve $n$.

Pretpostavimo da je $n$ paran broj.

Zbroj prvih $n$ prirodnih brojeva je umnožak prirodnih brojeva $\frac n2$ i $n+1$.

Ako je $n+1$ složen broj, onda vrijedi $n+1=p^2$ za prost broj $p\geq3$ ili $n+1=a\cdot b$, gdje je $1<a<b<n$.

Prvi slučaj. Neka je $n+1=p^2$ za prost broj $p$.

Budući da su brojevi $n$ i $p$ relativno prosti, brojevi $p$, $2p$ i $\frac n2$ međusobno su različiti i manji od $n$, pa $p\cdot2p\cdot\frac n2$ dijeli $n!$. Slijedi da $\frac n2\cdot p^2=\frac n2\cdot(n+1)$ dijeli $n!$.

Drugi slučaj. Neka je $n+1=a\cdot b$ za $1<a<b<n$.

Budući da su brojevi $\frac n2$ i $n+1$ relativno prosti, brojevi $a$, $b$ i $\frac n2$ međusobno su različiti i manji od $n$, pa $\frac n2\cdot a\cdot b$ dijeli $n!$.

Treći slučaj. Neka je $n+1=p$ za neki neparan prost broj $p$.

Tada $p$ dijeli $\frac{n(n+1)}2$, ali $p$ ne dijeli $n!$.

Rješenje su svi prirodni brojevi koji nisu oblika $p-1$, gdje je $p$ neparan prost broj.