Divisibility of composite numbers [duplicate]

Solution 1:

By the Fermat little theorem, $n^{5} \equiv n \mod 5$ i.e. $n^{5} - n \equiv 0 \mod 5$.

Solution 2:

I'm going to take a leap, and suppose that you are doing exercises from the first section of Ireland and Rosen. In that case, I think that FLT is not the 'anticipated' method of solution.

So let's start from your factorization, $(n-1)n(n+1)(n^2 + 1)$

If $n$ is of the form $5k$, $5k-1$, or $5k+1$, we're done from the first three factors. What if $n$ is of the form $5k \pm 2$?

I claim to you that $n^2 + 1$ is always divisible by $5$ if $n = 5k \pm 2$. Perhaps the easiest way to see this is through strict computation. Or you could note that the constant term is either $5$ or $10$. In any case, I leave that part to you: can you show that $n^2 + 1$ is divisible by $5$ if $n = 5k \pm 2$?

Solution 3:

Using combinatorial polynomials: $$ \begin{align} n^5-n &=120\binom{n}{5}+240\binom{n}{4}+150\binom{n}{3}+30\binom{n}{2}\\ &=30\left(4\binom{n}{5}+8\binom{n}{4}+5\binom{n}{3}+\binom{n}{2}\right) \end{align} $$ Note: The combinatorial polynomial expansion for a known polynomial, $P(n)$, is not as hard as it might seem. The coefficient, $a_0$, of $\binom{n}{0}$ is simply $P(0)$. If the coefficients, $a_j$, for $\binom{n}{j}$ are known for $j<k$, then the coefficient for $\binom{n}{k}$ is $$ P(k)-\sum_{j=0}^{k-1}a_j\binom{k}{j} $$

Solution 4:

Note that $n^2+1$ is divisible by $5$ iff $n^2-4$ is divisible by $5$. But $n^2-4=(n-2)(n+2)$.

So $(n^2+1)(n-1)(n)(n+1)$ is divisible by $5$ iff $(n-2)(n-1)(n)(n+1)(n+2)$ is divisible by $5$. But this is the product of $5$ consecutive integers. End of proof.

Remark: There are more general ways of attacking the problem. But the one used above continues the pattern that you used for $2$ and $3$. Continuing in this way quickly becomes too complicated for practical use, and one ends up turning to Fermat's Theorem, and Euler's Theorem.

Solution 5:

You are almost done: If $n \equiv 0, \pm 1 \pmod 5$ we are done (as we have $5 \mid n$, $5 \mid n-1$ or $5 \mid n+1$ then). So suppose $n \equiv \pm 2 \pmod 5$, but then $n^2 + 1 \equiv (\pm 2)^2 + 1 \equiv 0 \pmod 5$, hence $5 \mid n^2 + 1$, and so $5 \mid n^5 -n$ also in this case.