Results 1 to 2 of 2

Math Help - 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:
    (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 ?
    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, 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}
    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 4th 2011, 12:07 AM
  2. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 3rd 2011, 02:37 PM
  3. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 28th 2010, 06:08 AM
  4. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 13th 2008, 04:17 PM
  5. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 25th 2007, 09:39 PM

Search Tags


/mathhelpforum @mathhelpforum