Как известно, если разделить пять яблок на троих енотов, появится остаток из двух кусочков. Пятый класс, вторая четверть. А как обстоят дела с делимостью в других кольцах?
Продолжаем развивать тему конечных арифметик, колец и полей. Ну, что, мы большие молодцы! Мы теперь кое-что знаем про кольца и таблицы умножения в них, про делители нуля и идеалы, про делители единицы, группы обратимых элементов и поля. И все это мы нашли не выходя за пределы пальцев двух рук (лап). Сейчас мы уже в достаточной степени подкованы, чтобы порассуждать о вопросе делимости чисел в наших двух арифметических системах.
Взять всё и поделить!
Разговор о делимости надо сразу начать с того, что появившееся в прошлый раз понятие поля проводит черту между алгебраическими системами, в которых вопрос делимости актуален, и теми, где он теряет смысл.
Мы привыкли к тому, что натуральные и целые числа бывают чётными и нечётными, круглыми (кратными 10) и нет, составными и простыми. В этих числах мы решаем задачи на поиск наибольшего общего делителя и наименьшего общего кратного, используем алгоритм Евклида и так к этому привыкли, что уже подчас не замечаем, что в рациональных числах всего этого нет. При том, что в целых числителях и натуральных знаменателях дробей вопросы делимости актуальны, сами дроби делятся друг на друга в любых сочетаниях и без всяких проблем. И связано это с тем, что любое ненулевое рациональное число обратимо и входит в мультипликативную группу обратимых элементов, а значит, с точки зрения алгебры, рациональные числа образуют уже не кольцо, а поле.
На школьном пути постижения алгебраических структур мы приучаемся к мысли о том, что расширение наших возможностей связано с пополнением привычной числовой системы чем-то новым. От натуральных чисел мы переходим к целым, добавляя отрицательные (противоположные) числа и это даёт нам возможность вычитать любые числа друг из друга. Далее от целых переходим к рациональным, добавляя пары чисел, называемые дробями, которые позволяют формально делить любые числа на любые ненулевые. От рациональных переходим к вещественным, пополняя их корнями неразрешимых рациональных уравнений и трансцендентными величинами, а на самом деле, просто разрешая существовать пределам всех мыслимых сходящихся последовательностей. И, наконец, добавляя мнимую единицу, то есть корень ещё одного неразрешимого вещественного уравнения, переходим к комплексным числам, алгебраически замыкая числовую систему, и позволяя возводить любые числа в любые степени.
Однако, в самом начале этого пути, можно было получить полноценное поле не пополняя систему натуральных чисел, а напротив, сокращая её, и переходя в конечную арифметику вычетов. Так, полем может быть любое конечное кольцо без делителей нуля, а значит, все кольца вычетов ℤ/pℤ с простым p, позволяют не только складывать, вычитать и перемножать любые входящие в них числа, но и находить их отношения (решать любые корректные линейные уравнения) а так же возводить любые числа в любые доступные степени. И хотя сами эти системы не являются алгебраически замкнутыми (в них нельзя выразить решение произвольного алгебраического уравнения), в начале XIX века французский математик Эварист Галуа показал, каким образом их можно пополнять, оставляя полями. А почти век спустя, немецкий математик Курт Гензель показал способ перейти от них к комплексным числам минуя вещественные.
Так что наши игрушечные поля вовсе не игрушки, а способны стать мощным инструментом в теории чисел и алгебре. Но, повторю, в полях любые вопросы делимости "уже всё". Тривиальны.
Таким образом, мы заключаем, что в ℤ/5ℤ нет не только простых чисел, но даже разделение чисел на чётные и нечётные не имеет смысла. Выходит, теорию делимости на пяти пальцах толком не объяснить. А на десяти?
В кольце ℤ/10ℤ есть шанс. Давайте начнём наши соображения со знаменитого алгоритма Евклида, который мы используем в школе для того, чтобы выявлять общие делители и взаимно простые числа.
Сегодня нашим главным инструментом будут "звёздочки", то есть, прыжки по кольцу вычетов через равное количество делений.
В целых и натуральных числах, желая выяснить остаток от деления одного числа на другое, мы можем вычитать из большего числа меньшее, до тех пор, пока не получим число, не превышающее делитель.
Про отношение порядка (то есть, кто кого меньше или больше) в кольцах вычетов мы пока не задумывались, но это отдельный разговор. Спросите себя, если среда идет после понедельника, но перед воскресеньем, значит ли это, что воскресенье не может быть перед понедельником? Однако мы можем сравнивать не сами элементы ℤ/10ℤ, а например, расстояние от нуля, отсчитываемое на циферблате. Так 1 и 9 отстоят от нуля на 1 шаг, а 2 и 8 — на 2 шага, и т.д. Обозначим это расстояние как |x| и назовём нормой. А поскольку это просто натуральное число, то для него определено нормальное отношение порядка:
|0| < |±1| < |±2| < |±3| < |±4| < |5|.
Давайте выясним с помощью вычитания, как делится, например, 7 на 2 в целых числах и в кольце ℤ/10ℤ:
Раз |1| < |2|, то можем сказать, что у нас всё получилось 7 = 3×2+1 в обеих арифметиках. Вроде бы, всё в порядке. И вообще, если начиная с единицы построить в ℤ/10ℤ звёздочку с шагом 2, то мы получим все числа, дающие в остатке от деления на 2 единицу, то есть, нечётные числа: {1,3,5,7,9}, а если начнём с нуля, — то все чётные {0,2,4,6,8}.
Полученные нами подмножества не пересекаются, а их объединение равно всему множеству чисел. В таких случаях говорят, что всё множество удалось разбить на смежные классы.
Хорошо, а что с делимостью на 3? Точно таким же способом, с помощью многократного вычитания, мы можем выяснить, что остаток от деления 7 на 3 тоже равен 1. И вообще:
4 = 1×3 + 1, 5 = 1×3 + 2, 6 = 2×3 + 0, 7 = 2×3 + 1 и т. д.
Получается, что и тут никаких проблем нет!
Но, всё-таки, они есть. Вычитание это операция обратная сложению, значит с помощью сложения мы тоже должны получить множества чисел, имеющих одинаковый остаток. Однако, как мы знаем, тройка обратимый элемент в ℤ/10ℤ, и её "звёздочка" проходит все числа без исключения, с какого бы числа мы ни начали обход. Значит ли это, что все числа в ℤ/10ℤ делятся на 3 без остатка? А как же наши вычисления с помощью вычитания и нормы? Дело в том, что они, в присутствии делителей единицы, могут дать некорректный результат. Смотрите, мы получили, например, вычитанием что 4 = 1×3 + 1. Но мы знаем, что 1 = 3×7, а значит 4 = 1×3 +3×7 = 3×8, то есть 4 можно поделить на 3 без остатка, получив 8. Это противоречие говорит не только о том, что выбранный нами метод вычисления остатка от деления некорректен, но и что разложение числа в форме a = bq + r, где |r| < |b| не единственно. Или, иными словами, разбить на смежные классы по остаткам от деления 3 множество чисел в ℤ/10ℤ не получится.
Попытка с помощью звëздочки выделить числа, кратные четырём тоже обречена на провал: ими окажутся не только все чётные числа, включая 6 и 2, но при этом любое число будет одновременно иметь два разложения:
a = b×4 + 1 = b'×4 + 3, либо a = b×4 + 0 = b'×4 + 2.
В то же время, с делимостью на 5 у нас снова не будет никаких проблем! Все числа будут иметь единственное разложение и внятный корректный остаток. Убедитесь в этом сами с помощью "звёздочек".
Что на что делится, а что на что нет?
Подводим итог. В кольце ℤ/10ℤ можно корректно определить делимость только на 2 и на 5. Все остальные числа либо ведут себя, как единица, то есть, делят нацело всех без разбора, либо делят числа с остатком не единственным образом.
Легко понять, что подобно единице ведут себя обратимые элементы, а 2 и 5 — это числа, которые порождают идеалы нашего кольца. Любой идеал, который можно получить просто многократным прибавлением одного и того же элемента, называется главным идеалом, а число, его порождающее — генератором. Получается, что в ℤ/10ℤ деление с остатком корректно определяется только для генераторов главных идеалов.
Раз деление с остатком некорректно в общем случае, то и алгоритм Евклида для нахождения наименьшего общего делителя нам не применить. Да и сам этот общий делитель может быть неоднозначным.
Ух, как всё непросто! Но давайте теперь взглянем с позиции теории колец на привычные целые числа.
В ℤ только два обратимых элемента: ±1, которые делят все числа без остатка. Все идеалы в ℤ главные, и имеют вид nℤ, то есть генерируются произвольным от нуля числом n. А это значит, что понятие остатка от деления корректно для всех чисел из ℤ. Вот почему в целых числах работают и деление с остатком, и алгоритм Евклида, и китайская теорема об остатках и другие плюшки. Такие кольца называются евклидовыми.
При этом все целые числа можно разбить с помощью числа n на смежные классы с одинаковыми остатками от деления на число n. Один из них, содержащий ноль, будет идеалом nℤ, все другие могут быть получены из этого идеала прибавлением остатка ко всем его элементам. Такое разбиение обозначается знаком / и называется факторизацией.
А если вспомнить, что сумма, разность и произведение любых элементов идеала остаётся внутри него, то это означает, что при сложении двух элементов разных классов, например, x ∈ nℤ + a и y ∈ nℤ + b, идеальная часть останется идеальной, а все операции будут проводиться только с остатками. Так что x + y попадёт в класс nℤ + a + b. Это же верно и для вычитания с умножением. Получается, что классы образуют самостоятельное кольцо (не являющееся подкольцом ℤ), которое получается факторизацией кольца целых чисел по идеалу nℤ, то есть ℤ/nℤ. Вот откуда взялись термин "идеальные числа" и принятое обозначение колец вычетов.
Получается, делить можно не только числа, но и кольца!
* * *
Итак. В кольцах вычетов корректно делить с остатком можно только на числа, которые генерируют главные идеалы. Все делители единицы ведут себя как единица и делят любое число без остатка. В евклидовых полях все идеалы главные и в них имеется содержательная теория делимости. В полях же все числа обратимы, а значит, они все ведут себя, как единицы и вопрос делимости становится тривиальным.
В следующий раз мы уже сможем рассмотреть, как работает основная теорема арифметики в кольцах вычетов и какие числа можно называть простыми.
Задание-вопросы:
• А интересно, на какие числа можно делить с остатком на циферблате часов, то есть в кольце ℤ/12ℤ?
• Что мы получим, если факторизуем ℤ/10ℤ по идеалам {0,2,4,6,8}, и {0,5}?