Today I Learned

Some of the things I've learned every day since Oct 10, 2016

96: Euler’s Theorem (Number Theory)

Euler’s Theorem is a sort of extension of Fermat’s Little Theorem. One way of stating Fermat’s is that where n is prime and a is any integer,

a^{p-1} \equiv 1 (\textrm{mod } n),

whereas Euler’s Theorem makes the more general statement that if a, n are simply two coprime integers and \varphi (n) is Euler’s totient function,

a^{\varphi (n)} \equiv 1 (\textrm{mod } n).

The reason Fermat’s is a valid special case of Euler’s is because when n is prime, \varphi (n) = n - 1.

[The congruence in the statement of Euler’s theorem is actually equivalent (‘if and only if’) to a, n being coprime.]

Advertisements

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: