Найти число оснований a из Z∗ 429, для которых 429 является псевдопростым

задан 2 дня назад

10|600 символов нужно символов осталось
0

Требуется условие a^{428}=1 (mod 429). При этом 429=3 * 11 * 13.

Степенное сравнение должно выполняться по модулю 3, 11, 13. По модулю 3 оно верно, если a не делится на 3. Тогда a даёт 2 возможных остатка от деления на 3.

По модулю 11, мы знаем, что a^{10}=1(mod 11). Отсюда a^2=1(mod 11). Это два значения остатка.

Наконец, по модулю 13 имеем a^{12}=1(mod 13), и тогда a^4=1(mod 13), так как НОД(12,428)=4. Здесь a^2=1(13) или a^2=-1=5^2(13). Значений четыре: 1, -1, 5, -5.

По китайской теореме об остатках, для каждого набора возможных остатков от деления на 3, 11, 13, подойдёт ровно одно a по модулю произведения. Значит, псевдопростых будет 2 * 2 * 4 = 16 штук.

ссылка

отвечен вчера

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

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

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

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

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

отмечен:

×142

задан
2 дня назад

показан
33 раза

обновлен
вчера

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

по почте:

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

по RSS:

Ответы

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

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