(a mod x*y*z) mod x = a mod x
может кто-нибудь объяснить почему оно работает?
Понятно, что (a mod x) mod x = a mod x, а вот с произведением не совсем ясно. Числа x,y,z если что, простые.| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Вопрос об арифметике по модулю |
| Автор: eXtremal7 16.1.2014, 23:32 |
| Анализируя код, который содержит оптимизации расчёта обратных по модулю чисел для массива (т.е. дано число 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 если что, простые. |
| Автор: Akina 17.1.2014, 07:43 |
| Упростим до (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. |
| Автор: ksnk 17.1.2014, 13:58 |
| Вот, на пальцах, еще одна цепочка рассуждений. Рассмотрим выражение z mod x. Если добавить к z число, кратное x то результат операции не изменится. a-(a mod x*y) кратно x, что, в общем-то, очевидно, так как оно будет кратно x*y |
| Автор: eXtremal7 17.1.2014, 20:20 |
| 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, что и требовалось доказать! |