Results 1 to 2 of 2

Thread: Modular Exponentiation

  1. #1
    Newbie
    Joined
    Aug 2008
    Posts
    1

    Modular Exponentiation

    I'm struggling to understand why the following is true:

    x^d mod p = x^(d mod (p-1)) mod p

    Can anyone help to explain this?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by timorrill View Post
    x^d mod p = x^(d mod (p-1)) mod p

    Can anyone help to explain this?
    Assuming $\displaystyle \gcd(x,p)=1$.

    Let $\displaystyle e = d \bmod p-1$.
    Let $\displaystyle k = \text{ord}(x)$.

    Then $\displaystyle x^d \equiv x^e (\bmod p)$ if and only if $\displaystyle d\equiv e (\bmod k)$ if and only if $\displaystyle k|(d-e)$. But $\displaystyle (p-1)|(d-e)$ and $\displaystyle k|(p-1)$ so $\displaystyle k|(d-e)$.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. modular exponentiation example
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Mar 3rd 2012, 12:03 PM
  2. Modular Exponentiation Calculator
    Posted in the Math Software Forum
    Replies: 6
    Last Post: Apr 2nd 2011, 07:25 AM
  3. Modular Exponentiation
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Nov 13th 2010, 01:54 PM
  4. Modular Exponentiation
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Sep 13th 2010, 05:31 PM
  5. Modular exponentiation
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: Mar 8th 2009, 11:08 PM

Search Tags


/mathhelpforum @mathhelpforum