Модулярная арифметика. Поле по модулю. Деление по модулю. Функция Эйлера

9. Модулярная арифметика

Во всём последующем материале никак не фигурирует понятие “модуль числа” в привычном смысле (|x|). Речь идёт о “сравнении по модулю”. Если вы не знакомы с этим понятием, вкратце сравнение по модулю выглядит следующим образом:

a ≡ b mod m.

 

Это читается “a сравнимо с b по модулю m”, и в привычных для информатики терминах обозначает следующее:

(a − b) mod m = 0

или

a mod m=b mod m, где mod - операция взятия остатка от деления.

 

Поле по модулю

В некоторых задачах фигурирует условие следующего вида: “выведите остаток от деления ответа на 1000000007” или “выведите ответ по модулю 1000000007”. Это вовсе не значит, что вам нужно посчитать ответ обычным способом и вывести ans % 1000000007. Ответ в таких задачах часто настолько огромен, что его сложно представить даже с помощью длинной арифметики. Для их решения нужно вносить изменения во все промежуточные вычисления, чтобы не выйти за границы целочисленного типа.

 

Можно сказать, что в таких задачах мы оперируем не числами, а их остатками от деления на 1000000007. Это возможно благодаря следующим свойствам вычислений с остатком:

(a + b) mod m = ((a mod m) + (b mod m)) mod m

(a − b) mod m = ((a mod m) − (b mod m)) mod m

(a * b) mod m = ((a mod m) * (b mod m)) mod m

 

Таким образом, мы можем выполнять три важнейшие математические операции, даже не зная точных значений чисел, только их остатки от деления на заданное число (модуль).

 

Деление по модулю

Операция деления выполняется немного сложнее, чтобы её реализовать нам потребуются некоторые дополнительные сведения.

 

Функция Эйлера

phi(n) — это количество чисел от 1 до n, взаимно простых с n. Иными словами, это количество таких чисел в отрезке [1; n], наибольший общий делитель которых с n равен единице.

 

Свойства функции Эйлера

● Если p — простое число, то phi(p) = p - 1. Это очевидно, т. к. любое число, кроме самого p, взаимно просто с ним.

● Если p — простое, a — натуральное число, то phi(p^a) = p^a - p^(a-1). Поскольку с числом p^a не взаимнопросты только числа вида p*k (k натуральное), которых p^a / p = p^(a-1) штук.

● Если a и b взаимно простые, то ph(a * b) = phi(a) * phi(b) - "мультипликативность" функции Эйлера (что мы научимся использовать на полную позднее).

 

Докажем последнее свойство. Запишем n * m натуральных чисел, не превосходящих n * m, в виде прямоугольной таблицы с n столбцами и m строками, располагая первые n чисел в первой строке, вторые n чисел во второй и т. д.

Поскольку n и m взаимно просты, то целое s взаимно просто с n * m тогда и только тогда, когда оно взаимно просто как с n, так и с m. Итак, нужно доказать, что количество чисел в таблице, взаимно простых с n и с m равно phi(m) * phi(n).

В данном доказательстве мы используем тот факт, что число s взаимно просто с натуральным k тогда и только тогда, когда остаток деления s на k тоже взаимно прост с k. Данный факт довольно очевиден и используется в Алгоритме Евклида.

Теперь приступим непосредственно к доказательству. Число находящееся в i-ой строке и j-ом столбце нашей таблицы можно представить в виде n * (i−1) + j. Если это число взаимно просто с n, то и остаток этого числа по модулю n тоже взаимно прост с n. Но тогда и все числа в данном столбце тоже взаимно просты с n, так как весь столбец можно представить в виде арифметической прогрессии с разностью n, а при добавлении n остаток деления по модулю n не меняется. Поэтому, числа взаимно простые с n в таблице занимают ровно phi(n) столбцов.

Перед тем как продолжить доказательство, давайте рассмотрим небольшое утверждение. Пусть нам даны m последовательных членов арифметической прогрессии a, a + d, …, a + (m−1) * d. Тогда, если gcd(d,m)=1, то остатки всех этих m чисел по модулю m разные, а значит, образуют все множество остатков {0, …, m−1}, причем каждый остаток получается ровно из одного из членов прогрессии (x * d % m!= y * d % m, доказывается из того, что при данных условиях обе части можно поделить на d, реализовав это через умножение).

Воспользуемся данным утверждением, подставив разность арифметической прогрессии d=n. Тогда в каждом из phi(n) столбцов есть ровно phi(m) чисел, взаимно простых с m. Следовательно всего чисел, взаимно простых и с n и с m равно phi(m) * phi(n), что и требовалось доказать. Это очевидно, согласно тому, что число s взаимно просто с натуральным k тогда и только тогда, когда остаток деления s на k тоже взаимно прост с k.

 

       Отсюда можно получить функцию Эйлера для любого n через его факторизацию:

       Реализация

 

// функция Эйлера int getEuler(int x) {        int rs = x, t = x;        for (int i = 2; i * i <= x; ++i) {                    if (t % i == 0) {                                t /= i;                                rs -= rs / i;                                while (t % i == 0)                                            t /= i;                    }        }        if (t!= 1)                    rs -= rs / t;        return rs; }

 

       Можно реализовать и быстрее, если у нас есть факторизация полученная за меньшую асимптотику.