Fermat Little Theorem "maximal" extension

Jun 2013
1,315
116
London, England
I remember finding a paper that presented a "maximal" extension to Fermat's Little Theorem. I got as far as the case where $n$ is a product of distinct primes $p_i$ and if $l = lcm \{p_i -1 \}$ then:

$$\forall x: \ x^{l+1} = x \ (mod \ n)$$

Does anyone know of an extension to this, where $n$ is any number?
 
Oct 2009
942
366
In general, you should study this through the chinese remainder theorem. This gives a ring isomorphism $\varphi$ between rings $\mathbb{Z}_n$ and
$$\mathbb{Z}_{p_1^{k_1}}\times ... \mathbb{Z}_{p_l^{k_l}}$$
Thus we get $x^L = x$ if and only if $\varphi(x)^L = \varphi(x)$. And this is true if for each component in the ring $\mathbb{Z}_{p_1^{k_1}}\times ... \mathbb{Z}_{p_l^{k_l}}$ it is true. So this reduces the question to rings of the form $\mathbb{Z}_{p^k}$ which is easy.
 
  • Like
Reactions: 1 person