Арифметика и теоремы вычисления остатков
Теория чисел – наука о целых числах. Из множества целых чисел можно перейти к множеству остатков по некоторому модулю. Понятие сравнимости по данному модулю было введено немецким учёным Карлом Гауссом. В своей книге «Арифметика исследования» (1801) К. Гаусс не только точно определил отношение сравнимости по данному модулю, но и систематически развил теорию сравнений – важнейший раздел теории чисел. На множестве остатков проще доказывать теоремы, производить вычисления, исследовать математические закономерности. Поэтому данная тема актуальна.
Остаток от деления целого числа a на натуральное число m называется такое число r, что a = mq + r и 0 ≤ r < m.
В общем виде понятие сравнимости по некоторому модулю m є N можно определить следующим образом:
Пусть m ≥ 1. Два числа a и b называются сравнимыми по модулю m, если их разность делится на m. Записывается это в виде a ≡ b (mod m).
Свойства сравнений: если a ≡ b (mod m) и c ≡ d (mod m), то a + c ≡ b + d (mod m) и ac ≡ bd (mod m).
Классом вычетов по данному модулю m называется множество всех целых чисел сравнимых с некоторым данным целым числом a по модулю m. Такой класс обозначается ā.
Полной системой вычетов по некоторому модулю называется система чисел, взятых по одному из каждого класса по этому модулю.
Приведённой системой вычетов по некоторому модулю m называется система чисел, взятых по одному из каждого класса, взаимно простого с модулем m (ā взаимно прост с модулем m, если само число а взаимно просто с m).
При делении на m могут получиться m различных остатков: 0, 1, 2, …, m-1. Каждому из них соответствует свой класс вычетов. Остатку а соответствует класс вычетов ā, состоящий из чисел вида а + km, где k – целое число: ā = {a + km | k є Z}. Всё множество Z целых чисел распадается на m классов вычетов по модулю m. Множество всех этих классов обозначают через Zm: Zm={ 0, 1,…, m-1}. При изучении вопросов, касающихся делимости на m, лучше иметь дело с конечным множеством Zm, чем с бесконечным множеством Z .
Арифметические операции над классами вычетов:
- Сложение: ƒ(a+b)=ƒ(a)+ƒ(b) (mod m), эта запись означает следующее: в каждом из слагаемых берут по представителю и складывают их, а потом смотрят, в какой класс вычетов попала сумма. Сумма не изменится, если мы будем брать разных представителей начальных классов вычетов.
- Вычитание ƒ(a-b)=ƒ(a)-ƒ(b).
- Умножение ƒ(a×b)=ƒ(a)׃(b).
- Возведение в степень ƒ(an)=(ƒ(a))n
- Вычитание, умножение, возведение в степень классов вычетов определяются точно так же, как и сложение.
- Деление: разделить класс вычетов ā на класс вычетов b – значит найти такой класс вычетов с, что ā × c = b. Для целых чисел задача неразрешима, когда произведение двух целых чисел равно нулю в случае, если один из множителей равен нулю. Но в Zm класс вычетов ā называется делителем нуля, если он отличен от 0, но существует такой класс b ≠ 0, что ā × b = 0. Например, 2 × 3 = 0 (mod 6). Значит, класс вычетов ā в Zm не является делителем нуля в том случае, когда (а,m)=1. И в Zp, где р – простое, деление всегда возможно.
Знаменитые теоремы теории чисел носят как будто бы частный характер. Но попытки их доказательства обогащают математику новыми идеями, методами, теориями. В этом и состоит непреходящее значение великих теорем. Докажем малую теорему Ферма, теоремы Эйлера, Вильсона, Лейбница, Китайскую теорему об остатках.
Малая теорема Ферма
Ферма Пьер (1601-1665) – французский математик и юрист. Один из основоположников теории чисел и математического анализа, работал аналитической геометрии. В теории чисел известность получили великая и малая теоремы Ферма.
Теорема: «Если p – простое число, то для каждого целого числа а число аp - a делится на p». Эту теорему можно сформулировать иначе: «Если p – простое число, ā ≠0, то ā p-1 = 1 (mod p)».
Доказательство: Так как 0 < ā < p, а модуль p – простое число, то (a,p)=1. Поэтому классы вычетов ā ×1, ā × 2, …, ā × (p-1) являются теми же самыми, что и 1, 2, …, p-1, только взятыми, в другом порядке (Лемма 1). (Докажем эту лемму: пусть даны классы вычетов k и t по модулю р. Нам нужно доказать, что если k ≠ t, то k × ā = t × ā . Пусть k × ā = t × ā , тогда ā ×(k - t) = 0. Теперь перейдём к целым числам: a×(k – t) делится на p, a не делится на p, значит (k – t) делится на p, но 0 Эйлер Леонард (1707-1783) – математик, механик, физик и астроном. По происхождению швейцарец. Автор свыше 800 работ по математическому анализу, дифференцированной геометрии, теории чисел, приближённым вычислениям, небесной механике, математической физике, оптике, баллистике, кораблестроению, теории музыки и др., оказавших значительное влияние на развитие науки.Теорема Эйлера
В теореме Ферма модуль p обязан быть простым числом. Эйлер открыл замечательное обобщение этой теоремы на случай составного модуля m. Классы вычетов 1, 2, …, (p-1), которые мы умножали на ā, взаимно просты с p. Возьмём и для составного модуля m лишь классы вычетов, взаимно простые с m, и обозначим их число через φ(m). Умножение этих классов на класс вычетов ā , взаимно простой с m, лишь переставляет их. Перемножая эти произведения и рассуждая так же, как при доказательстве Малой теоремы Ферма, приходим к следующему утверждению: «Если (ā, m)=1, то ā φ(m)=1 (mod m)» – теорема Эйлера. φ(m) – функция Эйлера, показывающая число взаимно простых чисел с m и меньших m.
Cвойства: для (m,n)=1 справедливо равенство: φ(m×n)=φ(m)×φ(n). Кроме того, если p – простое число, то φ(p)=p-1; φ(p2)=p2-p, и вообще φ(pm)=pm-1(p-1).
Эти свойства позволяют легко вычислять функцию Эйлера для небольших значений n. Например, φ(100)=φ(4)×φ(25)=φ(4)×φ(52)=2×5(5-1)=40 .
Комментарии