Some modular arithmetic

**rebghb** · October 25th 2010, 11:18 AM

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

**Bacterius** · October 25th 2010, 11:41 AM

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

Thread: Some modular arithmetic

LinkBack

Thread Tools

Display

Some modular arithmetic

Similar Math Help Forum Discussions

Modular arithmetic

Modular arithmetic

Modular Arithmetic

Modular arithmetic

modular arithmetic

Search Tags