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!
No comments:
Post a Comment