TAOCP 1.3.2 Exercise 6
(a) Let $n$ be a composite integer, $n > 1$.
Section 1.3.2: The MIX Assembly Language
Exercise 6. [HM20] (a) Show that if n is not prime, n has a divisor d with 1 < d \le \sqrt{n}. (b) Use this fact to show that the test in step P7 of Algorithm P proves that N is prime.
Verified: yes
Solve time: 1m30s
Solution
(a) Let $n$ be a composite integer, $n > 1$. Then there exist integers $a, b$ such that $1 < a < n$, $1 < b < n$, and $n = a b$. If both $a$ and $b$ were strictly greater than $\sqrt{n}$, then their product would satisfy
$$ a b > \sqrt{n} \cdot \sqrt{n} = n, $$
contradicting the equality $n = a b$. Therefore, at least one of $a$ or $b$ satisfies $a \le \sqrt{n}$ or $b \le \sqrt{n}$. Let $d = \min(a, b)$; then $1 < d \le \sqrt{n}$, and $d$ divides $n$ by construction. This completes the proof of part (a). ∎
(b) Consider step P7 of Algorithm P. Let $N$ be the candidate number under consideration, and let $K$ index the potential prime divisors from the array $\text{PRIME}[1 \dots J]$. Step P6 divides $N$ by $\text{PRIME}[K]$, yielding quotient $Q$ and remainder $R$. If $R = 0$, $N$ is composite, and the algorithm advances $N \leftarrow N + 2$ at step P4. Otherwise, the algorithm proceeds to step P7.
By part (a), if $N$ is composite, it has a divisor $d \le \sqrt{N}$. The algorithm tests all primes $\text{PRIME}[K]$ in increasing order, starting with $K = 2$. Let $K_0$ be the smallest index such that $\text{PRIME}[K_0] \ge d$. Then either $N$ is divisible by some $\text{PRIME}[K] < \text{PRIME}[K_0]$, in which case step P6 detects $R = 0$ and returns to step P4, or $N$ is not divisible by any $\text{PRIME}[K] < \text{PRIME}[K_0]$. In the latter case, when $\text{PRIME}[K_0] \ge \sqrt{N}$, the division at step P6 satisfies $Q \le \text{PRIME}[K_0]$. Step P7 checks whether $Q \le \text{PRIME}[K]$, which now holds for $K = K_0$. The algorithm then correctly concludes $N$ is prime at step P2 and stores it in the table.
Therefore, the test at step P7 guarantees that all composite numbers are rejected before the assignment $\text{PRIME}[J] \leftarrow N$ occurs, and any number passing step P7 must be prime. This completes the proof of part (b). ∎