Abstract Nonsense

Crushing one theorem at a time

Chinese Remainder Theorem (Pt. III)

Point of Post: This is a continuation of this post.



\text{ }

As a last number theoretic corollary (there are many more, but I don’t have the time to list them all) we prove the fundamental fact about the Euler Totient Function \varphi. Recall that \varphi is the function \mathbb{N}\to\mathbb{N} defined by

\text{ }

\varphi(n)=\#\left\{k\leqslant n:(k,n)=1\right\}

\text{ }

It is easy to calculate \varphi for certain numbers. For example, if n=p^a for some prime p we know that r\leqslant n is NOT coprime to p^a if and only if p\mid r. So, the number of non-coprime numbers less than n is p^{a-1} since pm\leqslant p^a is true if and only if m\leqslant p^a, and so there are p^a choices. Thus, \varphi(p^a)=p^a-p^{a-1}. It is then a basic fact of number theory that \varphi(n)=\#(U(\mathbb{Z}/(n))) (i.e. the number of units in \mathbb{Z}/(n)). But, by the CRT we know that,as rings \mathbb{Z}/(n)\cong\mathbb{Z}/(p_1^{a_1})\times\cdots\times \mathbb{Z}/(p_m^{a_m}). But, recall that every ring isomorphism induces a group isomorphism on the group of units so that as groups we know U(\mathbb{Z}/(n))\cong U(\mathbb{Z}/(p_1^{a_1})\times\cdots\times U(\mathbb{Z}/(p_m^{a_m}))Recalling that the unit group of a product is the product group of the units we may finally conclude that U(\mathbb{Z}/(n))\cong U(\mathbb{Z}/(p_1^{a_1}))\times\cdots\times U(\mathbb{Z}/(p_m^{a_m})). And so in particular

\text{ }

\#(U(\mathbb{Z}/(n)))=\#(U(\mathbb{Z}/(p_1^{a_1})))\cdots \#(U(\mathbb{Z}/(p_m^{a_m})))

\text{ }

which, if you stare at it long enough says that

\text{ }

Theorem: For every n\in\mathbb{N} one has that

\text{ }

\displaystyle \varphi(n)=\prod_{j=1}^{m}\varphi\left(p_j^{a_j}\right)=\prod_{j=1}^{m}p_j^{a_j-1}\left(p_j-1\right)

\text{ }

\text{ }

All things considered, it’s pretty amazing what one little theorem can do!

\text{ }

\text{ }


1. Dummit, David Steven., and Richard M. Foote. Abstract Algebra. Hoboken, NJ: Wiley, 2004. Print.

2. Bhattacharya, P. B., S. K. Jain, and S. R. Nagpaul. Basic Abstract Algebra. Cambridge [Cambridgeshire: Cambridge UP, 1986. Print.


September 6, 2011 - Posted by | Algebra, Ring Theory | , , , , , , , , ,

1 Comment »

  1. […] then that since and and commute we have, from basic group theory, that . And, since (where is Euler’s totient function). The conclusion […]

    Pingback by The Unit and Automorphism Group of Z/nZ « Abstract Nonsense | September 10, 2011 | Reply

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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: