Results 1 to 2 of 2

Thread: Modular Exponentiation

  1. August 27th 2008, 03:49 PM #1
    timorrill
    timorrill is offline
    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. August 27th 2008, 04:31 PM #2
    ThePerfectHacker
    ThePerfectHacker is offline
    Global Moderator ThePerfectHacker's Avatar
    Joined
    Nov 2005
    From
    New York City
    Posts
    10,603
    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 \gcd(x,p)=1.

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

    Then x^d \equiv x^e (\bmod p) if and only if d\equiv e (\bmod k) if and only if k|(d-e). But (p-1)|(d-e) and k|(p-1) so k|(d-e).
    Follow Math Help Forum on Facebook and Google+
« Simplify | Elementary Number Theory - beginnings »

Similar Math Help Forum Discussions

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

Search Tags


/mathhelpforum @mathhelpforum