Lagmental Vicfred

Carmichael's Function Gives the Exponent of the Unit Group by Vicfred

tags: mathematics, congruences, multiplicative order, primitive roots

The least universal exponent modulo n is often smaller than Euler's totient. I will separate the object being defined from the consequence being claimed.

Start locally

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.

$$ \lambda(n)=\exp\bigl((\mathbf Z/n\mathbf Z)^\times\bigr) $$

The definition determines which expressions are legal; only then does the identity become meaningful. An equality in \(\mathcal A\) may change ambient meaning, so I keep \(\mathsf D\) separate from \(\mathsf C\).

$$ a^{\lambda(n)}\equiv1\pmod n\qquad(\gcd(a,n)=1) $$

Compute before generalising

The middle display is intentionally dense: it is where signs, bounds, multiplicities, or normalising factors are most likely to be lost.

$$ \lambda(p^k)=\varphi(p^k)\ (p\text{ odd}),\qquad\lambda(2^k)=\begin{cases}1,&k=1,\\2,&k=2,\\2^{k-2},&k\ge3.\end{cases} $$

The global view

The two-row display is also a debugging tool: if the conclusion changes when only notation changes, some hidden choice has entered the argument.

$$ \begin{aligned} \mathsf{D}\;&:\quad \lambda(n)=\exp\bigl((\mathbf Z/n\mathbf Z)^\times\bigr),\\[5pt] \mathsf{C}\;&:\quad a^{\lambda(n)}\equiv1\pmod n\qquad(\gcd(a,n)=1). \end{aligned} $$

Edge conditions

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] a^{\lambda(n)}\equiv1\pmod n\qquad(\gcd(a,n)=1) \end{gathered}} $$

The notation is dense, but it is doing honest work: every delimiter records scope and every index records dependence. Removing one should require a mathematical reason.

This article was posted on Wed 28 December 2011. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.