# Modular Arithmetic proof n^x mod x = n mod x

My question is regarding a basic modular arithmetic proof that I have been stuck with for the past week.

Suppose that for all n in the set of natural numbers (assuming 0 is not included in the natural numbers), show that:

$n^{17}$ mod 17 = n mod 17

I use 17 as an example number here, and an answer for this will suffice. But in case it is possible, I feel like there is an overall pattern to prove this for the general case:

$n^{x}$ mod x = n mod x, where x is a natural number.

I feel like the proof somehow contains modular arithmetic, such as multiplication, and I get the feeling it should be a short proof in nature, but I feel like I'm missing a step.

Any help is much appreciated!

That is the Fermat's Little Theorem:

If $n$ is an integer and $p$ is a prime, then $$n^p \equiv n (\mathrm{mod}~p).$$ It only holds when the exponent is prime. You can easily find counterexamples for the non - prime case.

You could prove this statement by induction on $n$ and applying the binomial theorem. If you want to give a proof using modular arithmetic, then you have to prove it in the follwing form:

If $p$ is a prime not dividing $n$, then $$n^{p-1} \equiv 1 (\mathrm{mod}~p).$$ For the proof, show that the reminders mod $p$ of ${n,2n,3n,...(p-1)n}$ are all distinct, so the product of them is equal mod $p$ to $1\times2\times...\times(p-1)$.

The result is false in general. For example

$$2^4 \equiv 0 \pmod{4}.$$

You may be interested to look up Fermat's Little Theorem:

If $p$ is a prime number, then for any $n \in \mathbb{N},$ we have

$$n^p \equiv n \pmod{p}.$$