Тест простоты Ферма
Выполняет тест простоты числа, основанный на малой теореме Ферма по заданным основаниям.
Этот материал распространяется на условиях лицензии Creative Commons Attribution/Share-Alike License 3.0 (Unported). Это означает, что вы можете размещать этот контент на своем сайте или создавать на его основе собственный (в том числе и в коммерческих целях), при условии сохранения оригинального лицензионного соглашения. Кроме того, Вы должны отметить автора этой работы, путем размещения HTML ссылки на оригинал работы https://planetcalc.ru/8983/. Пожалуйста оставьте без изменения все ссылки на других авторов данной работы или работы, на основе которой создана данная работа (если таковые имеются в спроводительном тексте).
При помощи данного калькулятора можно узнать является ли число псевдопростым по заданному основанию. Калькулятор использует тест простоты Ферма, основанный на малой теореме Ферма. Если n простое число, и a не делится на n, то справедливо сравнение: .
Тест простоты Ферма
Однако, при помощи теста нельзя достоверно утверждать, что число простое, если результат равен 1. То есть обратное утверждение неверно: если и числа a и n взаимно простые не означает что n - простое число.
Например, число 29341 - дает положительный результат по основаниям 3; 5; 7; 11, согласно результатам работы теста. Однако это число не является простым, это одно из составных чисел Кармайкла: 13 x 37 x 61= 29341.
Комментарии