# Is there a closed form to $a^b \bmod b$ if $b$ is not a prime?

We know

$$a^p \equiv a \pmod p\quad p\text{ a prime, }0\leq a \leq p-1.$$

But if we have $b$, not prime, what's the new formula? $$a^b \equiv\ ? \pmod b,\quad b\text{ not a prime, } 0\leq a \leq b-1\$$

How to find it?

OBS.: To someone who has reputation enough, I think it's interesting create a new tag named composite-numbers.

-

The best we have is Euler's theorem: If $a$ is relatively prime to $n$, then $$a^{\varphi(n)}\equiv 1 \pmod n$$ where $\varphi(n)$ is the totient function counting the number of integers between 1 (inclusive) and $n$ that are relative prime to $n$. This is easy enough to compute if you know the prime factorization of $n$, but (as far as is known) hard otherwise for large $n$.
I would add that because there is a closed form for $a^{\phi(n)}\pmod n$ there can't be a closed form for $a^n\pmod n$ unless there's a closed form relation between $\phi(n)$ and $n$, but any relation between those two numbers is equivalent to the factorization of $n$, and that is generally conceded to be a hard problem. –  Gerry Myerson Oct 27 '11 at 23:38
I think I didn't a bit clear in the first time of this question. Needed to change it. Thanks @HenningMakholm, but I already know this Euler theorem, but I would like a clue or a answer of how we can extend this formula to composite-numbers too. I think it can be very interesting, for example, $(a-1)! \equiv 0 \mod a$ implies $a$ is composite it still very interesting than $(p-1)! \equiv -1 \mod p$ implies $p$ is prime. –  GarouDan Oct 28 '11 at 12:45