Sunday 3 September 2017

elementary number theory - 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!

No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...