Привет всем, нужна ваша помощь.

Найти остаток от деления $%(2328^{18} + 132)^{12}$% на $%311$%.

Спасибо.

задан 9 Ноя '14 19:52

изменен 9 Ноя '14 21:04

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

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

В такого рода задачах часто бывает нужно применять теорему Эйлера или малую теорему Ферма. Но в данном случае это не требуется, так как показатели степени небольшие. Судя по всему, тут имелось в виду, что надо применять способ "быстрого" возведения в степень. А именно, для возведения в 12-ю степень не перемножать 12 чисел по очереди, а возвести дважды в квадрат и один раз в куб (в том или ином порядке). Аналогично для 18-й степени, хотя там можно поступить и по-другому.

Начать надо с нахождения остатка от деления числа 2328 на 311. Это легко делается на калькуляторе, или при помощи деления "столбиком". Получается 151. Теперь надо возвести его в 18-ю степень. Воспользуемся тем, что 18=16+2. Тогда, последовательно возводя числа в квадрат и беря остатки, получим следующее:

$%151^2\equiv98\pmod{311}$%

$%151^4\equiv98^2\equiv274\equiv-37\pmod{311}$%

$%151^8\equiv37^2\equiv125\pmod{311}$%

$%151^{16}\equiv125^2\equiv75\pmod{311}$%

$%151^{18}\equiv151^{16}\cdot151^2\equiv75\cdot98\equiv197\pmod{311}$%

Теперь прибавляем 132, получая 18 по модулю 311. Остаётся 18 возвести в 12-ю степень. Здесь поступаем аналогично, и можно для разнообразия действовать по схеме: в квадрат; в куб; в квадрат (там числа получаются поменьше). В ответе будет $%89$%.

ссылка

отвечен 9 Ноя '14 20:32

Класс, спасибо, вы так объясняете, что, думаю, зачем иду в универ слушать скучные лекции и негодование преподов, когда у тебя ничего не получается. Лучше тут. :) Спасибо.

(9 Ноя '14 20:46) asddsa

@asddsa: бывает так, что от преподавателей требуют "начитать" много материала. Особенно это характерно для "непрофильных" вузов. Я не раз слышал жалобы от студентов, что объясняют мало, а требуют много. Но зато есть форумы, где можно проконсультироваться, так что не всё так плохо. Когда кто-то интересуется способами решения задач или хочет узнать что-то новое, а не просто ищет "исполнителя", я охотно иду навстречу. Так что спрашивайте, если что интересно (тем более, теория чисел -- вещь сама по себе очень приятная).

(9 Ноя '14 20:50) falcao

Спасибо. :)

(9 Ноя '14 20:52) asddsa
10|600 символов нужно символов осталось
0

Можно еще так решить:

Положим $%{2328^{18}} + 132 \equiv k\,\,({\text{mod 311)}}$%, тогда $%{({2328^{18}} + 132)^{12}} \equiv {k^{12}}\,\,({\text{mod 311)}}$%. Вычислим сначала остаток от деления $%{2328^{18}}$% на $%311$%. $$\eqalign{ & {({2328^{18}} + 132)^{12}} \equiv {k^{12}}\,\,({\text{mod 311)}} \cr & 2328 \equiv 151\,\,\,({\text{mod 311)}} \Leftrightarrow {2328^{18}} \equiv {151^{18}}\,\,\,({\text{mod 311)}} \cr & {151^2} \equiv 98\,\,\,({\text{mod 311)}} \Leftrightarrow {({151^2})^9} \equiv {98^9}\,\,\,({\text{mod 311)}} \cr & {98^3} \equiv 106\,\,\,({\text{mod 311)}} \Leftrightarrow {({98^3})^3} \equiv {106^3}\,\,\,({\text{mod 311)}} \cr & {106^3} \equiv 197\,\,\,({\text{mod 311)}} \Leftrightarrow {2328^{18}} \equiv 197\,\,\,({\text{mod 311)}} \cr} $$

Итак, $%{2328^{18}}$% при делении на $%311$% дает остаток $%197$%, тогда $%{2328^{18}} + 132$% при делении на $%311$% дает остаток $%197 + 132 = 329 \equiv 18\,\,\,({\text{mod 311)}}$%. Теперь мы знаем, что $%{({2328^{18}} + 132)^{12}} \equiv {18^{12}}\,\,\,({\text{mod 311)}}$%, где $%k = 18$%. Осталось найти $%{18^{12}}\,\,\,{\text{mod }}\,{\text{311}}$%.

$$\eqalign{ & ({18^{12}}) = {324^6} \equiv {13^6}\,\,\,({\text{mod 311)}} \cr & {\text{1}}{{\text{3}}^6} = {2197^2} \equiv {20^2}\,\,\,\,({\text{mod 311)}} \cr & 400 \equiv 89\,\,\,({\text{mod 311)}} \cr} $$

Это значит, что $%{({2328^{18}} + 132)^{12}}$% дает остаток $%89$% при делении на $%311$%.

ссылка

отвечен 9 Ноя '14 21:50

@void_pointer: а в чём отличие? Мне кажется, разные методы рассматривать полезно, но здесь такие же вычисления, и даже промежуточные числа практически те же.

(9 Ноя '14 21:56) falcao

@falcao отличий немного, просто более подробно расписано.

(9 Ноя '14 22:02) night-raven

@void_pointer: когда что-то непонятное объяснено подробнее, то это бывает ценно, но здесь, на мой взгляд, то же самое изложено более длинно. Одни и те же выражения повторяются много раз, от этого становится труднее читать.

(9 Ноя '14 22:11) falcao
10|600 символов нужно символов осталось
0

Найти остаток от деления 11^81+7^164 на 18

ссылка

отвечен 5 Апр '16 18:53

@марина111111111: это не решение задачи, а новый вопрос. Его и надо помещать в виде отдельного вопроса. Для этого есть кнопка справа вверху.

(5 Апр '16 22:11) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×62

задан
9 Ноя '14 19:52

показан
2478 раз

обновлен
5 Апр '16 22:11

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

по почте:

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

по RSS:

Ответы

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

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