# Math Help - Modular Exponentiation

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?

2. Originally Posted by timorrill
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)$.