Chapter 5 · Combinatorics and Number Theory

5.3 Euler’s φ-Function and Primitive Roots

Euler's $\varphi$-function counts the invertible residues modulo $n$: it is multiplicative, sums to $n$ over the divisors, and gives Euler's theorem. Orders, primitive roots (which exist only for $1,2,4,p^k,2p^k$), indices, quadratic residues and the arithmetic functions $\tau,\sigma,\mu$ complete the picture.

In §5.2 we saw that $a$ is invertible modulo $n$ exactly when $\gcd(a,n)=1$, and that modulo a prime every nonzero residue $a$ satisfies $a^{p-1}\equiv1$. This section answers the natural follow-up questions. How many invertible residues are there modulo $n$? (Euler's function $\varphi(n)$.) Is there a universal exponent that sends all of them to $1$? (Euler's theorem: $\varphi(n)$ works.) What is the smallest exponent for a given $a$, and is there a single residue $g$ whose powers produce every invertible residue — a primitive root? The answer to the last question is surprisingly delicate: primitive roots exist modulo $7$, $9$, $25$ and $50$, but not modulo $8$, $12$ or $15$.

In the language of Chapter 6, the invertible residues form a finite abelian group $U_n$ of order $\varphi(n)$, Euler's theorem is Lagrange's theorem for this group, the order of $a$ modulo $n$ is its order as a group element, and "$n$ has a primitive root" means "$U_n$ is cyclic". Keeping both languages in view pays off: CSIR NET asks for $\varphi(n)$, last digits of huge powers, the number of primitive roots, the number of solutions of $x^k\equiv a$, $|\operatorname{Aut}(\mathbb{Z}_n)|=\varphi(n)$, the number of generators of a cyclic group, and the values of $\tau$, $\sigma$ and $\mu$ — all of it in this section.

Euler's $\varphi$-Function

📘 Definition 5.10 — Reduced residues and Euler's function

For $n\ge1$, Euler's function (the totient) is $$\varphi(n)=\#\{k:\ 1\le k\le n,\ \gcd(k,n)=1\}.$$ A reduced residue system modulo $n$ is a set of $\varphi(n)$ integers, pairwise incongruent mod $n$, each coprime to $n$ — one from each invertible class. The invertible classes form the set $U_n=\{\bar a\in\mathbb{Z}_n:\ \gcd(a,n)=1\}$ (also written $\mathbb{Z}_n^{\times}$), which is closed under multiplication.

Small values: $\varphi(1)=1$, $\varphi(2)=1$, $\varphi(3)=2$, $\varphi(4)=2$, $\varphi(5)=4$, $\varphi(6)=2$, $\varphi(7)=6$, $\varphi(8)=4$, $\varphi(9)=6$, $\varphi(10)=4$, $\varphi(12)=4$.

📐 Theorem 5.37 — Prime powers
For a prime $p$ and $k\ge1$, $\ \varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)$. In particular $\varphi(p)=p-1$; and $\varphi(n)=n-1$ if and only if $n$ is prime.

Proof. An integer $k$ is coprime to $p^k$ iff $p\nmid k$. Among $1,\dots,p^k$ the multiples of $p$ are $p,2p,\dots,p^{k-1}\cdot p$ — there are $p^{k-1}$ of them — and the rest are coprime. If $n\gt1$ is composite it has a divisor $a$ with $1\lt a\lt n$, and then $a$ and $n$ are two numbers in $\{1,\dots,n\}$ not coprime to $n$, so $\varphi(n)\le n-2$. ∎

📐 Theorem 5.38 — $\varphi$ is multiplicative
If $\gcd(m,n)=1$ then $\varphi(mn)=\varphi(m)\,\varphi(n)$. More precisely, the Chinese Remainder map $\bar x\mapsto(x\bmod m,\ x\bmod n)$ restricts to a bijection $U_{mn}\to U_m\times U_n$ that preserves multiplication.

Proof. By the Chinese Remainder Theorem (§5.2) the map $\mathbb{Z}_{mn}\to\mathbb{Z}_m\times\mathbb{Z}_n$ is a bijection preserving products. Now $\gcd(x,mn)=1$ iff $\gcd(x,m)=1$ and $\gcd(x,n)=1$ (a prime dividing $mn$ divides $m$ or $n$), and $\gcd(x,m)=\gcd(x\bmod m,\ m)$. So $\bar x\in U_{mn}$ iff its image lies in $U_m\times U_n$, and the restricted map is still a bijection. Counting both sides gives $\varphi(mn)=\varphi(m)\varphi(n)$. ∎

📐 Theorem 5.39 — The product formula
If $n=p_1^{a_1}\cdots p_r^{a_r}$ (distinct primes, $a_i\ge1$), then $$\varphi(n)=\prod_{i=1}^{r}p_i^{a_i-1}(p_i-1)=n\prod_{p\mid n}\left(1-\frac1p\right).$$

Proof. The prime powers $p_i^{a_i}$ are pairwise coprime, so Theorem 5.38 (with induction on $r$) and Theorem 5.37 give the first product; factoring $p_i^{a_i}$ out of each term gives the second. Second proof by inclusion–exclusion (§5.1): let $A_i$ be the set of multiples of $p_i$ in $\{1,\dots,n\}$; then $|A_{i_1}\cap\cdots\cap A_{i_s}|=n/(p_{i_1}\cdots p_{i_s})$, and $$\varphi(n)=n-\sum_i\frac{n}{p_i}+\sum_{i\lt j}\frac{n}{p_ip_j}-\cdots,$$ which is the expansion of $n\prod(1-1/p_i)$. ∎

The formula shows that $\varphi(n)/n$ depends only on which primes divide $n$, not on their exponents: $\varphi(n)/n=\tfrac12$ for every power of $2$, $\tfrac13$ for every $n=2^a3^b$ ($a,b\ge1$).

📐 Theorem 5.40 — Gauss's divisor-sum identity
For every $n\ge1$, $$\sum_{d\mid n}\varphi(d)=n,$$ the sum running over the positive divisors $d$ of $n$.

Proof. Write each of the $n$ fractions $\tfrac1n,\tfrac2n,\dots,\tfrac nn$ in lowest terms, $\tfrac kn=\tfrac ad$ with $d\mid n$, $1\le a\le d$ and $\gcd(a,d)=1$ (here $d=n/\gcd(k,n)$). Conversely every such $\tfrac ad$ equals $\tfrac kn$ for exactly one $k$, namely $k=a\cdot\tfrac nd$. So the $n$ fractions are partitioned according to their reduced denominator $d$, and exactly $\varphi(d)$ of them have denominator $d$. Counting the fractions in two ways gives $n=\sum_{d\mid n}\varphi(d)$. ∎

For $n=12$: the divisors $1,2,3,4,6,12$ contribute $1+1+2+2+2+4=12$. Interactive 1 below shows the fractions sorting themselves by denominator. In group language: a cyclic group of order $n$ has exactly $\varphi(d)$ elements of order $d$ for each $d\mid n$, and counting all elements gives the same identity (§6.1). That is how the identity will be used to prove the existence of primitive roots.

📐 Theorem 5.41 — Further properties of $\varphi$
  1. $\varphi(n)$ is even for $n\ge3$, and for $n\ge2$ the integers in $[1,n]$ coprime to $n$ have sum $\tfrac12n\varphi(n)$.
  2. For all $m,n$, with $d=\gcd(m,n)$: $\ \varphi(mn)=\varphi(m)\varphi(n)\dfrac{d}{\varphi(d)}$. So $\varphi(mn)\ge\varphi(m)\varphi(n)$, with equality iff $\gcd(m,n)=1$.
  3. If $m\mid n$ then $\varphi(m)\mid\varphi(n)$.

Proof. (1) If $\gcd(k,n)=1$ then $\gcd(n-k,n)=1$, and $k\ne n-k$ because $k=n/2$ would give $\gcd(k,n)=n/2\gt1$ when $n\gt2$. So the coprime residues come in pairs $\{k,n-k\}$; there is an even number of them, and each pair sums to $n$, giving the sum $\tfrac n2\varphi(n)$ (for $n=2$ the only term is $1=\tfrac12\cdot2\cdot1$).

(2) By the product formula, $\varphi(mn)/(mn)=\prod_{p\mid mn}(1-\tfrac1p)$. A prime dividing $mn$ divides $m$ or $n$, and it is counted twice in $\prod_{p\mid m}\prod_{p\mid n}$ exactly when it divides $d$. So $\tfrac{\varphi(mn)}{mn}\cdot\tfrac{\varphi(d)}{d}=\tfrac{\varphi(m)}m\cdot\tfrac{\varphi(n)}n$, which rearranges to the formula. Since $\varphi(d)\le d$ with equality iff $d=1$, the inequality follows.

(3) Every prime dividing $m$ divides $n$, with exponent $b_p\le a_p$; so $\varphi(m)=\prod_{p\mid m}p^{b_p-1}(p-1)$ divides $\prod_{p\mid n}p^{a_p-1}(p-1)=\varphi(n)$. ∎

✏️ Example 1 — Computing $\varphi$ and inverting it
(a) Compute $\varphi(1000)$, $\varphi(7!)$ and $\varphi(1001)$. (b) Find all $n$ with $\varphi(n)=12$.
(a) $1000=2^3\cdot5^3$: $\varphi=1000\cdot\tfrac12\cdot\tfrac45=400$. $\ 7!=5040=2^4\cdot3^2\cdot5\cdot7$: $\varphi=2^3\cdot(3\cdot2)\cdot4\cdot6=1152$. $\ 1001=7\cdot11\cdot13$: $\varphi=6\cdot10\cdot12=720$.
(b) Which primes? If $p\mid n$ then $p-1=\varphi(p)$ divides $\varphi(n)=12$ (Theorem 5.41(3)), so $p-1\in\{1,2,3,4,6,12\}$, i.e. $p\in\{2,3,5,7,13\}$ ($4$ is not prime).
Which prime powers? $\varphi(p^a)=p^{a-1}(p-1)$ must divide $12$. The candidates and their $\varphi$-values are: $2\mapsto1$, $4\mapsto2$, $8\mapsto4$; $\ 3\mapsto2$, $9\mapsto6$; $\ 5\mapsto4$; $\ 7\mapsto6$; $\ 13\mapsto12$. We need coprime prime powers whose $\varphi$-values multiply to $12$.
List Since $3$ is not a value of $\varphi$, the factorisations of $12$ into values are $12$ and $6\cdot2$ (with an optional factor $\varphi(2)=1$). $12$: $13$, and $2\cdot13=26$. $6\cdot2$: a $6$ from $7$ or $9$, a $2$ from $3$ or $4$: $7\cdot3=21$, $7\cdot4=28$, $9\cdot4=36$ ($9\cdot3$ is not a coprime product); adding the factor $2$ where no power of $2$ is present yet: $2\cdot21=42$. Answer: $n\in\{13,21,26,28,36,42\}$.
Check $\varphi(21)=2\cdot6$, $\varphi(26)=1\cdot12$, $\varphi(28)=2\cdot6$, $\varphi(36)=2\cdot6$, $\varphi(42)=1\cdot2\cdot6$ — all $12$ ✓.
✏️ Example 2 — Properties of $\varphi$: prove or disprove
Prove or disprove: (a) the equation $\varphi(n)=14$ has a solution; (b) $\varphi(n)=n/2$ if and only if $n$ is a power of $2$ (with $n\ge2$); (c) if $\varphi(m)\mid\varphi(n)$ then $m\mid n$; (d) $\varphi(2n)=\varphi(n)$ for every odd $n$; (e) $\varphi(n)\to\infty$ as $n\to\infty$.
(a) False If $p\mid n$ then $p-1\mid14$, so $p\in\{2,3\}$ ($p-1\in\{1,2,7,14\}$ and $8$, $15$ are not prime). Then $n=2^a3^b$ and $\varphi(n)$ is a product of powers of $2$ and $3$, never $14=2\cdot7$. ($14$ is the smallest even "nontotient".)
(b) True $\varphi(2^k)=2^{k-1}$. Conversely, suppose $\prod_{p\mid n}(1-\tfrac1p)=\tfrac12$. If $2\mid n$ and some odd $q\mid n$, the product is at most $\tfrac12(1-\tfrac1q)\lt\tfrac12$. If $n$ is odd, $\prod(p-1)/\prod p=\tfrac12$ gives $2\prod(p-1)=\prod p$, with the left side even and the right side odd. So $n$ is a power of $2$.
(c) False $\varphi(3)=2$ divides $\varphi(5)=4$, but $3\nmid5$. (Theorem 5.41(3) has no converse.)
(d) True For odd $n$, $\gcd(2,n)=1$, so $\varphi(2n)=\varphi(2)\varphi(n)=\varphi(n)$. (For even $n$, Theorem 5.41(2) with $d=2$ gives $\varphi(2n)=2\varphi(n)$.)
(e) True For each $N$, $\varphi(n)\le N$ forces every prime factor $p$ of $n$ to satisfy $p-1\le N$, and every exponent $a$ to satisfy $p^{a-1}\le N$; only finitely many $n$ qualify. (Quantitatively, $\varphi(n)\ge\sqrt{n/2}$ — Exercise I.8.)
Interactive 1 — Gauss's Identity: Sorting $k/n$ by Denominator

The top grid shows the fractions $\tfrac1n,\tfrac2n,\dots,\tfrac nn$ reduced to lowest terms and coloured by their reduced denominator $d$. Every $d$ that appears divides $n$, and the fractions with denominator $d$ are exactly $\tfrac ad$ with $\gcd(a,d)=1$ — there are $\varphi(d)$ of them. The bars count each colour; together they make up all $n$ cells, which is $\sum_{d\mid n}\varphi(d)=n$. Drag $n$ or press Play; watch primes (one big bar of height $n-1$) and highly composite numbers.

n—
divisors of n—
φ(n)—
Σ φ(d) over d | n—

Euler's Theorem and the Order of an Element

📐 Theorem 5.42 — Euler's theorem
Let $n\ge1$ and $\gcd(a,n)=1$. Then $a^{\varphi(n)}\equiv1\pmod n$. (For $n=p$ prime this is Fermat's little theorem.)

Proof. Let $r_1,\dots,r_{\varphi(n)}$ be a reduced residue system. The numbers $ar_1,\dots,ar_{\varphi(n)}$ are again coprime to $n$ (a product of integers coprime to $n$ is coprime to $n$ — the consequences of Bézout's identity, §5.2) and pairwise incongruent ($ar_i\equiv ar_j$ implies $r_i\equiv r_j$ by cancelling the invertible $a$). So they form another reduced residue system, and $$a^{\varphi(n)}\,r_1r_2\cdots r_{\varphi(n)}\equiv r_1r_2\cdots r_{\varphi(n)}\pmod n.$$ The product $r_1\cdots r_{\varphi(n)}$ is coprime to $n$, so it can be cancelled. ∎

Group-theoretically: $U_n$ is a group of order $\varphi(n)$, and by Lagrange's theorem (§6.1) the order of every element divides $\varphi(n)$. The hypothesis $\gcd(a,n)=1$ is essential: $2^{\varphi(10)}=16\not\equiv1\pmod{10}$.

📘 Definition 5.11 — Order modulo $n$
Let $\gcd(a,n)=1$. The order of $a$ modulo $n$, written $\operatorname{ord}_n(a)$, is the least $h\ge1$ with $a^h\equiv1\pmod n$. It exists by Euler's theorem. (It is also called the multiplicative order or the exponent to which $a$ belongs.)
📐 Theorem 5.43 — Properties of the order
Let $\gcd(a,n)=1$ and $h=\operatorname{ord}_n(a)$.
  1. $a^k\equiv1\pmod n$ if and only if $h\mid k$. In particular $h\mid\varphi(n)$.
  2. $a^i\equiv a^j\pmod n$ if and only if $i\equiv j\pmod h$; so $1,a,a^2,\dots,a^{h-1}$ are pairwise incongruent.
  3. For $k\ge1$: $\ \operatorname{ord}_n(a^k)=\dfrac{h}{\gcd(h,k)}$.

Proof. (1) Write $k=hq+r$ with $0\le r\lt h$. Then $a^k=(a^h)^qa^r\equiv a^r$, which is $\equiv1$ iff $r=0$, by minimality of $h$. Euler's theorem and (1) give $h\mid\varphi(n)$. (2) Say $i\ge j$; $a$ is invertible, so $a^i\equiv a^j\iff a^{i-j}\equiv1\iff h\mid i-j$. (3) Let $g=\gcd(h,k)$. By (1), $(a^k)^t\equiv1\iff h\mid kt\iff\tfrac hg\mid\tfrac kg\,t\iff\tfrac hg\mid t$, the last step because $\gcd(\tfrac hg,\tfrac kg)=1$. The least such $t\ge1$ is $h/g$. ∎

📐 Theorem 5.44 — Order of a product
If $\operatorname{ord}_n(a)=h$, $\operatorname{ord}_n(b)=k$ and $\gcd(h,k)=1$, then $\operatorname{ord}_n(ab)=hk$.

Proof. $(ab)^{hk}=(a^h)^k(b^k)^h\equiv1$. Conversely if $(ab)^t\equiv1$, raise to the power $h$: $b^{ht}\equiv(ab)^{ht}\equiv1$, so $k\mid ht$ and hence $k\mid t$ (Euclid's lemma). Symmetrically $h\mid t$, so $hk\mid t$ (coprime divisors). ∎

The coprimality is needed: $\operatorname{ord}(a)=\operatorname{ord}(a^{-1})$, but $\operatorname{ord}(a\cdot a^{-1})=1$. The smallest exponent that works for every unit mod $n$ is the Carmichael function $\lambda(n)=\max_a\operatorname{ord}_n(a)$; it divides $\varphi(n)$ and can be much smaller: $\lambda(65)=\operatorname{lcm}(\varphi(5),\varphi(13))=12$ while $\varphi(65)=48$.

✏️ Example 3 — Last digits and orders
(a) Find the last two digits of $7^{2026}$. (b) Find the last three digits of $2^{1000}$. (c) Find $\operatorname{ord}_{17}(2)$ and $\operatorname{ord}_{31}(2)$, and deduce $\operatorname{ord}_{527}(2)$, where $527=17\cdot31$.
(a) $7^2=49$, $7^4=2401\equiv1\pmod{100}$, so $\operatorname{ord}_{100}(7)=4$ (it divides $4$, and $7^2\not\equiv1$). Since $2026\equiv2\pmod4$, $7^{2026}\equiv7^2=49$: the last two digits are $49$. (Euler's theorem alone gives the exponent $\varphi(100)=40$ and $2026\equiv26\pmod{40}$ — correct but slower: the order is the efficient exponent.)
(b) $\gcd(2,1000)\ne1$, so split $1000=8\cdot125$. Mod $8$: $2^{1000}\equiv0$. Mod $125$: $\varphi(125)=100$ and $2^{1000}=(2^{100})^{10}\equiv1$. CRT: $x\equiv0\pmod8$, $x\equiv1\pmod{125}$; the numbers $\equiv1\pmod{125}$ are $1,126,251,376,\dots$ and $376=8\cdot47$. Last three digits: $376$.
(c) $2^4=16\equiv-1\pmod{17}$, so $2^8\equiv1$ but $2^4\not\equiv1$: the order divides $8$ and not $4$, hence is $8$. $\ 2^5=32\equiv1\pmod{31}$ and $5$ is prime, so $\operatorname{ord}_{31}(2)=5$. By the CRT, $2^t\equiv1\pmod{527}$ iff $8\mid t$ and $5\mid t$, so $\operatorname{ord}_{527}(2)=\operatorname{lcm}(8,5)=40$ — although $\varphi(527)=16\cdot30=480$.
Rule $\operatorname{ord}_{mn}(a)=\operatorname{lcm}(\operatorname{ord}_m(a),\operatorname{ord}_n(a))$ for coprime $m,n$ — the CRT applied to $a^t\equiv1$.
✏️ Example 4 — Prime factors of Fermat numbers
Let $F_k=2^{2^k}+1$. Prove that every prime $p\mid F_k$ satisfies $p\equiv1\pmod{2^{k+1}}$. Use this to explain why only five trial divisors below $650$ are needed to search for a factor of $F_5=2^{32}+1$, and check that $641\mid F_5$.
Order $F_k$ is odd, so $p\ne2$. From $2^{2^k}\equiv-1\pmod p$ we get $2^{2^{k+1}}\equiv1$, so $h=\operatorname{ord}_p(2)$ divides $2^{k+1}$, i.e. $h=2^j$ with $j\le k+1$.
Exactly $2^{k+1}$ If $j\le k$ then $h\mid2^k$ and $2^{2^k}\equiv1$; together with $2^{2^k}\equiv-1$ this gives $p\mid2$, impossible. So $h=2^{k+1}$.
Conclusion $h\mid\varphi(p)=p-1$ (Theorem 5.43(1)), i.e. $p\equiv1\pmod{2^{k+1}}$.
$F_5$ Prime factors of $F_5$ are $\equiv1\pmod{64}$: below $650$ the candidates $64m+1$ that are prime are $193,257,449,577,641$. Euler (1732) found the factor: $641=5\cdot2^7+1=5^4+2^4$, so $5\cdot2^7\equiv-1$ and $5^4\equiv-2^4\pmod{641}$. Then $2^{32}=2^4\cdot2^{28}\equiv-5^4\cdot2^{28}=-(5\cdot2^7)^4\equiv-(-1)^4=-1$, i.e. $641\mid2^{32}+1$.

Primitive Roots

📘 Definition 5.12 — Primitive root
An integer $g$ with $\gcd(g,n)=1$ is a primitive root modulo $n$ if $\operatorname{ord}_n(g)=\varphi(n)$. Equivalently (Theorem 5.43(2)), the powers $g,g^2,\dots,g^{\varphi(n)}$ run through a complete reduced residue system modulo $n$, i.e. $U_n=\{\bar g^k\}$ is a cyclic group generated by $\bar g$.

Modulo $7$: the powers of $3$ are $3,2,6,4,5,1$ — all six units — so $3$ is a primitive root, while $2$ has powers $2,4,1$ and order $3$. Modulo $8$: $3^2\equiv5^2\equiv7^2\equiv1$, so every unit has order $\le2\lt\varphi(8)=4$ and there is no primitive root. The existence proof for primes rests on a polynomial fact that fails for composite moduli.

📐 Theorem 5.45 — Lagrange's theorem on polynomial congruences
Let $p$ be prime and $f(x)=c_dx^d+\cdots+c_0$ a polynomial with integer coefficients and $p\nmid c_d$. Then $f(x)\equiv0\pmod p$ has at most $d$ solutions modulo $p$.

Proof. Induction on $d$; for $d=0$, $f=c_0\not\equiv0$ has no roots. Let $d\ge1$ and suppose $f(r)\equiv0$. Polynomial division by $x-r$ gives $f(x)=(x-r)q(x)+f(r)$ with $q$ of degree $d-1$ and leading coefficient $c_d$. If $s\not\equiv r$ is another root, then $(s-r)q(s)\equiv0$, and as $p$ is prime and $p\nmid s-r$, $q(s)\equiv0$. By induction $q$ has at most $d-1$ roots, so $f$ has at most $1+(d-1)=d$. ∎

The primality of $p$ was used exactly once — to cancel $s-r$. Modulo $8$ the quadratic $x^2-1$ has four roots, so Lagrange's theorem fails for composite moduli (it is the statement "a polynomial over a field has at most $\deg$ roots", and $\mathbb{Z}_8$ is not a field).

📐 Theorem 5.46 — Primitive roots modulo a prime
Let $p$ be prime. For every divisor $d$ of $p-1$ there are exactly $\varphi(d)$ residues of order $d$ modulo $p$. In particular there are exactly $\varphi(p-1)$ primitive roots modulo $p$, and $U_p$ is cyclic.

Proof. For $d\mid p-1$ let $\psi(d)$ be the number of residues of order $d$. Every one of the $p-1$ units has some order $d$, and $d\mid p-1$, so $\sum_{d\mid p-1}\psi(d)=p-1$.

Claim: $\psi(d)\le\varphi(d)$. If $\psi(d)=0$ this is clear. Otherwise take $a$ of order $d$. The $d$ residues $1,a,\dots,a^{d-1}$ are distinct (Theorem 5.43(2)) and all are roots of $x^d-1$, since $(a^j)^d=(a^d)^j\equiv1$. By Lagrange's theorem $x^d-1$ has no other roots, so every element of order $d$ is some $a^j$, $0\le j\lt d$. By Theorem 5.43(3), $a^j$ has order $d/\gcd(d,j)$, which equals $d$ iff $\gcd(j,d)=1$. Hence $\psi(d)=\varphi(d)$ in this case.

Conclusion. By Gauss's identity, $\sum_{d\mid p-1}\varphi(d)=p-1=\sum_{d\mid p-1}\psi(d)$, and each $\psi(d)\le\varphi(d)$. So no inequality can be strict: $\psi(d)=\varphi(d)$ for every $d\mid p-1$. Taking $d=p-1$ gives $\varphi(p-1)\ge1$ primitive roots. ∎

📐 Theorem 5.47 — All primitive roots from one
Suppose $g$ is a primitive root modulo $n$. Then $g^k$ is a primitive root if and only if $\gcd(k,\varphi(n))=1$. Hence $n$ has exactly $\varphi(\varphi(n))$ primitive roots (incongruent mod $n$).

Proof. Every unit is $g^k$ for a unique $k\in\{1,\dots,\varphi(n)\}$, and $\operatorname{ord}(g^k)=\varphi(n)/\gcd(k,\varphi(n))$ by Theorem 5.43(3). This equals $\varphi(n)$ iff $\gcd(k,\varphi(n))=1$, which happens for $\varphi(\varphi(n))$ values of $k$. ∎

📐 Theorem 5.48 — Testing a primitive root
Let $\gcd(g,n)=1$. Then $g$ is a primitive root modulo $n$ if and only if $g^{\varphi(n)/q}\not\equiv1\pmod n$ for every prime $q$ dividing $\varphi(n)$.

Proof. If $g$ is a primitive root, no exponent smaller than $\varphi(n)$ gives $1$. Conversely, if $h=\operatorname{ord}_n(g)\lt\varphi(n)$, then $h$ is a proper divisor of $\varphi(n)$, so $\varphi(n)/h\gt1$ has a prime factor $q$, and $h\mid\varphi(n)/q$. Then $g^{\varphi(n)/q}\equiv1$. ∎

📐 Theorem 5.49 — Which moduli have primitive roots (Gauss)
A primitive root modulo $n$ exists if and only if $n\in\{1,2,4\}$ or $n=p^k$ or $n=2p^k$ with $p$ an odd prime and $k\ge1$. In group language: $U_n$ is cyclic exactly for these $n$.

Proof of "only if". Every other $n$ is either (i) $2^k$ with $k\ge3$, or (ii) $n=ab$ with $\gcd(a,b)=1$ and $a,b\gt2$. (If $n$ has two distinct odd prime factors, split off one prime power; if $n=2^kp^j$ with $k\ge2$, take $a=2^k\ge4$, $b=p^j\ge3$.)

(i) Every odd $x$ satisfies $x^{2^{k-2}}\equiv1\pmod{2^k}$ for $k\ge3$. For $k=3$: $x^2-1=(x-1)(x+1)$ is a product of consecutive even numbers, so $8\mid x^2-1$. If $x^{2^{k-2}}=1+2^kt$, squaring gives $x^{2^{k-1}}=1+2^{k+1}t+2^{2k}t^2\equiv1\pmod{2^{k+1}}$. So every order is at most $2^{k-2}\lt\varphi(2^k)=2^{k-1}$.

(ii) For $a,b\gt2$ both $\varphi(a)$ and $\varphi(b)$ are even (Theorem 5.41(1)), so $e=\tfrac12\varphi(a)\varphi(b)=\tfrac12\varphi(n)$ is a multiple of $\varphi(a)$ and of $\varphi(b)$. For a unit $x$, Euler gives $x^e\equiv1\pmod a$ and $\pmod b$, hence $\pmod n$. So every order is at most $\varphi(n)/2$.

Sketch of "if". $n=1,2,4$: take $g=1$ (or $0$), $1$, $3$. Primes: Theorem 5.46. For $p^2$: let $g$ be a primitive root mod $p$. If $g^{p-1}\equiv1\pmod{p^2}$, replace $g$ by $g+p$; by the binomial theorem $(g+p)^{p-1}\equiv g^{p-1}+(p-1)g^{p-2}p$, which is $\equiv1-pg^{p-2}\not\equiv1\pmod{p^2}$. Now $\operatorname{ord}_{p^2}(g)$ is a multiple of $p-1$ (reducing mod $p$), divides $\varphi(p^2)=p(p-1)$, and is not $p-1$; so it is $p(p-1)$. An induction with the binomial theorem shows that the same $g$ is a primitive root mod every $p^k$. Finally, for $2p^k$ choose the odd one of $g$ and $g+p^k$: it is a primitive root mod $2p^k$ because $\varphi(2p^k)=\varphi(p^k)$ and $U_{2p^k}\cong U_2\times U_{p^k}$ with $U_2$ trivial. ∎

✏️ Example 5 — Finding and counting primitive roots
(a) Find all primitive roots modulo $13$. (b) Find the least primitive root modulo $41$, and the number of primitive roots. (c) Show that $2$ is a primitive root modulo $25$; find a primitive root modulo $50$ and the number of primitive roots modulo $50$. (d) Show that there is no primitive root modulo $15$.
(a) $\varphi(13)=12=2^2\cdot3$, so test $g^{6}$ and $g^{4}$ (Theorem 5.48). For $g=2$: $2^4=16\equiv3$, $2^6=64\equiv12\equiv-1$; neither is $1$, so $2$ is a primitive root. By Theorem 5.47 the primitive roots are $2^k$ with $\gcd(k,12)=1$, $k=1,5,7,11$: $2$, $2^5=32\equiv6$, $2^7=128\equiv11$, $2^{11}\equiv2^{-1}\equiv7$. Answer $\{2,6,7,11\}$ — $\varphi(12)=4$ of them.
(b) $\varphi(41)=40=2^3\cdot5$: test $g^{20}$ and $g^{8}$. $2^{10}=1024=24\cdot41+40\equiv-1$, so $2^{20}\equiv1$: no. $3^4=81\equiv-1$, so $3^8\equiv1$: no. $4=2^2$ and $5$: $5^4=625\equiv10$, $5^8\equiv100\equiv18$, $5^{16}\equiv18^2=324\equiv37$, $5^{20}\equiv37\cdot10=370\equiv1$: no. $6$: $6^2\equiv-5$, $6^4\equiv25$, $6^8\equiv625\equiv10\ne1$, $6^{16}\equiv100\equiv18$, $6^{20}\equiv18\cdot25=450\equiv40\equiv-1\ne1$. So $6$ is the least primitive root, and there are $\varphi(40)=16$.
(c) $\varphi(25)=20=2^2\cdot5$: $2^{10}=1024\equiv24\equiv-1\pmod{25}$ and $2^4=16$; neither is $1$, so $2$ is a primitive root mod $25$. Modulo $50=2\cdot25$, $2$ is not a unit, but $2+25=27$ is odd and is a primitive root (proof of Theorem 5.49). Number: $\varphi(\varphi(50))=\varphi(20)=8$.
(d) $15=3\cdot5$ is of type (ii) in Theorem 5.49: for every unit $x$, $x^2\equiv1\pmod3$ and $x^4\equiv1\pmod5$, so $x^4\equiv1\pmod{15}$, while $\varphi(15)=8$. Indeed the orders of $1,2,4,7,8,11,13,14$ are $1,4,2,4,4,2,4,2$.
Interactive 2 — Powers of $g$ Around the Units Modulo $n$

The $\varphi(n)$ units modulo $n$ sit on a circle. Starting at $1$, each step multiplies by $g$: the path $1\to g\to g^2\to\cdots$ returns to $1$ after $\operatorname{ord}_n(g)$ steps. A primitive root visits every unit. The table counts the units of each order $d$ and compares with $\varphi(d)$: for $n$ with a primitive root (here $n=7,9,10,11,13,14,17,18,19,25,27$) the two columns agree, as in a cyclic group; for $n=15,16,20,21$ there is no element of order $\varphi(n)$.

φ(n)—
power—
ord(g)—
primitive root?—
number of primitive roots—

Indices, Power Residues and Quadratic Residues

A primitive root turns multiplication into addition, just as a logarithm does: if every unit is a power of $g$, multiplying units means adding exponents modulo $\varphi(n)$. This is the discrete logarithm, whose computational difficulty underlies the Diffie–Hellman key exchange.

📘 Definition 5.13 — Index (discrete logarithm)
Let $g$ be a primitive root modulo $n$ and $\gcd(a,n)=1$. The index of $a$ to the base $g$, $\operatorname{ind}_g(a)$, is the unique $k\in\{0,1,\dots,\varphi(n)-1\}$ with $g^k\equiv a\pmod n$.
📐 Theorem 5.50 — Laws of indices
For units $a,b$ modulo $n$ and $k\ge0$, all congruences of indices being modulo $\varphi(n)$:
  1. $\operatorname{ind}_g(ab)\equiv\operatorname{ind}_g(a)+\operatorname{ind}_g(b)$;
  2. $\operatorname{ind}_g(a^k)\equiv k\operatorname{ind}_g(a)$, and $\operatorname{ind}_g(1)=0$;
  3. for an odd prime $p$: $\operatorname{ind}_g(-1)=\tfrac{p-1}{2}$.

Proof. (1), (2): $g^{\operatorname{ind}a+\operatorname{ind}b}\equiv ab\equiv g^{\operatorname{ind}(ab)}$ and $g^{k\operatorname{ind}a}\equiv a^k$; apply Theorem 5.43(2) with $h=\varphi(n)$. (3) $x=g^{(p-1)/2}$ satisfies $x^2\equiv1$ and $x\not\equiv1$ (the order of $g$ is $p-1$), so $x\equiv-1$ because the only square roots of $1$ modulo a prime are $\pm1$ (§5.2, Fermat and Wilson). ∎

📐 Theorem 5.51 — $k$-th power residues modulo a prime
Let $p$ be prime, $p\nmid a$, $k\ge1$ and $d=\gcd(k,p-1)$. The congruence $x^k\equiv a\pmod p$ is solvable if and only if $a^{(p-1)/d}\equiv1\pmod p$, and then it has exactly $d$ solutions. Consequently exactly $(p-1)/d$ of the $p-1$ units are $k$-th powers.

Proof. Fix a primitive root $g$ and write $x\equiv g^y$, $a\equiv g^{s}$ with $s=\operatorname{ind}_ga$. Then $x^k\equiv a$ iff $ky\equiv s\pmod{p-1}$ — a linear congruence in $y$, solvable iff $d\mid s$, with exactly $d$ solutions mod $p-1$ (the theorem on linear congruences, §5.2), giving $d$ distinct $x$. Finally $a^{(p-1)/d}=g^{s(p-1)/d}\equiv1$ iff $p-1\mid s(p-1)/d$ iff $d\mid s$. The $k$-th powers are the $g^s$ with $d\mid s$: $(p-1)/d$ of them. ∎

📘 Definition 5.14 — Quadratic residues and the Legendre symbol
Let $p$ be an odd prime and $p\nmid a$. Then $a$ is a quadratic residue mod $p$ if $x^2\equiv a\pmod p$ is solvable, and a quadratic non-residue otherwise. The Legendre symbol is $$\left(\frac ap\right)=\begin{cases}1,&a\text{ a quadratic residue},\\-1,&a\text{ a non-residue},\\0,&p\mid a.\end{cases}$$
📐 Theorem 5.52 — Euler's criterion
Let $p$ be an odd prime. For every integer $a$, $$\left(\frac ap\right)\equiv a^{(p-1)/2}\pmod p.$$ Consequently: exactly $\tfrac{p-1}2$ of the units are quadratic residues, namely the even powers of a primitive root; and the symbol is multiplicative, $\left(\frac{ab}p\right)=\left(\frac ap\right)\left(\frac bp\right)$.

Proof. If $p\mid a$ both sides are $0$. Otherwise Theorem 5.51 with $k=2$, $d=\gcd(2,p-1)=2$ says $a$ is a residue iff $a^{(p-1)/2}\equiv1$. If $a$ is a non-residue, $y=a^{(p-1)/2}$ satisfies $y^2=a^{p-1}\equiv1$ and $y\not\equiv1$, so $y\equiv-1$ (square roots of $1$ modulo $p$ are $\pm1$, §5.2). The count $(p-1)/2$ and the description by even indices come from Theorem 5.51. Multiplicativity: both sides of $\left(\frac{ab}p\right)\equiv(ab)^{(p-1)/2}=a^{(p-1)/2}b^{(p-1)/2}$ are $\pm1$, and $1\not\equiv-1\pmod p$. ∎

So the product of two non-residues is a residue — as with signs, $(-1)(-1)=1$. Every primitive root is a non-residue (its index $1$ is odd), but not conversely: $-1$ is a non-residue mod $23$ of order $2$.

📐 Theorem 5.53 — $-1$, $2$ and quadratic reciprocity
Let $p\ne q$ be odd primes.
  1. $\left(\frac{-1}p\right)=(-1)^{(p-1)/2}$: $\ -1$ is a residue iff $p\equiv1\pmod4$.
  2. $\left(\frac2p\right)=(-1)^{(p^2-1)/8}$: $\ 2$ is a residue iff $p\equiv\pm1\pmod8$.
  3. Quadratic reciprocity (Gauss, 1796): $\left(\frac pq\right)\left(\frac qp\right)=(-1)^{\frac{p-1}2\cdot\frac{q-1}2}$. So $\left(\frac pq\right)=\left(\frac qp\right)$ unless $p\equiv q\equiv3\pmod4$, when $\left(\frac pq\right)=-\left(\frac qp\right)$.

Proof of (1). Euler's criterion with $a=-1$ (this is also the theorem "when is $-1$ a square modulo $p$?" of §5.2). Parts (2) and (3) are quoted; their standard proofs use Gauss's lemma, which counts how many of $a,2a,\dots,\frac{p-1}2a$ have least absolute residue negative. ∎

✏️ Example 6 — Index tables and Legendre symbols
(a) Make the table of indices modulo $13$ to the base $2$, and use it to solve $x^3\equiv5\pmod{13}$ and $7^x\equiv6\pmod{13}$. List the quadratic residues modulo $13$. (b) Is $x^2\equiv19\pmod{43}$ solvable? (c) How many solutions does $x^4\equiv1\pmod{13}$ have, and how many $x^6\equiv5\pmod{13}$?
Table Powers of $2$ mod $13$: $2^0,\dots,2^{11}\equiv1,2,4,8,3,6,12,11,9,5,10,7$. Inverting:
$a$123456789101112
$\operatorname{ind}_2a$01429511381076
$x^3\equiv5$ Taking indices: $3\operatorname{ind}x\equiv\operatorname{ind}5=9\pmod{12}$. Here $\gcd(3,12)=3\mid9$: three solutions, $\operatorname{ind}x\equiv3\pmod4$, i.e. $\operatorname{ind}x\in\{3,7,11\}$, so $x\equiv8,11,7$. Check: $8^3=512=39\cdot13+5$ ✓.
$7^x\equiv6$ $x\operatorname{ind}7\equiv\operatorname{ind}6$: $11x\equiv5\pmod{12}$; $11\equiv-1$, so $x\equiv-5\equiv7\pmod{12}$. Check: $7^7\equiv(2^{11})^7=2^{77}\equiv2^{77-72}=2^5\equiv6$ ✓. Quadratic residues = even indices: $\{1,4,3,12,9,10\}=\{1,3,4,9,10,12\}$.
(b) $19$ and $43$ are primes $\equiv3\pmod4$, so $\left(\frac{19}{43}\right)=-\left(\frac{43}{19}\right)=-\left(\frac{5}{19}\right)$. Since $5\equiv1\pmod4$: $\left(\frac5{19}\right)=\left(\frac{19}5\right)=\left(\frac45\right)=1$. Hence $\left(\frac{19}{43}\right)=-1$: not solvable.
(c) $x^4\equiv1$: $d=\gcd(4,12)=4$ and $1^{3}\equiv1$, so $4$ solutions ($x\equiv1,5,8,12$: indices $0,3,6,9$). $\ x^6\equiv5$: $d=\gcd(6,12)=6$; test $5^{12/6}=25\equiv12\not\equiv1$, so no solution (equivalently $6\nmid\operatorname{ind}5=9$).

Multiplicative Functions: $\tau$, $\sigma$ and $\mu$

📘 Definition 5.15 — Multiplicative functions, $\tau$ and $\sigma$

An arithmetic function is a function $f:\mathbb{N}\to\mathbb{C}$. It is multiplicative if $f(1)=1$ and $f(mn)=f(m)f(n)$ whenever $\gcd(m,n)=1$, and completely multiplicative if $f(mn)=f(m)f(n)$ for all $m,n$.

The divisor function $\tau(n)$ (also $d(n)$) is the number of positive divisors of $n$, and $\sigma(n)$ is their sum. Examples: $\varphi$, $\tau$, $\sigma$ are multiplicative but not completely ($\tau(4)=3\ne\tau(2)^2$); $f(n)=n^s$ is completely multiplicative.

📐 Theorem 5.54 — Divisor sums of multiplicative functions
If $f$ is multiplicative, so is $F(n)=\sum_{d\mid n}f(d)$. In particular, for $n=p_1^{a_1}\cdots p_r^{a_r}$, $$\tau(n)=\prod_{i=1}^{r}(a_i+1),$$ $$\sigma(n)=\prod_{i=1}^{r}\frac{p_i^{a_i+1}-1}{p_i-1}.$$

Proof. Let $\gcd(m,n)=1$. Every divisor $d$ of $mn$ factors uniquely as $d=d_1d_2$ with $d_1\mid m$, $d_2\mid n$ (namely $d_1=\gcd(d,m)$, $d_2=\gcd(d,n)$; compare exponents in the prime factorisations, §5.2), and conversely every such product divides $mn$. Since $\gcd(d_1,d_2)=1$, $$F(mn)=\sum_{d_1\mid m}\sum_{d_2\mid n}f(d_1)f(d_2)=F(m)F(n).$$ $\tau$ and $\sigma$ are the divisor sums of the multiplicative functions $1$ and $n$. On a prime power, $\tau(p^a)=a+1$ (divisors $1,p,\dots,p^a$) and $\sigma(p^a)=1+p+\cdots+p^a=\frac{p^{a+1}-1}{p-1}$; multiply. ∎

A number is perfect if $\sigma(n)=2n$: $6$, $28$, $496$, $8128$. Euclid proved that $2^{p-1}(2^p-1)$ is perfect whenever $2^p-1$ is prime (Exercise IV.7), and Euler proved that every even perfect number has this form; whether an odd perfect number exists is a famous open problem.

📘 Definition 5.16 — The Möbius function
$\mu(1)=1$; $\ \mu(n)=(-1)^r$ if $n$ is a product of $r$ distinct primes; $\ \mu(n)=0$ if $p^2\mid n$ for some prime $p$. Thus $\mu(30)=-1$, $\mu(15)=1$, $\mu(12)=0$. It is multiplicative.
📐 Theorem 5.55 — The basic Möbius sum
$$\sum_{d\mid n}\mu(d)=\begin{cases}1,&n=1,\\0,&n\gt1.\end{cases}$$

Proof. The sum is multiplicative (Theorem 5.54) and equals $1$ at $n=1$. At a prime power $p^a$ ($a\ge1$) it is $\mu(1)+\mu(p)+0+\cdots=1-1=0$. So for $n\gt1$ at least one factor of the product is $0$. ∎

📐 Theorem 5.56 — Möbius inversion
For arithmetic functions $f,F$, the relation $$F(n)=\sum_{d\mid n}f(d)\quad\text{for all }n$$ holds if and only if $$f(n)=\sum_{d\mid n}\mu(d)\,F\!\left(\frac nd\right)\quad\text{for all }n.$$ In particular Gauss's identity inverts to $\varphi(n)=\sum_{d\mid n}\mu(d)\,\dfrac nd$.

Proof. ($\Rightarrow$) Substitute and swap the order of summation over the pairs $(d,e)$ with $de\mid n$: $$\sum_{d\mid n}\mu(d)F\!\left(\tfrac nd\right)=\sum_{d\mid n}\mu(d)\sum_{e\mid n/d}f(e),$$ $$\sum_{d\mid n}\mu(d)\sum_{e\mid n/d}f(e)=\sum_{e\mid n}f(e)\sum_{d\mid n/e}\mu(d).$$ By Theorem 5.55 the inner sum is $0$ unless $n/e=1$, leaving $f(n)$. ($\Leftarrow$) Similarly, $\sum_{d\mid n}f(d)=\sum_{d\mid n}\sum_{e\mid d}\mu(e)F(d/e)$; putting $d=ek$, this is $\sum_{k\mid n}F(k)\sum_{e\mid n/k}\mu(e)=F(n)$. For the last claim take $F(n)=n$, $f=\varphi$ (Theorem 5.40). ∎

Expanding $\sum_{d\mid n}\mu(d)\tfrac nd$ over the squarefree $d$ gives $n\prod_{p\mid n}(1-\tfrac1p)$ — a third proof of the product formula, and exactly the inclusion–exclusion computation of Theorem 5.39.

✏️ Example 7 — $\tau$, $\sigma$, $\mu$ for $n=720$, and two proofs
(a) For $n=720$ find $\tau(n)$, $\sigma(n)$, the number of divisors that are perfect squares, and $\varphi(n)$ by Möbius inversion. (b) Prove that $\tau(n)$ is odd if and only if $n$ is a perfect square. (c) Is $\sigma$ completely multiplicative?
(a) $\tau,\sigma$ $720=2^4\cdot3^2\cdot5$. $\tau=5\cdot3\cdot2=30$. $\sigma=\tfrac{2^5-1}{1}\cdot\tfrac{3^3-1}{2}\cdot\tfrac{5^2-1}{4}=31\cdot13\cdot6=2418$ (so $720$ is abundant: $\sigma(n)\gt2n$).
Squares A divisor $2^a3^b5^c$ is a square iff $a,b,c$ are even: $a\in\{0,2,4\}$, $b\in\{0,2\}$, $c=0$ — $3\cdot2\cdot1=6$ square divisors ($1,4,16,9,36,144$).
$\varphi$ by inversion Only squarefree $d\mid720$ contribute: $d\in\{1,2,3,5,6,10,15,30\}$ with $\mu=1,-1,-1,-1,1,1,1,-1$. So $\varphi(720)=720-360-240-144+120+72+48-24=192$, agreeing with $720\cdot\tfrac12\cdot\tfrac23\cdot\tfrac45=192$.
(b) $\tau(n)=\prod(a_i+1)$ is odd iff every $a_i+1$ is odd iff every exponent $a_i$ is even iff $n$ is a square. (Pairing proof: divisors pair as $d\leftrightarrow n/d$, and the pair is a single divisor only when $d=\sqrt n$.)
(c) No $\sigma(4)=1+2+4=7$ but $\sigma(2)^2=9$. Multiplicativity holds only for coprime arguments.
⚠️ Counterexamples and pitfalls
  1. $\varphi$ is not completely multiplicative. $\varphi(4)=2\ne\varphi(2)^2=1$; in general $\varphi(mn)=\varphi(m)\varphi(n)\,d/\varphi(d)$ with $d=\gcd(m,n)$.
  2. $\varphi(n)=k$ may have no solution, or several. $\varphi(n)=14$ and $\varphi(n)=26$ have none (and no odd $k\gt1$ is a value); $\varphi(n)=12$ has six solutions.
  3. $\varphi(m)\mid\varphi(n)$ does not imply $m\mid n$. $\varphi(3)=2\mid4=\varphi(5)$.
  4. Euler's theorem needs $\gcd(a,n)=1$. $2^{\varphi(10)}=16\not\equiv1\pmod{10}$; for such $a$ split $n$ and use the CRT.
  5. $\varphi(n)$ is an exponent that works, not the order. $\operatorname{ord}_{100}(7)=4$ while $\varphi(100)=40$; the best universal exponent is $\lambda(n)$, e.g. $\lambda(65)=12$, $\varphi(65)=48$.
  6. Primitive roots need not exist. None modulo $8$, $12$, $15$, $16$, $20$, $21$, $24$: $U_8=\{1,3,5,7\}$ has every element of order $\le2$. They exist exactly for $1,2,4,p^k,2p^k$.
  7. A primitive root mod $p$ need not be one mod $p^2$. $14$ is a primitive root mod $29$, but $14^{28}\equiv1\pmod{29^2}$, so its order mod $841$ is $28\ne812$; then $14+29=43$ works.
  8. Non-residue $\ne$ primitive root. Mod $23$ there are $11$ non-residues but only $\varphi(22)=10$ primitive roots; $-1\equiv22$ is a non-residue of order $2$.
  9. Lagrange's root bound is for primes. $x^2\equiv1\pmod8$ has $4$ roots; $x^2\equiv1\pmod{15}$ has $4$.
  10. "Symbol $=1$" modulo a composite does not mean "square". The Jacobi symbol $\left(\frac2{15}\right)=\left(\frac23\right)\left(\frac25\right)=(-1)(-1)=1$, yet $x^2\equiv2\pmod{15}$ has no solution ($2$ is not a square mod $3$).
  11. Orders do not multiply in general. $\operatorname{ord}(a\cdot a^{-1})=1$; Theorem 5.44 needs coprime orders.
  12. Index arithmetic is modulo $\varphi(n)$, not $n$. In $x^3\equiv5\pmod{13}$ the index congruence is $3y\equiv9\pmod{12}$.
  13. $\mu(n)=0$ as soon as a square divides $n$; $\sum_{d\mid n}\mu(d)=0$ for all $n\gt1$, but $\sum_{d\mid n}|\mu(d)|=2^{r}$ ($r$ = number of distinct primes).

Exercises

I
Euler's function.
  • 1 Compute $\varphi(360)$, $\varphi(2^{10})$, $\varphi(10!)$ and $\varphi(2026)$.
  • 2 Find all $n$ with $\varphi(n)=6$ and all $n$ with $\varphi(n)=8$.
  • 3 Prove that $\varphi(n)=26$ has no solution.
  • 4 Find all $n$ with $\varphi(n)=\tfrac n3$.
  • 5 Prove that $\varphi(n)\mid n$ if and only if $n=1$, $n=2^a$ ($a\ge1$) or $n=2^a3^b$ ($a,b\ge1$).
  • 6 Find the sum of all integers in $[1,100]$ coprime to $100$.
  • 7 How many fractions $\tfrac ab$ with $1\le a\lt b\le10$ are in lowest terms?
  • 8 Prove that $\varphi(n)\ge\sqrt{n/2}$ for every $n\ge1$.
1 $360=2^3\cdot3^2\cdot5$: $\varphi=4\cdot6\cdot4=96$. $\varphi(2^{10})=2^9=512$. $10!=2^8\cdot3^4\cdot5^2\cdot7$: $\varphi=2^7\cdot54\cdot20\cdot6=829440$. $2026=2\cdot1013$ ($1013$ is prime): $\varphi=1012$.
2 $\varphi(n)=6$: primes with $p-1\mid6$ are $2,3,7$; $n\in\{7,9,14,18\}$. $\ \varphi(n)=8$: primes $2,3,5$ ($p-1\mid8$; $9$ is not prime), $n\in\{15,16,20,24,30\}$. Check: $\varphi(15)=2\cdot4$, $\varphi(16)=8$, $\varphi(20)=2\cdot4$, $\varphi(24)=4\cdot2$, $\varphi(30)=1\cdot2\cdot4$ ✓.
3 If $p\mid n$ then $p-1\mid26$, so $p-1\in\{1,2,13,26\}$, $p\in\{2,3\}$ ($14$, $27$ are not prime). Then $\varphi(n)$ is of the form $2^x3^y$, never $26=2\cdot13$.
4 We need $\prod_{p\mid n}\frac{p-1}{p}=\tfrac13$, i.e. $3\prod(p-1)=\prod p$. If $n$ is odd ($n\gt1$), the left side is even and the right side odd — impossible ($n=1$ gives $1\ne\tfrac13$). So $2\mid n$, and the odd primes satisfy $3\prod_{\text{odd}}(p-1)=2\prod_{\text{odd}}p$. The left side is divisible by $3$, so $3\mid n$; cancelling the factor for $p=3$ leaves $\prod_{p\ge5}(p-1)=\prod_{p\ge5}p$, which forces no further primes. Answer: $n=2^a3^b$ with $a,b\ge1$.
5 $\dfrac{n}{\varphi(n)}=\prod_{p\mid n}\dfrac p{p-1}$ must be an integer. With no odd prime: $n=2^a$ gives $2$ (and $n=1$ gives $1$). If $r\ge1$ odd primes divide $n$, the denominator $\prod(p-1)$ is divisible by $2^r$ while the numerator has at most one factor $2$; so $r=1$ and $2\mid n$, i.e. $n=2^ap^b$ with $\tfrac{2p}{p-1}$ an integer, forcing $p-1\mid2$, $p=3$.
6 Theorem 5.41(1): $\tfrac12\cdot100\cdot\varphi(100)=50\cdot40=2000$.
7 For each denominator $b$ there are $\varphi(b)$ reduced numerators $a\lt b$ (for $b\ge2$). $\sum_{b=2}^{10}\varphi(b)=1+2+2+4+2+6+4+6+4=31$.
8 By multiplicativity it suffices to bound each prime power. For odd $p$: $\varphi(p^a)=p^{a-1}(p-1)\ge p^{a-1}\sqrt p\ge p^{a/2}$, since $p-1\ge\sqrt p$ for $p\ge3$. For $p=2$: $\varphi(2^a)=2^{a-1}\ge2^{a/2}/\sqrt2$. Multiplying, $\varphi(n)\ge\sqrt n/\sqrt2$ (with equality at $n=2$).
II
Euler's theorem and orders.
  • 1 Find the last two digits of $17^{2026}$ and of $9^{9^9}$.
  • 2 Find $\operatorname{ord}_{19}(2)$ and $\operatorname{ord}_{100}(3)$.
  • 3 If $\operatorname{ord}_n(a)=12$, find $\operatorname{ord}_n(a^8)$, $\operatorname{ord}_n(a^9)$ and $\operatorname{ord}_n(a^5)$.
  • 4 Use Euler's theorem to find the inverse of $7$ modulo $30$.
  • 5 Show that $a^{12}\equiv1\pmod{65}$ for every $a$ coprime to $65$, although $\varphi(65)=48$.
  • 6 Prove that every odd prime divisor $p$ of $n^2+1$ satisfies $p\equiv1\pmod4$, and deduce that there are infinitely many primes $\equiv1\pmod4$.
  • 7 Let $p,q$ be odd primes with $q\mid2^p-1$. Prove that $q\equiv1\pmod{2p}$. Check with $2^{11}-1=23\cdot89$.
  • 8 Prove that $n\mid\varphi(a^n-1)$ for all integers $a\ge2$, $n\ge1$.
1 $\operatorname{ord}_{100}(17)=20$ ($17^2=289\equiv89$, $17^4\equiv89^2\equiv21$, $17^5\equiv21\cdot17=357\equiv57$, $17^{10}\equiv57^2\equiv49$, $17^{20}\equiv49^2\equiv1$). $2026\equiv6\pmod{20}$: $17^6=17^4\cdot17^2\equiv21\cdot89=1869\equiv69$. Last two digits $69$. For $9^{9^9}$: $9^5=59049\equiv49$, $9^{10}\equiv49^2\equiv1\pmod{100}$, so reduce the exponent mod $10$: $9^9\equiv(-1)^9\equiv9\pmod{10}$. Hence $9^{9^9}\equiv9^9=9^{10}\cdot9^{-1}\equiv9^{-1}\equiv89\pmod{100}$ ($9\cdot89=801$). Last two digits $89$.
2 $\operatorname{ord}_{19}(2)$ divides $18$; $2^6=64\equiv7$, $2^9\equiv7\cdot8=56\equiv-1$; neither $2^6$ nor $2^9$ is $1$, so the order is $18$ ($2$ is a primitive root mod $19$). $\operatorname{ord}_{100}(3)$: mod $4$ the order is $2$; mod $25$, $3^4=81\equiv6$, $3^5=243\equiv-7$, $3^{10}\equiv49\equiv-1$, so the order (a divisor of $20$, not dividing $4$ or $10$) is $20$; lcm $=20$.
3 Theorem 5.43(3): $12/\gcd(12,8)=3$, $12/\gcd(12,9)=4$, $12/\gcd(12,5)=12$.
4 $\varphi(30)=8$, so $7^{-1}\equiv7^7$. $7^2=49\equiv19$, $7^4\equiv361\equiv1\pmod{30}$, so $7^7\equiv7^3=7\cdot19=133\equiv13$. Check $7\cdot13=91\equiv1$ ✓.
5 $65=5\cdot13$; $a^4\equiv1\pmod5$ and $a^{12}\equiv1\pmod{13}$; $4\mid12$, so $a^{12}\equiv1$ modulo both, hence modulo $65$. ($\lambda(65)=12$.)
6 $n^2\equiv-1\pmod p$ gives $n^4\equiv1$ and $n^2\not\equiv1$ ($p\gt2$), so $\operatorname{ord}_p(n)=4$ divides $p-1$. If $p_1,\dots,p_k$ were all the primes $\equiv1\pmod4$, then $N=(2p_1\cdots p_k)^2+1$ is odd, and each prime factor of $N$ is $\equiv1\pmod4$ and different from every $p_i$ (as $p_i\mid N-1$). Contradiction.
7 $2^p\equiv1\pmod q$ and $p$ is prime, so $\operatorname{ord}_q(2)\in\{1,p\}$; it is not $1$ ($q\nmid1$), so it is $p$, and $p\mid q-1$. As $q-1$ is even and $p$ odd, $2p\mid q-1$. Check: $23=2\cdot11+1$, $89=4\cdot22+1$ ✓.
8 $\gcd(a,a^n-1)=1$ and $\operatorname{ord}_{a^n-1}(a)=n$ (since $a^n\equiv1$, and $0\lt a^k-1\lt a^n-1$ for $0\lt k\lt n$). The order divides $\varphi(a^n-1)$.
III
Primitive roots and indices.
  • 1 Find all primitive roots modulo $11$.
  • 2 Find the least primitive root of $19$ and of $23$.
  • 3 Show that there is no primitive root modulo $24$ by computing $x^2\bmod24$ for every unit $x$.
  • 4 How many primitive roots are there modulo $81$, $98$ and $2026$? Is there one modulo $100$?
  • 5 Let $g$ be a primitive root modulo an odd prime $p$. Prove that $g^{(p-1)/2}\equiv-1$ and that $g$ is a quadratic non-residue.
  • 6 Using indices to the base $2$ modulo $11$, solve $x^4\equiv3\pmod{11}$ and $3^x\equiv5\pmod{11}$.
  • 7 For which primes $p$ does $x^3\equiv a\pmod p$ have a solution for every $a$?
  • 8 Prove that the product of all primitive roots modulo a prime $p\ge5$ is $\equiv1\pmod p$.
  • 9 Show that $|\operatorname{Aut}(\mathbb{Z}_{n})|=\varphi(n)$ and that the number of generators of a cyclic group of order $n$ is $\varphi(n)$. For which $n$ is $\operatorname{Aut}(\mathbb{Z}_n)$ cyclic?
1 $\varphi(11)=10=2\cdot5$; test $g^5$ and $g^2$. $2^5=32\equiv-1$, $2^2=4$: $2$ is a primitive root. The others are $2^k$ with $\gcd(k,10)=1$: $2,2^3=8,2^7\equiv7,2^9\equiv6$. Answer $\{2,6,7,8\}$.
2 $19$: $2$ (Exercise II.2). $23$: $\varphi=22=2\cdot11$, test $g^{11}$ and $g^2$. $2^{11}=2048=89\cdot23+1$: no. $3^{11}$: $3^3=27\equiv4$, $3^9\equiv64\equiv18$, $3^{11}\equiv18\cdot9=162\equiv1$: no. $4=2^2$: no. $5$: $5^2\equiv2$, $5^{11}=5\cdot(5^2)^5\equiv5\cdot2^5=160\equiv22\equiv-1$; and $5^2\equiv2\ne1$. So $5$.
3 Units mod $24$: $1,5,7,11,13,17,19,23$; their squares are $1,25,49,121,169,289,361,529$, all $\equiv1\pmod{24}$. So every order is $\le2\lt\varphi(24)=8$.
4 $81=3^4$: $\varphi(\varphi(81))=\varphi(54)=18$. $98=2\cdot7^2$: $\varphi(\varphi(98))=\varphi(42)=12$. $2026=2\cdot1013$: $\varphi(1012)=\varphi(4\cdot11\cdot23)=2\cdot10\cdot22=440$. $100=4\cdot25$ is not of the form $1,2,4,p^k,2p^k$: none.
5 $x=g^{(p-1)/2}$ satisfies $x^2\equiv1$, $x\not\equiv1$, so $x\equiv-1$ (square roots of $1$ mod $p$, §5.2). By Euler's criterion $\left(\frac gp\right)\equiv g^{(p-1)/2}\equiv-1$.
6 Indices base $2$ mod $11$: $\operatorname{ind}3=8$, $\operatorname{ind}5=4$. $x^4\equiv3$: $4y\equiv8\pmod{10}$, $d=2$, $y\equiv2\pmod5$, $y\in\{2,7\}$, $x\equiv4,7$. Check $4^4=256=23\cdot11+3$ ✓. $\ 3^x\equiv5$: $8x\equiv4\pmod{10}$, $4x\equiv2\pmod5$, $x\equiv3\pmod5$: $x\equiv3,8\pmod{10}$. Check $3^3=27\equiv5$ ✓ (and $\operatorname{ord}_{11}3=5$).
7 By Theorem 5.51 every unit is a cube iff $d=\gcd(3,p-1)=1$, i.e. $p=3$ or $p\equiv2\pmod3$; and $p=2$ trivially. So $p=2$, $p=3$ and $p\equiv2\pmod3$ ($5,11,17,23,29,\dots$).
8 If $g$ is a primitive root, so is $g^{-1}=g^{p-2}$ ($\gcd(p-2,p-1)=1$), and $g^{-1}\not\equiv g$ because $g^2\not\equiv1$ when $p-1\gt2$. So the primitive roots pair off as $\{g,g^{-1}\}$, each pair having product $1$.
9 An automorphism of $\mathbb{Z}_n$ is determined by the image $a$ of $1$, and $x\mapsto ax$ is bijective iff $\gcd(a,n)=1$; composition corresponds to multiplication, so $\operatorname{Aut}(\mathbb{Z}_n)\cong U_n$, of order $\varphi(n)$. The generators of $\mathbb{Z}_n$ are the $a$ with $\gcd(a,n)=1$. $\operatorname{Aut}(\mathbb{Z}_n)$ is cyclic iff $U_n$ is, i.e. iff $n=1,2,4,p^k,2p^k$ (Theorem 5.49).
IV
Quadratic residues and multiplicative functions.
  • 1 List the quadratic residues modulo $11$ and modulo $13$. Is $10$ a square modulo $13$? Modulo $11$?
  • 2 Evaluate $\left(\frac5{19}\right)$ by Euler's criterion and by reciprocity, and find a solution of $x^2\equiv5\pmod{19}$.
  • 3 Decide whether $x^2\equiv13\pmod{61}$ and $x^2\equiv-1\pmod{61}$ are solvable.
  • 4 Check Theorem 5.53(2) for $p=3,5,7,11,13,17$ by listing squares.
  • 5 Compute $\tau(2026)$, $\sigma(2026)$, $\mu(2026)$, $\tau(360)$, $\sigma(360)$.
  • 6 Prove that $\sigma(n)$ is odd if and only if $n$ is a square or twice a square.
  • 7 Prove Euclid's theorem: if $2^p-1$ is prime, then $2^{p-1}(2^p-1)$ is perfect. Verify for $496$.
  • 8 Prove that $\sum_{d\mid n}\mu(d)\,\tau(n/d)=1$ for every $n$.
  • 9 Prove that $\sum_{d\mid n}|\mu(d)|=2^{r}$, where $r$ is the number of distinct prime factors of $n$.
  • 10 (Modelling.) A circular dial has $n$ equally spaced marks. A pointer starts at mark $0$ and jumps $k$ marks each second ($1\le k\le n$). For how many $k$ does the pointer visit every mark? For $n=60$, how many jump sizes visit exactly $12$ marks?
1 Mod $11$: squares of $1,\dots,5$ are $1,4,9,5,3$, so $\{1,3,4,5,9\}$. Mod $13$: $1,4,9,3,12,10$, so $\{1,3,4,9,10,12\}$. $10$ is a square mod $13$ ($6^2=36\equiv10$) but not mod $11$.
2 $5^2\equiv6$, $5^4\equiv36\equiv-2$, $5^8\equiv4$, $5^9\equiv20\equiv1\pmod{19}$: $\left(\frac5{19}\right)=1$. Reciprocity ($5\equiv1\pmod4$): $\left(\frac5{19}\right)=\left(\frac{19}5\right)=\left(\frac45\right)=1$. A root: $9^2=81=4\cdot19+5$, so $x\equiv\pm9$.
3 $61\equiv1\pmod4$: $\left(\frac{13}{61}\right)=\left(\frac{61}{13}\right)=\left(\frac9{13}\right)=1$ — solvable ($x\equiv\pm14$: $196=3\cdot61+13$). And $-1$ is a square mod $61$ because $61\equiv1\pmod4$ (e.g. $x=11$: $121=2\cdot61-1$).
4 Squares mod $3$: $\{1\}$; mod $5$: $\{1,4\}$; mod $7$: $\{1,2,4\}$; mod $11$: $\{1,3,4,5,9\}$; mod $13$: $\{1,3,4,9,10,12\}$; mod $17$: $\{1,2,4,8,9,13,15,16\}$. So $2$ is a residue exactly for $p=7,17$ ($\equiv\mp1\pmod8$) and a non-residue for $3,5,11,13$ ($\equiv\pm3\pmod8$) ✓.
5 $2026=2\cdot1013$: $\tau=4$, $\sigma=3\cdot1014=3042$, $\mu=1$. $360=2^3\cdot3^2\cdot5$: $\tau=4\cdot3\cdot2=24$, $\sigma=15\cdot13\cdot6=1170$.
6 $\sigma(2^a)=2^{a+1}-1$ is always odd. For odd $p$, $\sigma(p^a)=1+p+\cdots+p^a$ is a sum of $a+1$ odd terms, odd iff $a$ is even. So $\sigma(n)$ is odd iff every odd prime has an even exponent, i.e. the odd part of $n$ is a square $m^2$; then $n=2^am^2$, which is a square ($a$ even) or twice a square ($a$ odd).
7 With $q=2^p-1$ prime and $\gcd(2^{p-1},q)=1$: $\sigma(2^{p-1}q)=(2^p-1)(q+1)=(2^p-1)2^p=2\cdot2^{p-1}q$. For $p=5$: $496=2^4\cdot31$, $\sigma=31\cdot32=992=2\cdot496$ ✓.
8 $\tau(n)=\sum_{d\mid n}1$, so by Möbius inversion (with $f\equiv1$, $F=\tau$), $1=f(n)=\sum_{d\mid n}\mu(d)\tau(n/d)$.
9 $|\mu|$ is multiplicative, so the sum is multiplicative; at $p^a$ it is $1+1=2$. Multiply over the $r$ primes. (Equivalently: $|\mu(d)|=1$ exactly for the $2^r$ squarefree divisors.)
10 The pointer visits the marks $0,k,2k,\dots$ mod $n$, i.e. the subgroup generated by $k$ in $\mathbb{Z}_n$, which has $n/\gcd(k,n)$ elements. It visits every mark iff $\gcd(k,n)=1$: $\varphi(n)$ jump sizes. For $n=60$, exactly $12$ marks iff $\gcd(k,60)=5$, i.e. $k=5j$ with $\gcd(j,12)=1$, $1\le j\le12$: $\varphi(12)=4$ jump sizes ($k=5,25,35,55$).
🎯 Exam corner CSIR Part BCSIR Part CGATE MA

E1. CSIR Part B GATE MA The number of primitive roots modulo $50$ is (A) $0$; (B) $8$; (C) $10$; (D) $20$.

Existence $50=2\cdot5^2$ is of the form $2p^k$, so primitive roots exist (Theorem 5.49) — (A) is out.
Count $\varphi(50)=20$ and there are $\varphi(20)=8$ primitive roots (Theorem 5.47). (D) is $\varphi(50)$, the number of units; (C) is half of it.
Answer (B).

E2. CSIR Part B The last two digits of $3^{2026}$ are (A) $09$; (B) $29$; (C) $49$; (D) $69$.

Order $\operatorname{ord}_{100}(3)=20$ (Exercise II.2), and $2026\equiv6\pmod{20}$.
Compute $3^6=729\equiv29\pmod{100}$. (Option (C) $49\equiv3^{10}$ is what one gets by reducing the exponent modulo $\varphi(100)=40$ and then slipping, $2026\equiv10$ instead of $26$; the correct reduction $3^{26}=3^{20}\cdot3^6\equiv29$ agrees with the order method.)
Answer (B).

E3. CSIR Part B For which of the following $n$ is the group $U_n$ of units of $\mathbb{Z}_n$ cyclic? (A) $36$; (B) $50$; (C) $60$; (D) $64$.

Criterion $U_n$ is cyclic iff $n=1,2,4,p^k,2p^k$ ($p$ odd).
Options $36=4\cdot9$ (type (ii)), $60=4\cdot15$ (type (ii)), $64=2^6$ (type (i)): not cyclic. $50=2\cdot5^2$: cyclic.
Answer (B).

E4. CSIR Part C Which of the following statements about Euler's function are true? (One or more options may be correct.) (A) $\varphi(n)$ is even for every $n\ge3$. (B) $\varphi(mn)=\varphi(m)\varphi(n)$ for all $m,n\ge1$. (C) The equation $\varphi(n)=14$ has no solution. (D) $\varphi(n)\ge\sqrt n$ for every $n\ge1$.

(A) True Pair $k$ with $n-k$ (Theorem 5.41(1)).
(B) False $\varphi(4)=2\ne\varphi(2)\varphi(2)=1$.
(C) True Example 2(a).
(D) False $\varphi(6)=2\lt\sqrt6$ (also $n=2$). Only $\varphi(n)\ge\sqrt{n/2}$ holds in general (Exercise I.8).
Answer (A) and (C).

E5. CSIR Part C Let $p=23$. Which of the following are true? (One or more options may be correct.) (A) $5$ is a primitive root modulo $23$. (B) The primitive roots modulo $23$ are exactly the quadratic non-residues modulo $23$. (C) $x^2\equiv-1\pmod{23}$ has a solution. (D) $x^{11}\equiv1\pmod{23}$ has exactly $11$ solutions.

(A) True $\varphi(23)=22=2\cdot11$; $5^2\equiv2\ne1$ and $5^{11}\equiv-1\ne1$ (Exercise III.2).
(B) False There are $11$ non-residues but only $\varphi(22)=10$ primitive roots; $-1$ is a non-residue ($23\equiv3\pmod4$) of order $2$.
(C) False $23\equiv3\pmod4$, so $\left(\frac{-1}{23}\right)=-1$.
(D) True Theorem 5.51 with $a=1$: $d=\gcd(11,22)=11$ solutions (the quadratic residues, indices even).
Answer (A) and (D).

E6. CSIR Part C Let $n=360$. Which of the following are true? (One or more options may be correct.) (A) $\tau(n)=24$. (B) $\sigma(n)=1170$. (C) Exactly $6$ positive divisors of $n$ are perfect squares. (D) $\sum_{d\mid n}\mu(d)=0$.

(A) True $360=2^3\cdot3^2\cdot5$: $\tau=4\cdot3\cdot2=24$.
(B) True $\sigma=15\cdot13\cdot6=1170$.
(C) False Square divisors $2^a3^b$ with $a\in\{0,2\}$, $b\in\{0,2\}$: $1,4,9,36$ — only $4$.
(D) True Theorem 5.55, as $n\gt1$.
Answer (A), (B) and (D).
🧑‍🏫 For the teacher

Suggested plan — 3 lectures × 60 min.

  1. Euler's function. Definition and Theorem 5.37; multiplicativity from the CRT (Theorem 5.38) — draw the $U_{15}\leftrightarrow U_3\times U_5$ table; product formula; Gauss's identity with Interactive 1 at $n=12$, then a prime and $n=36$. Example 1(b) ("invert $\varphi$") on the board, and Example 2(a).
  2. Euler's theorem and orders. Theorem 5.42 by the permutation trick, Definition 5.11 and Theorem 5.43 (stress $\operatorname{ord}\mid\varphi(n)$ and $\operatorname{ord}(a^k)=h/\gcd(h,k)$). Example 3 — last digits are the most frequent exam item. Example 4 as the model "order argument".
  3. Primitive roots, indices, residues, $\tau,\sigma,\mu$. Lagrange's root bound, the counting proof of Theorem 5.46, Theorem 5.47 and the test 5.48; project Interactive 2 for $n=13$ (try $g=2$ and $g=3$), then $n=15$ and $n=16$, where the table shows the missing order. State Theorem 5.49 and prove the "only if" half. Index table of Example 6, Euler's criterion. Close with Theorem 5.54 and Example 7.

Discussion questions. (1) Why does the proof of Theorem 5.46 fail modulo $8$, and which line uses that $p$ is prime? (2) Every primitive root is a non-residue. When are the two sets equal? (Hint: when is $\varphi(p-1)=\tfrac{p-1}2$?) (3) Why do the indices live in $\mathbb{Z}_{\varphi(n)}$ rather than in $\mathbb{Z}_n$, and what does this have to do with $U_n\cong\mathbb{Z}_{\varphi(n)}$?

Misconceptions to watch for. Treating $\varphi$ as completely multiplicative; applying Euler's theorem when $\gcd(a,n)\gt1$; believing $\operatorname{ord}_n(a)=\varphi(n)$ always; assuming primitive roots exist for every $n$; confusing "non-residue" with "primitive root"; reducing indices mod $n$; forgetting that $\mu$ vanishes on non-squarefree numbers.

Suggested homework. I(1, 2, 3, 6), II(1, 2, 4, 6), III(1, 2, 4, 6, 9), IV(1, 2, 5, 7, 10); Exam corner E2, E4, E5.

🔬 Research–Teaching NexusResearch-tutored · optional, about 60 minutes

Research question. For how many primes $p$ is $2$ a primitive root — and why does the decimal expansion of $1/7$ repeat with period $6$ while that of $1/11$ repeats with period $2$?

Why it matters. The period of the decimal expansion of $1/p$ is $\operatorname{ord}_p(10)$, so "full-period" primes are those for which $10$ is a primitive root. Long-period sequences built from primitive roots are used in pseudo-random number generators, in error-correcting and spread-spectrum codes (mobile phones, GPS), and in the design of acoustic diffusers for concert halls, where primitive-root sequences scatter sound evenly. Emil Artin conjectured in 1927 that every integer other than $-1$ and a perfect square is a primitive root for infinitely many primes, with a predictable density; the conjecture is still open, although it is known to follow from the generalised Riemann hypothesis (Hooley, 1967).

What to do.

  1. Write a function $\operatorname{ord}_p(a)$ that tests only the divisors of $p-1$ (use Theorem 5.48).
  2. For every odd prime $p\lt10^5$, decide whether $2$ is a primitive root. Compute the proportion and compare it with Artin's constant $A=\prod_{q\text{ prime}}\left(1-\frac{1}{q(q-1)}\right)\approx0.3739558$.
  3. List the primes $p\lt100$ for which $1/p$ has period $p-1$. Check a few by long division.
  4. Repeat step 2 for $a=4$ and $a=3$. Why is $4$ never a primitive root? Does $3$ have the same proportion as $2$?

Tools: Python with pow(a, k, p) (or sympy.n_order to check your function); a plotting tool for the running proportion as $p$ grows.

Hand in: A one-page note: your proportion with the number of primes tested, the list of full-period primes below $100$, and a one-paragraph explanation of the $a=4$ case.

Going further. Read how Hooley's conditional proof turns Artin's heuristic — "$a$ fails to be a primitive root mod $p$ when $a$ is a $q$-th power residue for some prime $q\mid p-1$" — into the product formula for $A$, and why the density for $a=3$ is also $A$ while some special values of $a$ need a correction factor.

Instructor note: among the $9591$ odd primes below $10^5$, $2$ is a primitive root for $3603$ ($37.57\%$); below $10^6$ the count is $29341$ of $78497$ odd primes ($37.38\%$), close to $A\approx37.40\%$. The full-period primes below $100$ are $7, 17, 19, 23, 29, 47, 59, 61, 97$ (there are $60$ below $1000$). $4=2^2$ is a square, hence a quadratic residue, hence never a primitive root modulo an odd prime (Exercise III.5).

🧪 Self-check quiz

0/5 correct

Q1. $\varphi(100)$ equals

Q2. The order of $2$ modulo $7$ is

Q3. Which modulus has a primitive root?

Q4. How many primitive roots are there modulo $17$?

Q5. For an odd prime $p$, the congruence $x^2\equiv-1\pmod p$ is solvable if and only if