Pound; b£ n-1
Если для каждого простого делителя p числа n-1 справедливы следующие утверждения:
(1) bn-1≡ 1(mod n),
(2) b(n-1)/p≢ 1(mod n),
то n – простое число.
Тест:Брилхарт, Лемер и Селфридж
В 1975 году Брилхарт, Лемер и Селфридж поставили себе целью так усовершенствовать тест Люка, чтобы для разных простых делителей числа n-
1 можно было находить вычеты различных чисел b. Это намного бы упростило применение теста. Результат их усилий сформулирован ниже
Пусть n – нечетное натуральное число, причем
n-1=p1 e1…pr er,
где p1 <…< pr – простые числа. Если для каждого i=1,2,…,r существует такое
целое число bi (2 £ bi £ n-1), что
|