# Some modular arithmetic

• Oct 25th 2010, 12:18 PM
rebghb
Some modular arithmetic
Hello everyone!

I'm new to modular arithmetic, I read a few identities like:
$(a+b)\mod N = ( (a\mod N) + (b\mod N) )\mod N$ and
$(a \times b)\mod N = ( (a\mod N) \times (b\mod N) ) \mod N$... I searched this, but couldn't find an identity for this:
$a^b\mod N = (a \times a \times \cdots \times a) \mod N = (a \mod N)^b \mod N$. But so what? We didn't reduce the equation, we just replaced $a$ by $a \mod N$.
Is there a way that calculates or defines $a^b \mod N$ ?
• Oct 25th 2010, 12:41 PM
Bacterius
In this case, $b$ (and in general any exponent) cannot be "reduced" that easily, as $b$ is replaced by $b \mod{\varphi{(n)}}$, where $\varphi{(n)}$ is the Euler Totient of $n$.

So $a^b \equiv (a \mod{n})^{b \mod{\varphi{(n)}}} \pmod{n}$

The following goes beyond basic number theory - this can be shown, interestingly, to "pile up" for various exponent levels, and the $\varphi$ function is iterated :

$a^{(b^c)} \equiv (a \mod{n})^{\displaystyle (b^{c \mod{\varphi{(\varphi{(n)})}}}) \mod{\varphi{(n)}}} \pmod{n}$