Согласно теореме о единственности разложения на простые множители, простые числа являются теми «кирпичиками», из которых строятся целые числа. Помимо ±2, все остальные простые числа нечетны, так как четным число называется только когда оно делится на 2. Уже Евклиду было известно, что простых чисел бесконечно много. Он доказал это, заметив, что число N = (p₁p₂...p_n) + 1 (где p₁, p₂, ..., p_n – все простые числа) не делится ни на одно простое число p₁, p₂, ..., p_n и, потому либо само N, либо один из его простых множителей должен быть простым числом, отличным от p₁, p₂, ..., p_n. Следовательно, p₁, p₂, ..., p_n не может быть полным перечнем всех простых чисел.

Пусть m і 1 – некоторое заданное целое число. Любое число a при делении на m дает остаток, равный одному из чисел 0, 1, ..., m – 1. (Например, при m = 13 и a, принимающем последовательно значения 29, 7, -21, 65, получаем: 29 = 2Ч3 + 3, 7 = 0Ч13 + 7, –21 = –2Ч13 + 5, 65 = 5Ч13 + 0, и остатки равны соответственно 3, 7, 5, 0.) Если числа a и b при делении на m дают один и тот же остаток, то в некоторых случаях их можно рассматривать как эквивалентные относительно m. Математики говорят в таких случаях, что числа a и b сравнимы по модулю m, что записывается так: a є b (mod m) и называется сравнением по модулю m. Мы все знакомы со сравнением по модулю 12 в случае с часами: 17 часов означает то же самое, что 5 часов пополудни, так как 17 є 5 (mod 12). Это отношение, называемое сравнением, было введено К.Гауссом (1777–1855). Оно несколько похоже на равенство тем, что сравнения по одному и тому же модулю m можно складывать и умножать, как обычно: если a є b (mod m) и c є d (mod m), то a + c є b + d (mod m), a – c є b – d (mod m), aЧc є bЧd (mod m) и ta є tb (mod m) при любом целом t. Сокращение на общий множитель, вообще говоря, невозможно, т.к. 20 є 32 (mod 6), но 5 № 8 (mod 6). Однако если ta є tb (mod m) и (t,m) = d, то a є b (mod (m/d)). При d = 1 это по существу сводится к сокращению на общий множитель; например, 28 є 40 (mod 3), и так как числа 4 и 3 взаимно простые, мы можем разделить обе части сравнения на 4 и получить 7 є 10 (mod 3). Можно также показать, что если a є b (mod m), то НОД чисел a и m равен НОД чисел b и m. В качестве примера рассмотрим сравнение 6 є 10 (mod 4): НОД (6, 4) равен 2, и НОД (10, 4) также равен 2.

Все целые числа, сравнимые с каким-либо числом, образуют один класс вычетов. Для каждого модуля m существует m классов вычетов, соответствующих m остаткам 0, 1, ..., m - 1; каждый из классов содержит одно из чисел 0, 1, ..., m – 1 вместе со всеми числами, сравнимыми с этим числом по модулю m. Если два числа a и b принадлежат одному классу вычетов, т.е. удовлетворяют соотношению a є b (mod m), то НОД (a,m) = НОД (b,m); следовательно, либо все элементы данного класса вычетов взаимно просты с m, либо ни один не взаимно прост. Число «приведенных» классов вычетов, т.е. классов вычетов, элементы которых взаимно просты с m, обозначается f (m). Таким образом возникает функция на множестве целых чисел, называемая f-функцией Эйлера в честь Л.Эйлера (1707–1783). При m = 6 существует шесть классов вычетов, каждый из которых содержит одно из чисел 0, 1, ..., 5. С этим m взаимно просты только элементы класса, содержащего число 5, и класса, содержащего число 1. Следовательно, f (m) = 2.

Как и в случае уравнений, можно рассматривать сравнения с одним или более неизвестными. Простейшим служит линейное сравнение с одним неизвестным ax є b (mod m). Оно выполняется только в том случае, когда m делит число (ax – b), или ax – b = my при некотором целом y. Таким образом, это сравнение эквивалентно линейному уравнению ax – my = b. Так как левая его часть обязательно делится на НОД (a, m), оно не может выполняться ни при каких целых числах x и y, если НОД (a, m) не делит число b.

Можно показать, что сравнение ax є b (mod m) разрешимо в том и только в том случае, когда НОД (a, m) делит число b, а если это условие выполнено, то существует ровно НОД (a, m) классов вычетов по модулю m, элементы которых удовлетворяют этому сравнению. Например, уравнение 2x + 6y = 5 неразрешимо в целых числах, т.к. НОД (2, 6) = 2, а число 5 не делится на 2; уравнение 2x + 3y = 5 разрешимо, т.к. НОД (2, 3) = 1; аналогично, уравнение 2x + 3y = b разрешимо при любом целом b. Действительно, при любых a и m, таких, что НОД (a, m) = 1, уравнение ax – my = b разрешимо для любого b.

Уравнение ax – my = b – это, по-видимому, простейший пример «диофантова уравнения», т.е. уравнения с целыми коэффициентами, которое требуется решить в целых числах.

Общее квадратичное сравнение ax² + bx + c є 0 (mod m) можно проанализировать весьма полно. Умножая на 4a, получаем 4a²x² + 4abx + 4ac є 0 (mod 4am), или (2ax + b)² є (b² – 4ac) (mod 4am). Полагая 2ax + b = u и b² – 4ac = r, мы сводим решение исходного сравнения к решению сравнения u² є r (mod 4am). В свою очередь решения последнего сравнения с помощью чуть более сложных рассуждений можно свести к решению сравнений вида u² є r (mod p), где p – простое число. Поэтому все сложности и весь интерес кроются в этом, казалось бы, частном случае общего квадратичного сравнения. Если сравнение u² є r (mod p) разрешимо, то u называется квадратичным вычетом по модулю p, а в противном случае – квадратичным невычетом. «Квадратичный закон взаимности», открытый эмпирически Эйлером (ок. 1772) и доказанный Гауссом (1801), утверждает, что если p и q – различные нечетные простые числа, то каждое из них или является квадратичным вычетом по модулю другого, или это не верно ни для одного из них за исключением случая, когда и p, и q имеют вид 4k + 3 и когда лишь одно из этих чисел является квадратичным вычетом по модулю другого. Теорема Гаусса, названная им «золотой теоремой», служит мощным инструментом теоретико-числовых исследований и позволяет ответить на вопрос, разрешимо ли данное квадратичное сравнение.

Сравнения более высоких степеней вида f (x) є 0 (mod m), где f (x) – многочлен степени выше 2, решаются с большим трудом. Согласно теореме Ж.Лагранжа (1736 – 1813), число решений (точнее, число классов вычетов, каждый из элементов которых является решением) не превышает степени многочлена f (x), если модуль простой. Существует простой критерий разрешимости сравнения xⁿ є r (mod p), принадлежащий Эйлеру, но он неприменим к сравнениям общего вида, о разрешимости которых при n > 2 мало что известно.

назад   дальше