2
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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)$.

$\endgroup$
0
$\begingroup$

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}.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.