TAOCP 4.5.4 Exercise 17
We prove simultaneously, by induction on the height of the tree, that for every node $(q,x)$: 1.
Section 4.5.4: Factoring into Primes
Exercise 17. [M25] (V. R. Pratt.) A complete proof of primality by the converse of Fermat's theorem takes the form of a tree whose nodes have the form $(q, x)$, where $q$ and $x$ are positive integers satisfying the following arithmetic conditions: (i) If $(q, x_1), \ldots, (q_r, x)$ are the children of $(q, x)$ then $q = q_1 \cdots q_r + 1$. [In particular, if $(q, x)$ is childless, then $q = 2$.] (ii) If $(r, y)$ is a child of $(q, x)$, then $x^{(q-1)/r} \bmod q \ne 1$. (iii) For each node $(q, x)$, we have $x^{q-1} \bmod q = 1$. Prove that this conditions imply that $q$ is prime and $x$ is a primitive root modulo $q$, for all nodes $(q, x)$. [For example, the tree
$$ \begin{array}{c} (1009, 11)\[4pt] (2,1)\quad (2,1)\quad (2,1)\quad (2,1)\quad (7,3)\quad (3,2)\quad (3,2)\[4pt] \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad (2,1)\quad (3,2)\quad (2,1)\quad (2,1)\[4pt] \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad (2,1) \end{array} $$
demonstrates that 1009 is prime.] Prove that such a tree with root $(q, x)$ has at most $f(q)$ nodes, where $f$ is a rather slowly growing function.
Verified: yes
Solve time: 2m06s
Solution
We prove simultaneously, by induction on the height of the tree, that for every node $(q,x)$:
- $q$ is prime;
- $x$ is a primitive root modulo $q$.
For a node $(q,x)$, let its children be
$$ (q_1,x_1),\ldots,(q_r,x_r). $$
Condition (i) states that
$$ q-1=q_1q_2\cdots q_r . $$
Assume first that $(q,x)$ is childless. Then condition (i) implies
$$ q=2. $$
The only nonzero residue modulo $2$ is $1$, hence $x\equiv1\pmod2$. Since the multiplicative group modulo $2$ has order $1$, $x$ is a primitive root modulo $2$. Thus both assertions hold for every leaf.
Now consider a nonleaf node $(q,x)$ and assume inductively that the assertions hold for all descendants. In particular, every child label $q_i$ is prime.
Since
$$ q-1=q_1q_2\cdots q_r, $$
every prime divisor of $q-1$ is among the numbers $q_1,\ldots,q_r$.
Condition (iii) gives
$$ x^{q-1}\equiv1\pmod q. $$
Let $d$ be the multiplicative order of $x$ modulo $q$. Then
$$ d\mid(q-1). $$
Suppose that $d<q-1$. Since $d$ is a proper divisor of $q-1$, some prime divisor $q_i$ of $q-1$ satisfies
$$ d\mid \frac{q-1}{q_i}. $$
Hence
$$ x^{(q-1)/q_i}\equiv1\pmod q. $$
This contradicts condition (ii), which requires
$$ x^{(q-1)/q_i}\not\equiv1\pmod q $$
for every child $(q_i,x_i)$.
Therefore
$$ d=q-1. $$
The residue class of $x$ modulo $q$ has order $q-1$.
If $q$ were composite, then every invertible residue modulo $q$ would have order at most $\varphi(q)$. Since $q$ is composite and $q>1$,
$$ \varphi(q)<q-1. $$
But $x$ has order $q-1$, a contradiction. Hence $q$ must be prime.
Since $q$ is prime and $x$ has order $q-1$, $x$ is a primitive root modulo $q$.
The induction is complete. Therefore every node $(q,x)$ in the tree satisfies that $q$ is prime and $x$ is a primitive root modulo $q$.
To establish the bound on the number of nodes, let $F(q)$ denote the maximum possible number of nodes in a valid tree rooted at a prime $q$.
For a leaf,
$$ F(2)=1. $$
If $q>2$ and the children have labels $q_1,\ldots,q_r$, then
$$ q-1=q_1q_2\cdots q_r, $$
hence
$$ F(q)\le 1+\sum_{i=1}^r F(q_i). $$
Define
$$ f(q)=1+\sum_{p^e\parallel(q-1)} e,f(p), \qquad f(2)=1. $$
Repeated application of the preceding inequality yields
$$ F(q)\le f(q). $$
To estimate the growth of $f$, write
$$ g(q)=\frac{f(q)}{\log_2 q}. $$
Since every prime factor of $q-1$ is strictly smaller than $q$,
$$ f(q) \le 1+\sum_{p^e\parallel(q-1)} e,g(p)\log_2 p. $$
Let
$$ G(q)=\max_{2\le t\le q} g(t). $$
Then
$$ f(q) \le 1+G(q-1)\sum_{p^e\parallel(q-1)} e\log_2 p = 1+G(q-1)\log_2(q-1). $$
Therefore
$$ g(q) \le \frac1{\log_2 q} + G(q-1)\frac{\log_2(q-1)}{\log_2 q} \le \frac1{\log_2 q}+G(q-1). $$
Since the additive term tends to $0$, induction shows that
$$ f(q)=O(\log q). $$
Thus every Pratt certificate tree for $q$ contains at most $f(q)$ nodes, where $f(q)$ grows only on the order of $\log q$. In particular, the proof of primality has size proportional to the number of bits of $q$.
This completes the proof.
∎