В теории чисел , с нечетным целым числом п называется вероятное простым число Эйлера-Якоби (или, чаще, вероятные простой Эйлер ) основывать , если и п являются взаимно простым , а
где - символ Якоби .
Если n - нечетное составное целое число, удовлетворяющее вышеуказанному сравнению, то n называется псевдопервичным числом Эйлера – Якоби (или, чаще, псевдопервичным числом Эйлера ) для основания a .
Характеристики
Мотивом для этого определения является тот факт, что все простые числа n удовлетворяют приведенному выше уравнению, как объясняется в статье о критериях Эйлера . Уравнение можно проверить довольно быстро, что может быть использовано для вероятностной проверки на простоту . Эти тесты более чем в два раза сильнее тестов, основанных на маленькой теореме Ферма .
Каждое псевдопростое число Эйлера – Якоби также является псевдопервичным числом Ферма и псевдопервичным числом Эйлера . Не существует чисел, которые являлись бы псевдопростыми числами Эйлера – Якоби для всех оснований, как числа Кармайкла . Соловей и Штрассен показали, что для любого составного n , по крайней мере, для n / 2 базисов, меньших n , n не является псевдопростом Эйлера – Якоби.
Наименьшее основание 2 псевдопростых чисел Эйлера – Якоби равно 561. Существует 11347 псевдопростых чисел Эйлера – Якоби с основанием 2, которые меньше 25 · 10 9 (см. OEIS : A047713 ) (стр. 1005 из [1] ).
В литературе (например, [1] ) псевдопервичное число Эйлера – Якоби, как оно определено выше, часто называется просто псевдопервичным числом Эйлера.
Смотрите также
Рекомендации
- ^ a b Карл Померанс ; Джон Л. Селфридж ; Сэмюэл С. Вагстафф младший (июль 1980 г.). «Псевдопреступности до 25 · 10 9 » (PDF) . Математика вычислений . 35 (151): 1003–1026. DOI : 10.1090 / S0025-5718-1980-0572872-7 .