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
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$.
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$. ∎
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)$. ∎
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$).
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.
- $\varphi(n)$ is even for $n\ge3$, and for $n\ge2$ the integers in $[1,n]$ coprime to $n$ have sum $\tfrac12n\varphi(n)$.
- 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$.
- 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)$. ∎
Euler's Theorem and the Order of an Element
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}$.
- $a^k\equiv1\pmod n$ if and only if $h\mid k$. In particular $h\mid\varphi(n)$.
- $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.
- 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$. ∎
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$.
Primitive Roots
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.
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).
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. ∎
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$. ∎
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$. ∎
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. ∎
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.
- $\operatorname{ind}_g(ab)\equiv\operatorname{ind}_g(a)+\operatorname{ind}_g(b)$;
- $\operatorname{ind}_g(a^k)\equiv k\operatorname{ind}_g(a)$, and $\operatorname{ind}_g(1)=0$;
- 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). ∎
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. ∎
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$.
- $\left(\frac{-1}p\right)=(-1)^{(p-1)/2}$: $\ -1$ is a residue iff $p\equiv1\pmod4$.
- $\left(\frac2p\right)=(-1)^{(p^2-1)/8}$: $\ 2$ is a residue iff $p\equiv\pm1\pmod8$.
- 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. ∎
| $a$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $\operatorname{ind}_2a$ | 0 | 1 | 4 | 2 | 9 | 5 | 11 | 3 | 8 | 10 | 7 | 6 |
Multiplicative Functions: $\tau$, $\sigma$ and $\mu$
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.
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.
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$. ∎
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.
- $\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)$.
- $\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.
- $\varphi(m)\mid\varphi(n)$ does not imply $m\mid n$. $\varphi(3)=2\mid4=\varphi(5)$.
- 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.
- $\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$.
- 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$.
- 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.
- 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$.
- Lagrange's root bound is for primes. $x^2\equiv1\pmod8$ has $4$ roots; $x^2\equiv1\pmod{15}$ has $4$.
- "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$).
- Orders do not multiply in general. $\operatorname{ord}(a\cdot a^{-1})=1$; Theorem 5.44 needs coprime orders.
- Index arithmetic is modulo $\varphi(n)$, not $n$. In $x^3\equiv5\pmod{13}$ the index congruence is $3y\equiv9\pmod{12}$.
- $\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
- 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 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 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 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?
E1. CSIR Part B GATE MA The number of primitive roots modulo $50$ is (A) $0$; (B) $8$; (C) $10$; (D) $20$.
E2. CSIR Part B The last two digits of $3^{2026}$ are (A) $09$; (B) $29$; (C) $49$; (D) $69$.
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$.
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$.
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.
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$.
Suggested plan — 3 lectures × 60 min.
- 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).
- 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".
- 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 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.
- Write a function $\operatorname{ord}_p(a)$ that tests only the divisors of $p-1$ (use Theorem 5.48).
- 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$.
- List the primes $p\lt100$ for which $1/p$ has period $p-1$. Check a few by long division.
- 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.
🧪 Self-check quiz
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