TAOCP 4.5.4 Exercise 1
If $d_k$ is not prime, then $d_k$ has a prime factor $p < d_k$.
Section 4.5.4: Factoring into Primes
Exercise 1. [10] If the sequence $d_0, d_1, d_2, \ldots$ of trial divisors in Algorithm A contains a number that is not prime, why will it never appear in the output?
Verified: yes
Solve time: 1m11s
If $d_k$ is not prime, then $d_k$ has a prime factor $p < d_k$. At the moment when step A3 divides $n$ by $d_k$, either $n \bmod d_k \ne 0$, in which case step A4 causes the algorithm to skip $d_k$, or $n$ is divisible by $d_k$. In the latter case, $n$ is also divisible by $p$, and since $p < d_k$, step A2–A5 will already have removed all factors of $p$ before $d_k$ is reached. Consequently, $d_k$ cannot divide the remaining $n$, so step A5 is never executed for $d_k$. Therefore, nonprime trial divisors cannot appear in the output sequence of prime factors. This completes the proof.
∎