Свойства сравнений

1. Для всякого целого с a º b (mod m) Û a ± c º b ± c (mod m), то есть к обеим частям сравнения можно прибавить или вычесть из обеих частей одно и то же целое число.

2. Сравнения можно почленно складывать и вычитать: a º b (mod m) & c º d (mod m) Þ a ± c º b ± d (mod m).

& , Þ , Û .

3. Сравнения можно почленно перемножать: a º b (mod m) & c º d (mod m) Þ a × c º b × d (mod m).

& , Þ , Û .

4. Следствие из свойства 3. Сравнения можно почленно возводить в любую натуральную степень: a º b (mod m) Þ aⁿ º bⁿ (mod m) для .

5. Если в сравнении числа a, b, m имеют общий делитель d, то на него обе части сравнения и модуль можно сократить: a º b (mod m) Û a/d º b/d (mod m/d).

.

6. Обе части сравнения можно сократить на их общий множитель, взаимно простой с модулем: если a = a₁ × d, b = b₁ × d, (d, m) = 1, то a º b (mod m) Û a₁ º b₁ (mod m).

, Þ по свойству 6 делимости целых чисел, но так как (d, m) = 1, то по свойству 2 взаимно простых чисел, значит q = q₁ × d, q₁ Î Z. Таким образом, a º b (mod m) Û Û Û (mod m).

Легко проверяются следующие три свойства.

7. Рефлексивность: для любого целого а и всякого натурального m a º a (mod m).

Действительно, a – a = 0 и m | 0 по свойству 1 делимости целых чисел.

8. Симметричность: a º b (mod m) Û b º a (mod m).

m | (a – b) Û m | (b – a) по свойству 7 делимости целых чисел.

9. Транзитивность: если a º b (mod m) и b º c (mod m), то a º c (mod m).

a – c = (a – b) + (b – c), m | (a – b) & m | (b – c) Þ m | (a – c) по свойствам 5 и 6 делимости целых чисел.

Свойства 7–9 означают, что отношение сравнимости на множестве целых чисел Z есть отношение эквивалентности. Это означает, что Z разбивается на непересекающиеся классы попарно сравнимых друг с другом по модулю целых чисел.

Каждый класс сравнимых друг с другом целых чисел характеризуется общими свойствами представителей этого класса. Например, все они имеют один и тот же остаток от деления на модуль; все они в силу теорем 1.6.1 и 1.2.1 имеют одинаковый наибольший общий делитель с этим модулем.

, , где , .

, где , Þ (a, m) = (m, b).

§1.7. Множество классов вычетов

При делении целых чисел на натуральное число m существует m различных остатков: 0, 1, 2,…, m – 1. Соответственно этим остаткам Z разбивается на m непересекающихся классов сравнимых друг с другом чисел, имеющих, как отмечено в §1.6, один и тот же остаток от деления на m. В соответствии с остатками от деления на m эти классы будем обозначать , ,…, . Таким образом, класс = {× + | Î Z} для каждого = 0, 1, 2,…, m – 1. Любой представитель класса однозначно определяет свой класс, то есть для каждого × + класс = .

Поскольку остаток по-английски – «residue» – переводится на русский язык еще и как «вычет», то множество всех классов сравнимых друг с другом чисел по модулю m называют множеством классов вычетов по модулю m и обозначают Z/mZ. Таким образом, Z/mZ = – множество из m элементов. Заметим, что для любых классов , Î Z/mZ и для произвольных k₁, k₂ Î , l₁, l₂ Î суммы k₁ + l₁ и k₂ + l₂ принадлежат одному классу из Z/mZ, так как эти суммы сравнимы друг с другом по модулю m согласно свойству 2 сравнений из §1.6. Аналогично, согласно свойству 3 сравнений из §1.6 произведения k₁ × l₁ и k₂ × l₂ находятся в одном классе из Z/mZ.

Определим операции сложения и умножения на Z/mZ. Полагая, что сумма + = , где – такой единственный класс из Z/mZ, в который попадают все суммы + для k Î , l Î , а произведение × = – тот единственный класс из Z/mZ, в который попадают все произведения k × l для k Î , l Î .

, .

Поскольку сложение и умножение в Z/mZ однозначно определяются сложением и умножением представителей классов вычетов, то свойства 1–5 операций сложения и умножения в Z из §1.1 справедливы и в Z/mZ.

1. + = + , = – ассоциативность.

2. + = + , = – коммутативность.

3. Существует единственный нейтральный элемент: + = , = для " Î Z/m.

Пусть – нейтральный элемент. Тогда

Пусть – нейтральный элемент. Тогда .

При m = 1 – также нейтральный элемент относительно умножения.

4. Для всякого Î Z/mZ существует единственный противоположный класс такой, что + = , при этом = .

Пусть . Тогда

.

5. – дистрибутивность умножения относительно сложения.

Свойства 1, 2, 5 выполняются для всех Z/mZ.

Определение 1.7.1. Элемент Î Z/mZ называется обратимым, если найдется такой класс Î Z/mZ, что . Тогда называют обратным классом к .

При m = 1 , Z/Z = {} и состоит из одного обратимого класса вычетов.

Из ассоциативности умножения вытекает, что если – обратимый класс, то для него обратный класс определен однозначно.

Пусть . Тогда

.

Лемма 1.7.1. Пусть Î Z/mZ – такой класс, что (k, m) = 1. Тогда

1. для каждого ¹ × ¹ ;

2. , если ;

3. – обратимый класс в Z/mZ.

1.(k, m) = 1. Если бы $ l, 0 < l < m, такое, что , то m | k × l, но по свойству 2 взаимной простоты m | l, что невозможно.

2.Если бы при , то , то есть m | k × (l₁ – l₂), в силу свойства 2 взаимной простоты m | (l₁ – l₂), что невозможно, поскольку 0 < | l₁ – l₂ | < m.

3.По критерию взаимной простоты (теорема 1.4.1) $ u, v Î Z такие, что k × u + m × v = 1 Þ , то есть – обратимый класс, – обратный к нему класс.

Лемма 1.7.2.Пусть Î Z/mZ – такой класс, что (k, m) = d > 1. Тогда

1. существует ¹ такой, что × = ;

2. существуют такие, что ;

3. для всех ¹ × ¹ , то есть класс не обратим в Z/mZ.

1. Так как (k, m) = d > 1, то m = d × l, где 1 < l < m, k = d × k₁, (k₁, l) = 1 по свойству 1 взаимно простых чисел. Тогда , что означает при .

2. Существует с условием согласно утверждению 1 данной леммы. Рассмотрим Î Z/mZ, построим класс Î Z/mZ, . Тогда .

3. Если бы был обратим в Z/mZ, то существовал бы Î Z/mZ со свойством , то есть согласно условию 3 теоремы 1.6.1 k × u = 1 + m × q, q Î Z, Û k × u – m × q = 1 Û (k, m) = 1 (по критерию взаимной простоты), что не так.

Из лемм 1.7.1 и 1.7.2 вытекает следующая теорема.

Теорема 1.7.1. Класс Î Z/mZ обратим тогда и только тогда, когда (k, m) = 1. Произведение обратимых классов есть обратимый класс.

Первое утверждение следует из утверждений 3 лемм 1.7.1 и 1.7.2.

Пусть n ³ 2 и – обратимые классы, – соответственно обратные к ним классы. Тогда, поскольку операция умножения в Z/mZ коммутативна,

.

Следовательно, .

Следствие. Если p – простое число, то в Z/pZ каждый ненулевой класс обратим.

Поскольку Z/mZ состоит из конечного множества элементов, то сложение и умножение можно задавать поэлементно в виде таблиц. На пересечении i-й строки и j-го столбца таблицы пишется (где – знак операции). Так задавать алгебраические операции на конечном множестве впервые предложил известный английский математик XIX века Артур Кэли (1821–1895), поэтому такие таблицы называются таблицами Кэли.

Пример 1.7.1. Построим таблицы сложения и умножения в Z/3Z и в Z/4Z – таблицы 1.7.1 и 1.7.2 соответственно – и найдем обратимые элементы.

Z/3Z = = {3Z, 3Z + 1, 3Z + 2}.

Таблицы 1.7.1

+					×

Из таблицы умножения 1.7.1 видно, что классы и обратны сами себе.

Z/4Z = = {4Z, 4Z + 1, 4Z + 2, 4Z + 3}.

Таблицы 1.7.2

+						×

Из таблицы умножения 1.7.2 видно, что классы и обратны сами себе, а класс не обратим.·

Определение 1.7.2. Функция Эйлера (или тотиент-функция) j ставит в соответствие каждому натуральному m > 1 количество натуральных чисел, меньших m и взаимно простых с m.

Эта функция обладает следующими свойствами.

Теорема 1.7.2 (о вычислении значений функции Эйлера).

1. j(p) = p – 1 для каждого простого числа p.

2. j(p^s) = p^s – p^{s – 1}, ".

3. Если (n, m) = 1 то j(n × m) = j(n) × j(m).

4. Если – каноническое разложение числа n, то

.

1. Количество чисел множества {1, 2, 3,…, p – 1}, взаимно простых с p, равно p – 1, так как любое число этого множества взаимно просто с p.

2. Рассмотрим множество

{1, 2, 3,…, p – 1, p, p + 1,…, 2p,…, 3p,…, ,…, }.

Разобьем это множество на подмножества {1, 2, 3,…, p – 1, p}, {p + 1,…, 2p},…, {}. В каждом подмножестве число элементов, взаимно простых с p, равно p – 1. Всего таких подмножеств . Поэтому j(p^s) = (p – 1) × p^{s – 1} = p^s – p^{s – 1}.

3. Рассмотрим множество {1, 2,…, n, n + 1,…, 2n,…, (m – 1)n,…, mn}. Разобьем его на подмножества {1, 2, 3,…, n}, {n + 1, n + 2,…, 2n}, {2n + 1,…, 3n},…, {(m – 2)n + 1,…, (m – 1)n}, {(m – 1)n + 1,…, (m – 1)n + n = mn}. В первом подмножестве количество чисел, взаимно простых с , равно j(n) по определению. Во всех подмножествах числа имеют вид , , (b, n) = (n, r) (теорема 1.2.1), то есть количество чисел, взаимно простых с n, тоже равно j(n). Всего элементов, взаимно простых с n, в исходном множестве – j(n) × m. Числа, взаимно простые с m × n, взаимно просты с m и n одновременно. Пусть – числа первого подмножества, взаимно простые с n. Тогда , 0 £ k, l £ m – 1, k ¹ l, так как , ведь (n, m) = 1, 0 < | k – l | < m.

для фиксированного . Все множество чисел, взаимно простых с n, разобьем на j(n) подмножеств по m элементов в каждом, вычеты которых по модулю m все различны. В каждом множестве j(m) элементов, взаимно простых с m, так как их вычеты одинаковы в различных множествах, поэтому всего j(n) × j(m) элементов, взаимно простых с n и m одновременно.

4. Пусть – каноническое разложение числа n. Тогда

Пример 1.7.2. = 72 = 2³ × 3².

Следовательно, j(72) = (2³ – 2²) × (3² – 3) = 72 × (1 – 1/2) × (1 – 1/3) = 24.·

Из теоремы 1.7.1 следует, что в Z/mZ имеется в точности j(m) обратимых классов.

Пример 1.7.3. j(18) = j(2 × 3²) = 6, значит в Z/18Z имеется в точности 6 обратимых элементов. Ими являются классы .·

Теорема 1.7.3 (Л. Эйлер). Для " m Î N_>1, a Î Z (a, m) = 1 тогда и только тогда, когда a^j(m) º 1 (mod m).

Необходимость. Если (a, m) = 1, то – обратимый элемент Z/mZ по теореме 1.7.1. Пусть – все обратимые элементы в Z/mZ. Рассмотрим

.

Действительно, при i ¹ j по лемме 1.7.1, тогда , , – все различные обратимые классы по теореме 1.7.1. Следовательно,

Так как , то по свойству 6 сравнений a^j(m) º 1 (mod m).

Достаточность. , a^j(m) º 1 (mod m) Þ – обратимый элемент в Z/mZ Þ (a, m) = 1 (по теореме 1.7.1).

Следствие. В Z/mZ при m Î N_>1 всякий обратимый элемент обладает свойствами: 1) , 2) обратным к является класс

Теорема 1.7.4 (малая теорема Ферма). Пусть p – простое число, a Î Z не делится на p тогда и только тогда, когда 1 (mod p).

Доказательство следует из теоремы Эйлера, поскольку j(p) = p – 1.

Следствие 1. В Z/pZ обратным к ¹ является класс

Следствие 2. Если , m Î N_>1, для некоторого целого a при (a, m) = 1, то m – составное число.

Этот факт часто используется для проверки числа на простоту. Он позволяет установить наличие нетривиальных множителей данного числа m, не находя ни одного из таких множителей.