Lagmental Vicfred

Euler's Totient Counts the Units Modulo n by Vicfred

Last updated: Wed 24 August 2016

tags: mathematics, congruences, multiplicative order, primitive roots

The totient function is multiplicative and removes one factor 1 minus 1 over p for every prime dividing n. A small computation will anchor the general statement before the abstraction takes over.

Set-up

Congruences turn divisibility into arithmetic in \(\mathbf Z/n\mathbf Z\). The unit group \((\mathbf Z/n\mathbf Z)^\times\) controls which residues can be cancelled, inverted, or assigned a multiplicative order.

$$ \varphi(n)=\#(\mathbf Z/n\mathbf Z)^\times $$

The formulas should not be merged too early. The datum \(\mathsf D\), the conclusion \(\mathsf C\), and the bridge \(\Longrightarrow\) have three different logical jobs.

$$ \varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right) $$

The calculation

The following line is the smallest calculation that still exercises the mechanism. It keeps nested delimiters and the order of operations explicit.

$$ n=360=2^3\,3^2\,5\quad\Longrightarrow\quad\varphi(360)=360\left(1-\frac12\right)\left(1-\frac13\right)\left(1-\frac15\right)=96 $$

What survives abstraction

The formula is reusable precisely because it says which pieces are structural and which belong only to the worked example.

$$ \begin{aligned} \mathsf{D}\;&:\quad \varphi(n)=\#(\mathbf Z/n\mathbf Z)^\times,\\[5pt] \mathsf{C}\;&:\quad \varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right). \end{aligned} $$

The boundary

Cancellation modulo \(n\) requires a unit. Dividing both sides by a zero divisor is one of the fastest ways to manufacture a false congruence.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right) \end{gathered}} $$

This is enough machinery for one note: an exact object, a worked case, a structural law, and a clearly marked boundary. Each layer can now be tested independently.

This article was posted on Thu 07 January 2016. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.