Prove without using Fermat's theorem or congruences that for every integer $ n $ we have:

Question

a)$ n ^ 5 - n$ is divisible by 5

b)$ n ^ 7-n$ is divisible by 7

c) $n ^ {11} - n$ is divisible by 11

d)$ n ^ {13} -n$ is divisible by 13

I think it can all be done by factoring

Answer 1

You just observe that, if $p$ is an odd prime, then $$ n^p-n\equiv n(n-1)(n-2)\dots(n-p+1)\pmod{p} $$ For instance, with $p=5$ (congruence modulo $5$) \begin{align} n(n-1)(n-2)(n-3)(n-4) &\equiv n(n+1)(n-1)(n+2)(n-2)\\ &\equiv n(n^2-1)(n^2-4)\\ &\equiv n(n^2-1)(n^2+1)\\ &\equiv n^5-n \end{align} Now every $n$ is congruent to one among $0,1,2,3,4$.

For $p=7$ (congruence modulo $7$) \begin{align} n(n-1)(n-2)(n-3)(n-4)(n-5)(n-6) &\equiv n(n+1)(n-1)(n+2)(n-2)(n+3)(n-3)\\ &\equiv n(n^2-1)(n^2-4)(n^2-9)\\ &\equiv n(n^4-5n^2+4)(n^2-2)\\ &\equiv n(n^6-5n^4+4n^2-2n^4+10n^2-8)\\ &\equiv n(n^6-1)\\ &\equiv n^7-n \end{align}

Answer 2

a) $$n^5-n=(n^2+1)(n+1)n(n-1)$$

now if $n\equiv2 \pmod{5}$ or $n\equiv3 \pmod{5}$, $n^2+1$ is divisible by 5, otherwise one three other terms

b) $$n^7-n=n(n^3-1)(n^3+1)$$

$n \equiv 0 \pmod{7}$ - it's trivial, $7|n^3-1$ if $n \equiv 1 \pmod{7}$, $n \equiv 2 \pmod{7}$ or $n \equiv 4 \pmod{7}$ and $7|n^3+1$ if $n \equiv 3 \pmod{7}$, $n \equiv 5 \pmod{7}$ or $n \equiv 6 \pmod{7}$

Other can be done equivalently.

For larger powers the following formula might be helpful: $n^a+1=(n+1)(n^{a-1}-\dots+1)$, $n^a-1=(n-1)(n^{a-1}+\dots+1)$ for odd $a$.

Answer 3

This problem can be seen and resolved as a matter of symmetry (and combinatorials).

Suppose we have infinite balls of n colors and a circle with "p" (prime) holes. (The first hole has a small signal).

We place the balls in the hollow "p" of the circle

We can repeat the balls, but avoiding putting all the same.

So, how many ways can n balls be placed in the p-holes of the circle?

$$n ^ p-n$$

But it turns out that for each different placement of balls, we can always observe that "there is no rotation symmetry", we cannot rotate the circle less than one turn and see the same colors in the same positions. (This that: p is a prime).

Which leads us to that for each "position" there are other (p-1) accounted for in the totals.

With which it is demonstrated by these symmetries that:

$$n ^ p-n$$ is divisible by $$p$$