Остаток от деления числа в большой степени

#алгоритм #математика

Как можно быстро вычислить (x^n)mod y.
Уже когда-то копал этот вопрос и обнаружил теорему Эйлера (теория чисел).

Не относится к вопросу:
Но вся проблема в том, что я учусь в школе, и мы не проходили еще подобных выражений,
найденных мною на wiki, и теории чисел.
Объясните пожалуйста:


Как использовать эту теорему на практике(например, реализация на C).
(Не так важно, но просто интересно)Кратко значение формулировки на
wiki. Буду рад какой-нибудь статье, etc для тех, кто еще не знаком с 
теорией чисел и математикой >9 классов.

    

Ответы

Ответ 1

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


  Наприклад ми хочемо обчислити 7222 (mod 10). Маємо, що 7 і 10 є
  взаємно простими і φ(10) = 4. Одже згідно з теоремою Ейлера 74 ≡ 1 (mod 10) і як
наслідок
  
  7222 ≡ 74x55 + 2 ≡ (74)55 x 72 ≡ 155 x 72 ≡ 49 ≡ 9 (mod 10).


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

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

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

7222 ≡ 74x55 + 2 ≡ (74)55 x 72 ≡ 155 x 72 ≡ 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) и т.д.