Fermat’s Little Theorem Co-prime Condition

It is confusing for students regarding the two forms of the Fermat’s Little Theorem, which is the generalization of the ancient Chinese Remainder Theorem (中国剩馀定理) — the only theorem used in modern Computer Cryptography .

General: For any number a

\boxed { a^p \equiv a \mod p, \forall a}

We get,
a^{p} - a \equiv 0 \mod p
a. (a^{(p-1)} -1) \equiv 0 \mod p
p \mid a.(a^{(p-1)} -1)
If (a, p) co-prime, or g.c.d.(a, p)=1,
then p cannot divide a,
thus
p \mid (a^{(p-1)} -1)
a^{(p-1)} -1 \equiv 0 \mod p

Special: g.c.d. (a, p)=1

\boxed {a^{(p-1)} \equiv 1 \mod p, \forall a \text { co-prime p}}

image

Advertisements

One thought on “Fermat’s Little Theorem Co-prime Condition

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