# Working with mod p (Euler's and Fermat's Theorem)

• Apr 22nd 2010, 11:19 PM
Zennie
Working with mod p (Euler's and Fermat's Theorem)
Prove that if $\displaystyle p$ is prime, then for any number $\displaystyle a$, divisible by $\displaystyle p$ or not, $\displaystyle a^p \equiv a (mod p)$
• Apr 22nd 2010, 11:22 PM
Drexel28
Quote:

Originally Posted by Zennie
Prove that if $\displaystyle p$ is prime, then for any number $\displaystyle a$, divisible by $\displaystyle p$ or not, $\displaystyle a^p \equiv a (mod p)$

Are you asking to prove Euler's theorem? Do you know group theory? Note that $\displaystyle \left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}$ forms a group whose order is $\displaystyle \varphi(n)$ and since any element of a group to it's order is the identity element the conclusion follows.

If you're just trying to apply it merely notice that if $\displaystyle a\nmid p$ then by virtue of $\displaystyle p$'s primality $\displaystyle (a,p)=1$ in which case Fermat's theorem applies. If $\displaystyle a\mid p$ then either $\displaystyle a\equiv 0,1$ in which case the theorem is a triviality.