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

Как можно быстро вычислить (x^n)mod y. Уже когда-то копал этот вопрос и обнаружил теорему Эйлера (теория чисел). Не относится к вопросу: Но вся проблема в том, что я учусь в школе, и мы не проходили еще подобных выражений, найденных мною на wiki, и теории чисел. Объясните пожалуйста:
Как использовать эту теорему на практике(например, реализация на C). (Не так важно, но просто интересно)Кратко значение формулировки на wiki. Буду рад какой-нибудь статье, etc для тех, кто еще не знаком с теорией чисел и математикой >9 классов.

Ответ

В украинской (также как и в английской и немецкой [остальные не проверял]) версии википедии есть хороший пример использования Теоремы Эйлера
Наприклад ми хочемо обчислити 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) и т.д.