Fermat Little Theorem "maximal" extension

Pero

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?

Pero

Thanks.

It was an extension of this as well. The result I posted was for any $x$, not just $x$ coprime with $n$. It was something more general than that.

It was on this site, but the older posts seem to have gone.

[email protected]

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.

1 person