Как найти остаток от деления степеней числа

vorvalm писал(а):

1. Если в Википедии это понятие встречается, а нигде это не поясняется (в Википедии), то это — не правильно.

2. Я имею очень неплохую подготовку прикладного математика по специальности «нелинейная динамика». На форуме опубликована моя монография, где изложены три метода (два — авторские) анализа нелинейных моделей в интегральной форме записи (нелинейные интегро-дифференциальные уравнения). Я имею математическую подготовку, которой могут позавидовать многие физики, но даже я не знаю, что означает запись:
[math]a^{varphi(m)}equiv 1pmod m[/math]
Если я не понимаю этой записи, то (очевидно) её не понимают большинство физиков.
(Проверьте сами.)

Я это говорю к тому, что математики (и не только математики, но математики — особенно) выдумывают понятия и записи, которые понятны только им. А потом жонглируют ими и раздувают щёки, дескать — вот мы какие умные, нас даже не понимают.

Физики тоже так делают. (Выдумывают жаргонные словечки, а потом ими публично жонглируют.)

Всё это делает бездари, чтобы создать видимость научной деятельности.
На то, чтобы придумать что-то полезное людям, у них просто не хватает потенции учёного.

В украинской (также как и в английской и немецкой [остальные не проверял]) версии википедии есть хороший пример использования Теоремы Эйлера:

Наприклад ми хочемо обчислити 7²²² (mod 10). Маємо, що 7 і 10 є
взаємно простими і φ(10) = 4. Одже згідно з теоремою Ейлера 7⁴ ≡ 1 (mod 10) і як наслідок

7²²² ≡ 7^{4×55 + 2} ≡ (7⁴)⁵⁵ x 7² ≡ 1⁵⁵ x 7² ≡ 49 ≡ 9 (mod 10).

Моя попытка перевода:

Например мы хотим вычислить «7²²² (mod 10)». 7 и 10 являются взаимно-простыми и φ(10) = 4 (это число натуральных чисел не больших чем 10 и являющихся взаимнопростыми по отношению к 10. Это следующие числа: 1,3,7,9 и всего их 4).

Следовательно согласно теореме Эйлера 7⁴ ≡ 1 (mod 10) и как следствие:

7²²² ≡ 7^{4×55 + 2} ≡ (7⁴)⁵⁵ x 7² ≡ 1⁵⁵ x 7² ≡ 49 ≡ 9 (mod 10).

Следствия из теоремы:

если a^φ(n) ≡ 1 (mod n), то и (a^φ(n))^k ≡ 1 (mod n) для любого положительного k, т.к.

(a^φ(n))^k ≡ a^φ(n) mod n * (a^φ(n))^{k — 1} mod n ≡ (a^φ(n))^{k — 1} (mod n) и т.д.

Я думаю, что «в виде исключения» здесь можно изложить полное решение. Сам пример составлен достаточно удачно, и на его основе можно пронаблюдать разные «тонкости», касающиеся того, какие методы можно применять. Способы хотя и стандартны, но некоторыми из них пример решается легче, а некоторыми сложнее. К тому же, примеры этого типа часто звучат на форуме, и написанное потом можно будет давать в качестве ссылки.

Но, тем не менее, даже для понимания решения нужно владеть следующим «теорминимумом»: линейные сравнения и их системы; китайская теорема об остатках; малая теорема Ферма; функция Эйлера; теорема Эйлера. Всё это можно прочитать, например, в учебнике Бухштаба.

Прежде всего, нужно разложить на простые множители число $%611$%. Если бы оно было простым, ответ мгновенно получался бы из малой теоремы Ферма: $%x^pequiv xpmod{p}$%. Но здесь число составное: деля его последовательно на простые, видим, что оно делится на $%13$% и равно $%pq=13cdot47=611$%.

Понятно, что число $%a=34$% не делится ни на $%p$%, ни на $%q$%, поэтому оно взаимно просто с $%n=pq$%, и можно применить теорему Эйлера: $%a^{varphi(n)}equiv1pmod{n}$%. Здесь $%varphi(n)=varphi(pq)=(p-1)(q-1)$%; показатель степени приводим по модулю $%varphi(n)$%, получая $%pq-(p-1)(q-1)=p+q-1=59$%. При этом задача сводится к нахождению остатка от деления $%34^{59}$% на $%611$%. В таком виде можно было бы посчитать остаток при помощи «быстрого возведения в степень», последовательно возводя числа в квадрат и беря остатки от деления. Далее через двоичное разложение $%59$% мы получили бы ответ, но это требовало бы длинных вычислений. Тем не менее, сам этот метод иногда применим, и его полезно иметь в виду. Здесь же проще найти остатки от деления числа на $%13$% и $%47$% по отдельности, а потом применить китайскую теорему об остатках.

Итак, по модулю $%p=13$% мы заменяем $%34$% на $%-5$%, а показатель степени $%pq$% приводим по модулю $%p-1=12$%, получая $%q=47$%, что сравнимо с $%-1$%. Это удобно, так как вместо возведения в степень нужно найти элемент, обратный $%-5$% по модулю $%13$%. Это делается устно за счёт того, что $%5cdot5equiv25equiv-1pmod{13}$%, то есть число $%x=34^{611}$% из условия при делении на $%13$% даёт в остатке $%5$%. Более подробно повторим то, что было выше: $%xequiv(-5)^{611}equiv(-5)^{12q-1}equiv(-5)^{-1}equiv5pmod{13}$%.

Теперь рассуждаем по модулю $%q=47$%. Здесь основание степени приводим по модулю $%47$%, заменяя на $%-13$%, а показатель приводим по модулю $%q-1=46$%, заменяя на $%13$%. Получается $%xequiv(-13)^{13}pmod{47}$%, и здесь уже применяем быстрое возведение в степень:

$%(-13)^2equiv169equiv28equiv-19pmod{47}$%;

$%(-13)^4equiv(-19)^2equiv361equiv32equiv-15pmod{47}$%;

$%(-13)^8equiv(-15)^2equiv225equiv37equiv-10pmod{47}$%.

Наконец, $%(-13)^{13}equiv(-13)^{8+4+1}equiv(-10)(-15)(-13)equiv(-10)7equiv24pmod{47}$%.

Итак, оба остатка найдены, и остаётся решить систему из двух сравнений:

$$
left{
begin{array}{l}
xequiv5mod{13}\
xequiv24pmod{47}
end{array}
right.
$$

Это делается стандартно: из второго уравнения получаем $%x=47y+24$%, где $%y$% целое, и подставляем в первое. После упрощений получается $%-5y-2equiv5pmod{13}$%, то есть $%-5yequiv7pmod{13}$%. Домножая обе части на $%5$%, имеем $%yequiv35equiv-4pmod{13}$%, то есть $%y=13k-4$%, где $%k$% целое. Отсюда $%x=47(13k-4)+24=611k-164$%. Остаток от деления на $%611$% равен $%611-164=447$%, и это ответ.