Здравствуйте. Подскажите как решить задачу: Найти все основания a, по которым число 91 является псевдопростым.

задан 21 Май '17 15:52

Поскольку бывают разные типы псевдопростых чисел, желательно сопроводить условие задачи точным определением.

(21 Май '17 22:40) falcao

@falcao: Составное число n называется псевдопростым числом Ферма по основанию a (взаимно простому с n), если выполнено сравнение a^(n-1) = 1 (mod n). Иными словами, составное число называют псевдопростым, если оно проходит тест Ферма по основанию a.

(21 Май '17 22:43) SergeY

@SergeY: теперь условие понятно, но это надо было сказать сразу, потому что есть много других тестов.

(22 Май '17 1:14) falcao
10|600 символов нужно символов осталось
2

По сути дела, надо описать решения сравнения $%a^{90}\equiv1\pmod{91}$%. Здесь $%a$% не делится ни на 7, ни на 13. Сравнение равносильно системе $%a^{90}\equiv1\pmod7$% и $%a^{90}\equiv1\pmod{13}$%. Первое условие выполнено в силу малой теоремы Ферма (90 делится на 6). Во втором случае та же малая теорема Ферма даёт $%a^{12}\equiv1\pmod{13}$%. Поскольку $%НОД(12,90)=6$%, получается условие $%a^6\equiv1\pmod{13}$%. Оно выполнено для случаев, когда $%a$% является квадратом по модулю 13. Такие числа нам известны (возводим в квадрат числа от 1 до 6 и берём остатки, а потом упорядочиваем их): 1, 3, 4, 9, 10, 12.

Таким образом, в ответе получатся числа вида $%a=13k+r$%, где $%k$% целое, и $%r$% взято из списка. Дополнительное ограничение -- чтобы $%a$% не делилось на 7. Это полное описание, которое позволяет сразу сказать по числу $%a$%, такое оно или "сякое".

Можно, конечно, выписать все остатки от деления на 91, но это совершенно лишняя работа.

ссылка

отвечен 22 Май '17 1:20

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×879

задан
21 Май '17 15:52

показан
574 раза

обновлен
22 Май '17 1:34

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru