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?

Printable View

- Aug 27th 2008, 03:49 PMtimorrillModular 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? - Aug 27th 2008, 04:31 PMThePerfectHacker
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)$.