Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.