Use Lagrange’s Theorem to prove Euler’s Theorem

Use Lagrange’s Theorem in the multiplicative group G = (\mathbb{Z}/(n))^\times to prove Euler’s Theorem: if \mathsf{gcd}(a,n) = 1 then a^{\varphi(n)} \equiv 1 \ \mathrm{mod}\ n. (\varphi denotes the Euler totient function.)

If \mathsf{gcd}(a,n) = 1, then \overline{a} \in \mathbb{Z}/(n)^\times. By Lagrange’s Theorem, |a| divides |G| = \varphi(n). Thus a^{\varphi(n)} \equiv 1 mod n.

Post a comment or leave a trackback: Trackback URL.


  • Kenneth Tiong  On October 13, 2011 at 10:56 am

    This is wrong. a does not generate G. Consider G = (Z/9Z) under mult,
    G = {1 2 4 5 7 8}
    a = = {1 ,4 ,7}

    We can only say |a| divides |G|

Leave a Reply

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

You are commenting using your 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: