Дальнейшие рассуждения рекомендуется читать медленно и внимательно:
*#Обозначим за <tex>x^{(1)} \ldots x^{(D)}</tex> все выполняющие наборы формулы <tex>\phi</tex>. Заметим, что их число, обозначенное как <tex>D</tex>, нам неизвестно (но не превосходит 2<sup>''n''</sup>).
*#Равенство <tex>i = \lceil \log_2 D \rceil</tex> выполняется с вероятностью 1/(<tex>n</tex>+1), так как <tex>i</tex> было выбрано из [0..<tex>n</tex>]. Предположим, что это соотношение верно.
*#Для некоторых <tex>x^{(j)}</tex> и <tex>x^{(h)}</tex> при условии несовпадения <tex>j</tex> и <tex>h</tex> имеется не более <tex>n</tex> простых делителей разности <tex>x^{(j)} - x^{(h)}</tex>, так как <tex>x^{(j)}</tex> и <tex>x^{(h)}</tex> не превосходят 2<sup>''n''</sup>.
*#Из курса теории чисел известно, что для достаточно больших <tex>n</tex> имеется не менее <tex>\Pi(b_i) \approx \frac{b_i}{\log_2 b_i} = \frac{2^{i + 2}n^2}{i + 2 + 2 \log_2 n} \ge 2^{i+1}n</tex> простых чисел, не превосходящих <tex>b_i</tex>.
*#Из двух предыдущих рассуждений следует, что существует по крайней мере <tex>2^{i+1}n - 2^{i}n = 2^{i}n</tex> чисел <tex>p</tex> таких, что они не превосходят <tex>b_i</tex> и остаток от деления <tex>x^{(j)}</tex> на <tex>p</tex> не совпадает с остатком от деления любого <tex>x^{(h)}</tex> на <tex>p</tex>.
*#Таким образом по крайней мере <tex>2^{i}n</tex> пар чисел <tex>0 \le p_l, r_l \le b_i</tex> отличают набор <tex>x^{(j)}</tex> от всех остальных. Заметим, что при этом множества пар отличающих чисел (<tex>p_l</tex>, <tex>r_l</tex>) для каждого выполняющего набора переменных <tex>x^{(j)}</tex> дизъюнктны.
*#Следовательно, всего имеется не менее <tex>2^i n \cdot D \ge 2^{2i-1}n</tex> искомых отличающих пар. В данной оценке мы использовали равенство из второго пункта.
*#Таким образом, вероятность выбрать отличающую пару чисел (<tex>p_l</tex>, <tex>r_l</tex>) составляет не менее <tex>\frac{2^{2i-1}n}{16\cdot2^{2i}n^4}=\frac{1}{32n^3}</tex>.
*#Домножая полученную вероятность на вероятность выбрать подходящее <tex>i</tex> (см. второй пункт), получим, что вероятность ошибочного построения формулы <tex>\phi_k</tex> составляет <tex>1-\frac{1}{32n^3(n+1)}</tex>.
Составив набор {<tex>\phi_1 \ldots \phi_m</tex>} из ''O''(''n''<sup>4</sup>) формул, каждый раз выбирая тройку (<tex>i</tex>, <tex>p_i</tex>, <tex>r_i</tex>) чисел случайным образом, получим константную вероятность ошибки. Таким образом необходимый набор формул построен, а теорема доказана.
