Анализируя код, который содержит оптимизации расчёта обратных по модулю чисел для массива (т.е. дано число a и массив модулей [M1..Mn], надо для каждой пары найти [(a,M1), ..., (a,Mn)] обратное по модулю число invert(a, M)), увидел, что в коде используется следующее равенство:

(a mod x*y*z) mod x = a mod x

может кто-нибудь объяснить почему оно работает?  Понятно, что (a mod x) mod x = a mod x, а вот с произведением не совсем ясно. Числа x,y,z если что, простые.

Упростим до (a mod x*y) mod x = a mod x. Допустим, (a mod x*y) mod x = М, само собой M < x. Пусть a = R*(x*y) + S, где S < x*y. Тогда (a mod x*y) mod x = ((R*(x*y) + S) mod x*y) mod x = S mod X = M. Следовательно, S = K*x + M. Тогда a = R*(x*y) + S = R*(x*y) + K*x + M. И, наконец, a mod x = (R*(x*y) + K*x + M) mod x = M mod x = M = (a mod x*y) mod x.

Вот, на пальцах, еще одна цепочка рассуждений.
 Рассмотрим выражение z mod x. Если добавить к z число, кратное x то результат операции не изменится.  a-(a mod x*y) кратно x, что, в общем-то, очевидно, так как оно будет кратно x*y

Akina, ksnk
Спасибо, разобрался! 

Вот как сам понимаю:
если (a mod xy = 0), то (a mod x = 0) и (a mod y = 0) (если а делится на произведение без остатка, то на каждое число тоже будет делиться без остатка).

(a - a mod xy) mod xy = 0   ->   (a - a mod xy) mod x = 0

Как уже было сказано, к делимому можно добавлять/вычитать число, кратное делителю, результат не изменится, т.е. a mod x = (a + Nx) mod x. Вот тогда и вычтем:

(a - (a - a mod xy)) mod x = a mod x
(a - a + a mod xy) mod x = a mod x
(a mod xy) mod x = a mod x, что и требовалось доказать!