0
$\begingroup$

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.

1 Answers 1

3

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$.

  • 0
    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.2011-10-28