Найти наибольший отрицательный вычет класса, которому принадлежит число 10^5^1000, по модулю 208

задан 14 Окт 21:22

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

Здесь нужно несколько раз применить теорему Эйлера. Пока что она неприменима, так как числа 10 и 208=2^{4}*13 не взаимно просты. Но степень 10 здесь, очевидно, делится на 2^4=16. Поэтому надо найти остаток от деления числа на 13. Здесь уже теорема Эйлера (в виде малой теоремы Ферма) применима, и сначала нужно найти остаток от деления показателя 5^1000 на число ф(13)=12.

Здесь 5 и 12 взаимно просты. Поэтому теорема Эйлера применима. Имеем ф(12)=ф(4)ф(3)=4. Из этого следует, что 5^4=1 (mod 12), и тем более 5^1000=1 (mod 12). То есть 5^1000=12k+1 при натуральном k, и 10 в степени 5^1000 по модулю 13 сравнимо с 10(10^12)^k=10.

Число x, остаток которого от деления на 208 мы ищем, удовлетворяет условиям x=0 (mod 16) и x=10 (mod 13). Согласно китайской теореме об остатках, эти два условия однозначно позволяют найти вычет по модулю 208. Полагая x=16y для целого y и подставляя во второе сравнение, имеем 16y=10 (mod 13), что равносильно 3y=-3(mod 13), то есть y=-1(mod 13) по свойствам сравнений. Это значит, что y=13m-1 при m из Z, и тогда x=16y=208m-16. Наибольший отрицательный вычет по модулю 208 равен -16.

ссылка

отвечен 15 Окт 0:06

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

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

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

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

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

отмечен:

×671

задан
14 Окт 21:22

показан
68 раз

обновлен
15 Окт 0:06

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

по почте:

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

по RSS:

Ответы

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

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