units-mod-n-coprime-and-totient

Sun Sep 13 2026

Start with n = 6

Which of 1 to 5 have an inverse mod 6? Multiply and look for a 1. Since $1 \cdot 1 = 1$ and $5 \cdot 5 = 25 \equiv 1$, both 1 and 5 are units. The residue 1 is a unit for every $n$ and is its own inverse, since $\gcd(1, n) = 1$. The other three never reach 1: $2 \cdot 3 = 6 \equiv 0$, $3 \cdot 2 \equiv 0$, $4 \cdot 3 = 12 \equiv 0$. Once a product hits 0 the row of products just cycles.

The rule is not "$n$ divides $a$": 6 does not divide 4, and 4 still fails. The rule is that $a$ and $n$ share a factor. 4 shares the factor 2 with 6, and a shared factor is enough to kill the inverse.

An inverse is a combination equal to 1

Write out what an inverse means. $a k \equiv 1 \pmod n$ says $a k = 1 + q n$ for some integer $q$, so

$a k - q n = 1 .$

So "does $a$ have an inverse" is the same question as "can I build 1 out of $a$ and $n$ with integer coefficients". Bézout's identity is the name for the fact that the smallest positive number you can build this way is $\gcd(a, n)$. The two directions below are that identity, proved on the pair we care about.

Shared factor means no inverse

Let $d = \gcd(a, n)$ and write $a = k_1 d$, $n = k_2 d$. Then every combination is

$a k - n q = (k k_1 - q k_2)\, d .$

Every combination is a whole number of copies of $d$. If $d > 1$ the combination can never equal 1, so there is no inverse. That is the "only if" direction.

Coprime means an inverse exists: run Euclid backwards

Take $a = 5$ and $n = 12$. Divide with remainder, then divide the divisor by the remainder, until the remainder is 0:

The last nonzero remainder is 1, and the goal is to write that 1 as a combination of 12 and 5. The first equation already does this for its own remainder: $2 = 12 - 2 \cdot 5$. The second equation contains that 2, so substitute, and its remainder 1 becomes a combination of 12 and 5 as well:

Reduce mod 12 and the $12 \cdot 2$ term vanishes: $5 \cdot 5 \equiv 1$, so 5 is its own inverse mod 12.

The general idea is a chain of substitutions. The first equation holds $a$, $n$ and a remainder. The remainder has coefficient 1 in its own equation, so solving for it writes the remainder as a combination of $a$ and $n$. Substitute that into the next equation, and its remainder is a combination of $a$ and $n$ too. Repeat down the chain. The last equation then reads $\gcd(a, n) = a x + n y$, and for coprime $a$ and $n$ that is $1 = a x + n y$, with $x$ the inverse. This is the extended Euclidean algorithm. Tracking $x$ and $y$ step by step, rather than by substitution, is the follow-up in extended-euclidean-algorithm-study.

Two claims carry this proof and both need checking: each Euclid step keeps the gcd, and the chain stops exactly at the gcd.

Each Euclid step keeps the gcd

One step is $a = q b + r$ with $0 \le r < b$. The claim is $\gcd(a, b) = \gcd(b, r)$.

First half. Let $d = \gcd(a, b)$, so $a = k_1 d$ and $b = k_2 d$. Picture a strip of length $a$ cut into $q$ segments of length $b$ and a leftover of length $r$. The block $d$ tiles the whole strip and tiles each $b$ segment, so it must tile the leftover:

$r = a - q b = (k_1 - q k_2)\, d .$

So $d$ is a common divisor of $b$ and $r$, and that is all it is so far. The block $d$ is the greatest common divisor of $(a, b)$. Nothing above says it is the greatest common divisor of $(b, r)$, only that it is a factor of both. Being the gcd of the first pair does not make it the gcd of the second. What this half proves is $\gcd(a, b) \le \gcd(b, r)$.

Second half. Take any $e$ dividing both $b$ and $r$, say $b = e m_1$ and $r = e m_2$. Then

$a = q b + r = e\,(q m_1 + m_2),$

so $e$ divides $a$ as well. Every common divisor of $(b, r)$ is a common divisor of $(a, b)$, which gives $\gcd(b, r) \le \gcd(a, b)$. The two inequalities together give equality. The trap in the one-sided version is its own note: euclid-step-keeps-gcd.

Why the chain stops at the gcd

The remainders are non-negative and strictly decreasing, since $r < b$ at every step, so the chain reaches 0 after finitely many steps. The last line reads $r_{k-1} = q \cdot r_k + 0$, and $\gcd(r_k, 0) = r_k$, because every integer divides 0. Chain the lemma back up the lines and $\gcd(a, n) = \gcd(r_k, 0) = r_k$. The last nonzero remainder is the gcd. When $a$ and $n$ are coprime that remainder is 1, which is exactly what the back-substitution builds.

The answer to the opening question

For prime $p$ the only divisors are 1 and $p$, so every residue from 1 to $p - 1$ is coprime to $p$ and has an inverse. That is why $\mathbb{Z}_p$ is a field. For composite $n$, exactly the residues that share a factor with $n$ drop out. Mod 6, that is 2, 3 and 4, and the survivors are 1 and 5.

The units form a group

Closure is the claim to check: if $a$ and $b$ are units, so is $a b$. Two different closures are in play, and keeping them apart is the whole proof.

The first is closure of the ring. Both $a^{-1}$ and $b^{-1}$ are elements of $\mathbb{Z}/n\mathbb{Z}$, and a ring is closed under multiplication, so the product $b^{-1} a^{-1}$ is guaranteed to exist as an element of $\mathbb{Z}/n\mathbb{Z}$. The ring hands over the candidate inverse for free.

The second is closure of the unit group, which is the thing to prove. A unit is an element with some inverse in the ring, so check the candidate:

So $a b$ has an inverse in the ring, which makes $a b$ a unit. That is unit-group closure, proved from ring closure plus one computation. Nothing here needed $b^{-1} a^{-1}$ to be a unit itself. Reaching for that fact is the circular step, because it is unit-group closure again.

The identity is 1, inverses exist by the definition of a unit, and associativity is inherited from the ring. So $(\mathbb{Z}/n\mathbb{Z})^\times$ is a group.

How many units: φ(n)

Euler's totient $\varphi(n)$ counts the integers in $1$ to $n$ that are coprime to $n$, so $|(\mathbb{Z}/n\mathbb{Z})^\times| = \varphi(n)$, and $\varphi(p) = p - 1$ for a prime.

Count $n = 15 = 3 \cdot 5$ by removing the failures. Count over 1 to 15 rather than 1 to 14, so that every count is exact and 15 itself lands in the removed pile where it belongs. The multiples of 3 number $15/3 = 5$, the multiples of 5 number $15/5 = 3$, and 15 was removed twice, so add it back once:

$\varphi(15) = 15 - \tfrac{15}{3} - \tfrac{15}{5} + \tfrac{15}{15} = 8 .$

The eight units mod 15 are 1, 2, 4, 7, 8, 11, 13, 14. The same count for any two distinct primes gives $\varphi(pq) = pq - q - p + 1 = (p - 1)(q - 1)$.

The general formula runs over the distinct primes dividing $n$:

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

The way to remember it: for each prime $p$ there are exactly $n/p$ multiples to throw out. Start from $n$, subtract each $n/p$, add back each $n/(pq)$ that was subtracted twice, and so on. Multiplying out the product produces exactly those signed terms, one per subset of the primes. Check: $15 \cdot \tfrac{2}{3} \cdot \tfrac{4}{5} = 8$. For $9$ there is only one prime and nothing to double count, so $\varphi(9) = 9 - 3 = 6$.

Open threads

• $\varphi(p^k)$, with 27 as the test case: which residues fail, how many, and the closed form.
• The term-by-term match between expanding $\prod (1 - 1/p_i)$ and inclusion-exclusion for three or more primes. Sketched in the session, not re-derived.
• Tracking the Bézout coefficients step by step instead of by substitution: extended-euclidean-algorithm-study.