"На какую цифру оканчивается число `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.
Просто я сомневаюсь, что я открыл что-то новое.
