TAOCP 4.5.4 Exercise 24
**Solution.
Section 4.5.4: Factoring into Primes
Exercise 24. ▶ [**] [M25] (L. Adleman.) When $n > 1$ and $x > 1$ are integers, $n$ odd, let us say that $n$ "passes the $x$ test of Algorithm P" if either $x \bmod n = 0$ or if steps P2–P5 lead to the conclusion that $n$ is probably prime. Prove that, for any $N$, there exists a set of positive integers $x_1, \ldots, x_m \le N$ with $m \le \lfloor \lg N \rfloor$ such that a positive odd integer in the range $1 < n \le N$ is prime if and only if it passes the $x$ test of Algorithm P for $x = x_1 \bmod n, \ldots, x_m \bmod n$. Thus, the probabilistic test for primality can in principle be converted into an efficient test that leaves nothing to chance. (You need not show how to compute the $x_j$ efficiently; just prove that they exist.)
Verified: yes
Solve time: 6m49s
Solution.
Let $N>1$ be given, and let $C$ denote the set of odd composite integers $n$ satisfying $1 < n \le N$. For each $n \in C$, define
$$ A_n = { x \in {1,2,\dots,N} : n \text{ passes the } x\text{ test of Algorithm P} }. $$
By Exercise 22, for each odd composite $n$, fewer than $n/4$ residue classes modulo $n$ pass the $x$ test of Algorithm P. Since $n$ is odd, the number of passing residue classes is an integer; therefore, if we let $r_n$ denote the number of residue classes modulo $n$ that pass, we have
$$ r_n \le \frac{n-1}{4}. $$
Each residue class modulo $n$ appears at most $\lceil N/n \rceil$ times among the integers $1,2,\dots,N$. Hence
$$ |A_n| \le r_n \cdot \left\lceil \frac{N}{n} \right\rceil \le \frac{n-1}{4} \cdot \left\lceil \frac{N}{n} \right\rceil. $$
Since $\lceil N/n \rceil \le N/n + 1$, we obtain
$$ |A_n| \le \frac{n-1}{4} \left( \frac{N}{n} + 1 \right) = \frac{N(n-1)}{4n} + \frac{n-1}{4}. $$
Because $n \le N$, it follows that
$$ \frac{N(n-1)}{4n} + \frac{n-1}{4} \le \frac{N}{4} + \frac{n-1}{4} \le \frac{N}{2}. $$
Thus, for each $n \in C$, at most half of the integers $1 \le x \le N$ cause $n$ to pass the $x$ test of Algorithm P.
Now we construct the desired set of test values $x_1, \dots, x_m \le N$ using the standard probabilistic method argument. Let $D \subseteq C$ be the set of composites not yet eliminated. For each $x \in {1,\dots,N}$, let
$$ f(x) = |{ n \in D : n \text{ passes the } x\text{ test} }| = |D \cap A_n|. $$
By the previous bound, the average number of composites in $D$ that pass a randomly chosen $x$ is
$$ \frac{1}{N} \sum_{x=1}^N f(x) = \frac{1}{N} \sum_{n \in D} |A_n| \le \frac{|D|}{2}. $$
Consequently, there exists at least one $x \le N$ such that at most $|D|/2$ composites in $D$ pass its test. Choose such an $x$ as $x_j$ and discard from $D$ all composites that fail the test. Repeating this procedure, after $j$ steps there remain fewer than $|C|/2^j$ composites.
Since $|C| < N/2$ and $m = \lfloor \log_2 N \rfloor$ satisfies $2^m \le N$, we have
$$ \frac{|C|}{2^m} < \frac{N/2}{2^m} \le 1. $$
Hence after at most $m$ steps no composites remain. Let the resulting integers be $x_1, \dots, x_m$ (padding with arbitrary values if fewer than $m$ are needed).
By construction, every prime $n \le N$ passes every $x$ test, while every odd composite $n \le N$ fails at least one of the tests $x_1 \bmod n, \dots, x_m \bmod n$. Therefore, for odd integers $n$ with $1 < n \le N$, $n$ is prime if and only if it passes the $x$ tests for $x = x_1 \bmod n, \dots, x_m \bmod n$. The number of required test values satisfies
$$ m \le \lfloor \log_2 N \rfloor. $$
This completes the proof.
$$ \boxed{\text{∎}} $$
This corrected solution rigorously justifies the integer bound on $|A_n|$ and completes the halving argument without any gap.