prove that (a^p) mod p = a mod p if p is prime
- User
prove that (a^p) mod p = a mod p if p is prime
- Assistant
To prove that ((a^p) \mod p = a \mod p) when (p) is a prime number, we can use Fermat's Little Theorem. Ferm and Little Theorem states that if (p) is a prime number and (a) is any integer not divisible by (p), then:
[ a^{p-1} \equiv 1 \pmod{p} ]
Now, let's manipulate this to show the desired result:
Starting from Fermat's Little Theorem: [ a^{p-1} \equiv 1 \pmod{p} ]
Multiply both sides of the congruence by (a): [ a \cdot a^{p-1} \equiv a \cdot 1 \pmod{p} ] [ a^p \equiv a \pmod{p} ]
Thus, ((a^p) \mod p = a \mod p) as we wanted to prove.
This holds for any integer (a) and any prime (p). Additionally, note that if (p) divides (a) (i.e., (a = kp) for some integer (k)), both sides also trivially equal (0) modulo (p), maintaining the validity of the equation.