We know,
((a mod N) * (b mod N)) mod N = (a*b) mod N
a^(p-1) mod p = 1
Thus
( a^(p-1) * a^(p-1) * a^(p-1) * ... * a^(p-1) ) mod p = ( 1 * 1 * 1 * ... * 1) mod p = 1
Tada.
Question
According to Fermat's Little theorem a^(p-1) mod(p) is 1. So a^k(p-1) mod(p)will also be 1 by splitting into k parts and apply modulus independently we get '1'. Am I missing something?
Solution
We know,
((a mod N) * (b mod N)) mod N = (a*b) mod N
a^(p-1) mod p = 1
Thus
( a^(p-1) * a^(p-1) * a^(p-1) * ... * a^(p-1) ) mod p = ( 1 * 1 * 1 * ... * 1) mod p = 1
Tada.
OTHER TIPS
You are right. In general, the equation holds as a^(k*phi(n)+b) is congruent with a^b modulo n where phi denotes the Euler-phi function, and a is relative prime to n.