设 l≥k 且 al=2l。令 p 为 l−1 的最小素因子（由于 l≥k≥3，故 l−1≥2，p 存在且 p≤l−1）。我们考察 n=l+1,l+2,…,l+p−1 这 p−1 步的递推。
对 1≤i≤p−1，令 n=l+i−1，此时 n−1=l+i−2。先计算 (n−1,l−1)=(l+i−2,l−1)=(i−1,l−1)。由于 1≤i≤p−1，故 0≤i−1≤p−2<p。而 p 是 l−1 的最小素因子，所以 l−1 的所有素因子都 ≥p，从而 (i−1,l−1)=1。
接下来计算 (an−1,n)。由归纳假设（见下一步），an−1=al+i−2=2l+i−2。于是
(an−1,n)=(2l+i−2,l+i−1)=(2l+i−2−2(l+i−1),l+i−1)=(−i,l+i−1)=(i,l+i−1).
又 (i,l+i−1)=(i,l−1)。由于 1≤i≤p−1<p，而 p 是 l−1 的最小素因子，故 (i,l−1)=1。因此 (an−1,n)=1，由递推规则得 an=an−1+1=2l+i−1。
由数学归纳法，对所有 1≤i≤p−1，都有 al+i−1=2l+i−1。特别地，al+p−2=2l+p−2。
现在考察 n=l+p−1 这一步。此时 an−1=al+p−2=2l+p−2，n=l+p−1。计算
(an−1,n)=(2l+p−2,l+p−1)=(2l+p−2−2(l+p−1),l+p−1)=(−p,l+p−1)=(p,l+p−1).
由于 p∣(l−1)，故 l+p−1=(l−1)+p 也被 p 整除，所以 (p,l+p−1)=p>1。由递推规则得 al+p−1=2(l+p−1)。
因此这一步的差为
al+p−1−al+p−2=2(l+p−1)−(2l+p−2)=p,
恰为素数。