теория-чисел — Как найти остаток от деления числа в степени?
Найдите остаток от деления чисел:
а) 23 в степени 277 на 9;
б) 17 в степени 332 на 10.
Нужно подробное решение. Заранее большое спасибо!
задан 15 Дек ’14 21:23
(16 Июн ’15 8:09) Dims Vs
1 ответ
Нужно воспользоваться свойствами сравнений и теоремой Эйлера. В первом примере 23 заменяем на 5 (остаток от деления на 9), и используем то, что $%\varphi(9)=6$%. Поскольку 5 взаимно просто с 9, из теоремы Эйлера следует, что $%5^6\equiv1\pmod9$%. Ввиду того, что $%277=6\cdot49+1$%, получается $%5^\equiv(5^6)^\cdot5\equiv5\pmod9$%, то есть остаток равен 5.
Во втором случае $%\varphi(10)=4$%, поэтому показатель степени делим с остатком на 4. Получается 0, поэтому остаток равен $%7^0=1$%. Здесь можно рассуждать даже проще, следя за последней цифрой произведения: ясно, что $%7^4$% оканчивается на 1, и при возведении в любую степень последняя цифра остаётся равна 1.
отвечен 15 Дек ’14 21:32
falcao
299k ● 9 ● 38 ● 53
Найти остаток от деления числа в степени
5.16. Запрещено создавать темы с множеством вопросов во всех разделах, кроме разделов платных услуг. Один вопрос — одна тема.
Задания и решения набирать ручками. Один вопрос — одна тема. Для формул есть редактор.
Лучшие ответы ( 1 )
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:
Найти остаток от деления числа в степени на другое число
Всем привет! Впервые столкнулся с задачей, где нужно найти остаток от деления числа в степени на.
Найти остаток от деления числа
Как это решить? (используя теоремы Эйлера, Ферма и пр) Найти остаток от деления 1040+1240 на 25
Найти остаток от деления числа
Найти остаток от деления числа ^ на 7. Я решал так: Поскольку число 2001 не делится.
Найти остаток от деления числа a на число b
a = 7^218 m=11 я нашел НоД не могу применить теорему Эйлера чтоб найти остаток , помогите.
Регистрация: 30.04.2021
Сообщений: 1
Сообщение было отмечено spvln как решение
Решение
Задачи решались с использованием теории сравнений из раздела теории чисел
1) 17 2001 =(17 3 ) 667 . 17 3 = 4913. Данное число дает остаток 913 при делении на 1000. По теории сравнений , следовательно . То есть 913 667 дает такой же остаток, что и исходное число в условии задачи. Далее 913 667 = (913 3 ) 222 *913. . Тогда . Рассуждая таким же образом, далее получим . . 729 37 *913 = 729 36 *729*913. . . Последнее число без труда считается на калькуляторе, оно дает остаток 17 при делении на 1000. Таким образом . Указанное число в задаче дает остаток 17 при делении на 1000.
Две следующие задачи проще
2) 11 дает остаток 4 при делении на 7 или . . . . И дальше остатки будут повторяться: 11 5 даст остаток 2, следующая степень 1 и так далее. У нас степень 1041. 1041 = 3*347, т. е. нацело делится на 3. Степени, кратные 3, дают остаток 1. Значит ответ 1.
3) . . . . И далее остатки повторяются. в итоге ^\equiv 1 (mod 5), так как 100 = 4*25.
Аналогично с тройкой: . . . . Степени снова повторяются, . Сумма 2 100 +3 100 дает остаток 2 при делении на 5. Ответ 2.
Найти остаток от деления числа a=3×2^73+9×16^29 на 17
Т.е. 2^8 дает остаток 1 при делении на 17. Тогда 2^8 в любой степени будет давать остаток 1 при делении на 17 (при умножении чисел остатки умножаются).
2^73 = 2 х 2^72 = 2 х (2^8)^9. Остаток: 2 х 1 = 2
3 × 2^73. Остаток: 3 х 2 = 6
16^29 = (2^4)^29 = 2^116 = 2^4 x 2^112 = 16 x (2^8)^14. Остаток: 16 х 1 = 16
9 × 16^29. Остаток 9 х 16 = 144 = 136 + 8 = 17 х 8 + 8. Остаток 8.
Число а: остаток 6 + 8 = 14.
Решите: найти остаток от деления числа 103 в степени15 на 17. задача по алгебре . выччислять нельзя!
правильно выше написано, есть такое свойство:
если a=b(mod n), то a^x=b^x(mod n)
вот и видим, что 103=1(mod 17), поэтому 103^15=1^15(mod 17). А единица в любой степени равна 1.
А можно ещё так:
103= 6*17+1
103^15 = (6*17+1)^15=произведению этих пятнадцати скобок, которое будет выглядеть так (6*17)^15 + какие-то произведения чисел кратные 17-и + 1^15 = 17Y+1, где Y — это большое большое число (сумма произведений разных чисел) , которое можно не считать потому что суть втом, что из него вынесли 17. Итак, 103^15 даёт при делении на 15 единицу.