Fermat’s Little Theorem

Use Lagrange’s Theorem in the multiplicative group (\mathbb{Z}/(p))^\times to prove Fermat’s Little Theorem: if p is prime then a^p \equiv a \ \mathrm{mod}\ p.


If p is prime, then \varphi(p) = p-1 (where \varphi denotes the Euler totient). Thus |((\mathbb{Z}/(p))^\times| = p-1. So for all a \in (\mathbb{Z}/(p))^\times, we have |a| divides p-1. Hence a = 1 \cdot a = a^{p-1} a = a^p mod p.

Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: