Изменения

Перейти к: навигация, поиск

Теорема Валианта-Вазирани

761 байт добавлено, 17:05, 3 мая 2010
Доказательство теоремы
*Для некоторых <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>b_i / \log_2 b_i = 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>.
==Внешние ссылки==
165
правок

Навигация