Results 1 to 2 of 2

Thread: Some modular arithmetic

  1. #1
    Member
    Joined
    Jan 2010
    Posts
    133

    Some modular arithmetic

    Hello everyone!

    I'm new to modular arithmetic, I read a few identities like:
    $\displaystyle (a+b)\mod N = ( (a\mod N) + (b\mod N) )\mod N$ and
    $\displaystyle (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:
    $\displaystyle 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 $\displaystyle a$ by $\displaystyle a \mod N$.
    Is there a way that calculates or defines $\displaystyle a^b \mod N$ ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    In this case, $\displaystyle b$ (and in general any exponent) cannot be "reduced" that easily, as $\displaystyle b$ is replaced by $\displaystyle b \mod{\varphi{(n)}}$, where $\displaystyle \varphi{(n)}$ is the Euler Totient of $\displaystyle n$.

    So $\displaystyle 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 $\displaystyle \varphi$ function is iterated :

    $\displaystyle a^{(b^c)} \equiv (a \mod{n})^{\displaystyle (b^{c \mod{\varphi{(\varphi{(n)})}}}) \mod{\varphi{(n)}}} \pmod{n}$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 3rd 2011, 11:07 PM
  2. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 3rd 2011, 01:37 PM
  3. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Mar 28th 2010, 05:08 AM
  4. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Dec 13th 2008, 03:17 PM
  5. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Apr 25th 2007, 08:39 PM

Search Tags


/mathhelpforum @mathhelpforum