# Abstract Nonsense

## 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{ }$

References:

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.