"На какую цифру оканчивается число `32^101 + 35^301` в 15-чной системе счисления?"
Вроде знаю как решать. Чисто проверить верно или нет.
Изначально число дано в 10 системе счисления. Для перевода числа из десятичной в любую другую, мы делим данное число на основание системы ну и дальше составляем ответ из одного значения частного, и остальных остатков. По сути задачу можно переопределить так
"Найти остаток от деления `32^101 + 35^301` на 15"
Так как `32 = 15 * 2 + 2`, то можно сделать преобразование
`32^101 -= 2^101`
Дальше по теореме Эйлера
$a^{\phi(n)} \equiv 1 (mod n)$, где `(a, n) = 1`
В таком случае, $2^{\phi(15)} \equiv 2^8 \equiv 1(mod 15)$
Тогда
`2^101 -= 2^96 * 32 -= (2^8)^12 * 32 -= 32` $\equiv 2 (mod 15)$
Второе слагаемое делится на 5, но не делится на 3. Поэтому нам надо найти остаток от деления `35^301/3`. Кстати, можно ли тут искать остаток `7^301/3`?
`35^301 -= 2^301`
Дальше по теореме Эйлера
$2^2 \equiv 1 (mod 3)$
`2^301 -= (2^2)^150 * 2 -= 2` $\equiv 2 (mod 3)$
Сумма остатков = 4. Ответ 4.
Вроде знаю как решать. Чисто проверить верно или нет.
Изначально число дано в 10 системе счисления. Для перевода числа из десятичной в любую другую, мы делим данное число на основание системы ну и дальше составляем ответ из одного значения частного, и остальных остатков. По сути задачу можно переопределить так
"Найти остаток от деления `32^101 + 35^301` на 15"
Так как `32 = 15 * 2 + 2`, то можно сделать преобразование
`32^101 -= 2^101`
Дальше по теореме Эйлера
$a^{\phi(n)} \equiv 1 (mod n)$, где `(a, n) = 1`
В таком случае, $2^{\phi(15)} \equiv 2^8 \equiv 1(mod 15)$
Тогда
`2^101 -= 2^96 * 32 -= (2^8)^12 * 32 -= 32` $\equiv 2 (mod 15)$
Второе слагаемое делится на 5, но не делится на 3. Поэтому нам надо найти остаток от деления `35^301/3`. Кстати, можно ли тут искать остаток `7^301/3`?
`35^301 -= 2^301`
Дальше по теореме Эйлера
$2^2 \equiv 1 (mod 3)$
`2^301 -= (2^2)^150 * 2 -= 2` $\equiv 2 (mod 3)$
Сумма остатков = 4. Ответ 4.
Непонятно равенство `35^301 -= 2^301` ...
Я бы рассуждал так ... (все равенства по модулю 15) ...
`32 = 2` ... `2^4 = 16 = 1 `... `2^{101} = 2*(2^4)^{25} = 2*1^{25} = 2`
`35 = 5` ... `5^3 = 125 = 5` ... `5^{301} = 5^{58} * 5^{3^5} = 5 * 5^3 * 5^{3^3} * 5^{3^3} * 5 = 5^5 = 5^3 = 5`
Итого, `2 + 5 = 7` ...
Не обессудьте за деревенский подход...
Ну мы же работаем с остатками. Поэтому можно заменить основание степени на меньший вычет по модулю 15
35 = 15 * 2 + 5
Конечно же должно быть `5^301`. Пошел перерешивать
С первым слагаемым у меня в общем-то верно получилось. Со вторым я наверное еще более по-деревенски решил)) Ну в принципе почти как у вас. У вас это прослеживается. Я просто проверил первые четыре степени пятерки и убедился, что остатки чередуются - то 5, если степень нечетная, то 10, если степень четная. Ну и раз конечная степень 301, то и остаток значит 5. Хотя грубо. Не люблю так решать, когда решение построено, пусть даже на очевидном, но предположении. Я все же не могу утверждать, что на какой-нибудь 243 степени эта закономерность не собьется. Хотя можно было это проследить так
5 = 5 (mod 15)
25 = 25 (mod 15) = 10 (mod 15)
125 = 50 (mod 15) = 5 (mod 15)
625 = 25 (mod 15) = 10 (mod 15)
Ну и так далее. Здесь хоть прослеживается закономерность.
я не утверждал противного... ... просто с функцией Эйлера не оперирую...
Ну и так далее. Здесь хоть прослеживается закономерность.
так даже проще...