Математическая продлёнка. Теория чисел на пальцах
Представляю вашему вниманию собранные в одну статью заметки к циклу занятий математического кружка, посвящённых элементам теории чисел. Кружковая математика не только про олимпиады, про успеваемость в школе и про хитровыдуманные задачки на смекалку. Это и расширение эрудиции, и небольшие самостоятельные исследования и своеобразные «экскурсии к предгорьям» большой математики.
Статья посвящена модулярным арифметикам, простым для понимания и доступным для экспериментов алгебраическим структурам, которые, тем не менее, способны показать «внутреннее устройство» числовой системы и познакомить с элементами теории чисел и теории колец. Это ни в коем случае не учебник по алгебре, не учебное пособие и не туториал в духе «теория колец за 10 минут». Это неформальное приглашение к исследованию тех, кому любопытно, что же мы имеем в виду, когда говорим слово «число».
Пусть вас не смущает сочетание довольно вольного изложения с серьёзными терминами и уравнениями. Это вполне обычно для математического кружка, в котором, с одной стороны, публика уже достаточно искушена и готова к трудностям, а с другой стороны состоит из неофитов, причём, достаточно молодых. Думаю, и для первокурсника, приступившего к изучению аглебры, эти заметки могут быть небесполезны.
Когда маленькие круче больших
Все мы знаем и любим целые числа. У них есть куча достоинств! С них начинается арифметика и знакомство с нетривиальной математикой. Целые числа можно складывать и вычитать, а также перемножать и решать разнообразные уравнения, которые называются диофантовыми. Правда, математики их, мягко говоря, недолюбливают, потому что общих методов их решения немного и задачи, которые выглядят простыми, на деле оказываются сверхсложными или почти неразрешимыми.
А если использовать не все целые числа сразу, а только их конечное подмножество? Действуя аккуратно, из них можно сооружать небольшие полноценные арифметики. Самые простые из них — модулярные арифметики. Они получаются когда мы от числовой прямой переходим к «числовой окружности», разбивая её на равные части, как на циферблате. Если арифметику целых чисел обозначают ℤ, то для арифметик на циферблате с 
делениями используется обозначение ℤ/nℤ.
Когда дело касается исчисления времени, мы пользуемся именно такими арифметиками, считая минуты (ℤ/60ℤ), часы (ℤ/24ℤ), месяцы (ℤ/12ℤ) и дни недели (ℤ/7ℤ), градусы для измерения углов (ℤ/360ℤ). Цифры, которые мы используем в позиционной системе счисления тоже образуют конечную арифметику ℤ/10ℤ. А компьютеры, логики и грамотные IT-шники используют двоичное счисление, основанное на самой маленькой нетривиальной арифметике с двумя элементами ℤ/2ℤ.
Примеры модулярных арифметик
Разумно предположить, что маленькие конечные арифметики окажутся слабее «большой» ℤ с бесконечным числом элементов. Например, в ℤ/10ℤ нет моего любимого числа 13. Однако, кое в чём они могут быть и сильнее.
Во-первых, таких арифметик много — столько же, сколько натуральных чисел, и каждая из них имеет свои особенности, делающие её непохожей на остальные. Во-вторых, конечные арифметики содержат конечное число элементов, а значит, задачи в них можно решать простым перебором. В-третьих, некоторые диофантовы уравнения, которые сложно или невозможно решить в ℤ, могут иметь решения в конечных арифметиках.
Вот несколько примеров для разогрева.
Отрицательные числа и формальные дроби
В арифметике ℤ/5ℤ из пяти элементов у каждого элемента есть противоположный, то есть такой, что в сумме они дают ноль. То есть, в этом смысле оно включает в себя и «отрицательные числа»: 
Более того, в этой системе у любого корректного линейного уравнения 
, есть решение, которое записывается формальной дробью 
. Таким образом, оно содержит в себе все возможные корректные формальные дроби, не существующие в целых числах:
Большая теорема Ферма
Большая теорема Ферма, гласит, что в ℤ уравнение 
не имеет нетривиальных решений при
Наконец, доказана теорема Шу́ра, утверждающая, что для любого натурального
найдется натуральное число 
, такое, что для простого 
, решающее уравнение 
, не существует не только в ℤ, но и в вещественных числах. Однако, это уравнение решается, например, в ℤ/5ℤ, потому что 
. И вообще, это уравнение имеет решения в арифметиках ℤ/mℤ, где m кратно 2, 5, 13, 17, 29 и т. д. Только не надо думать что 2 это некая мнимая единица в ℤ/5ℤ, это рядовое число.
Автоморфные числа
А вот ещё один пример числа, не существующего ни в ℤ, ни в ℝ. Это решение уравнения 
, отличное от 0 и 1. Такие числа, например, существуют в арифметиках ℤ/10ℤ, ℤ/100ℤ, ℤ/1000ℤ и т.д. Смотрите сами:
Золотое сечение
Уравнение 
имеет два иррациональных решения, которые связаны с числами Фибоначчи. Одно из них, положительное, называется золотым сечением и обозначается 
. В ℤ таких чисел нет, а в ℝ, как известно, 
. Это уравнение решается во всех модулярных арифметиках, содержащих 
(арифметиках ℤ/mℤ, в которых 
). Самая простая из них — ℤ/11ℤ, в которой 
. Во всех этих арифметиках можно напрямую использовать знаменитую формулу Бине, которая позволяет в конечной форме вычислить k-ое число Фибоначчи. Впрочем, о том, почему использовать формулу Бине можно там, где это уравнение не решается (как в ℤ, например), стоит поговорить отдельно, но для этого нужно хоть немного познакомиться с тем, что такое алгебраическая структура под названием кольцо
Может возникнуть вопрос:, а почему я называю конечные арифметики арифметиками? Достаточно ли возможности складывать и умножать для того, чтобы носить это гордое имя? Как в них обстоят дела с делимостью, с решением уравнений, с простыми числами, с основной теоремой арифметики, наконец? Сразу скажу, тут всё непросто. Но ведь тем и интереснее! К тому же, как известно, распределение простых чисел и в привычной нам арифметике целых чисел представляет многовековую загадку.
Звёздочки и колечки
У большинства из нас с вами на руках по пять пальцев. Так что для экспериментов и препарирования мы будем использовать ℤ/5ℤ и ℤ/10ℤ, которые образуют одна и две наши руки. Благо, они у нас всегда есть перед глазами.
Начнём мы свой анализ с того, что станем сосредоточенно возить пальцем по кругу. Нарисуем циферблат с пятью делениями и пройдёмся по нему, делая шаги по одному, два, три и четыре деления:
Шаги по циферблату ℤ/5ℤ.
Мы получили симпатичные «звёздочки», которые демонстрируют построение таблицы умножения в ℤ/5ℤ. Каждая из этих «звёздочек» соответствует своему ряду в таблице умножения.
Сложение и умножение в ℤ/5ℤ.
Таблица сложения в этой арифметике устроена очень просто: каждая строка получается циклическим сдвигом предыдущей. Это соответствует идее сложения, как сдвига числовой оси, но поскольку ось у нас зациклена, то роль сложения с числом на циферблате выполняет поворот всего циферблата на соответствующее числу количество делений.
В ℤ/5ℤ верно, что 1 + 4 = 2 + 3 = 0, а значит пары чисел (1, 4) и (2, 3), это пары противоположных друг другу чисел. Это же показывают и «звёздочки»: умножение на 1 и умножение на 4 выглядят одинаково, но производятся в противоположную сторону. То же верно и для умножения на 2 и на 3.
Противоположными положительным числам в целых числах являются отрицательные. Но в нашей конечной арифметике отрицательных чисел нет, а их роль берут на себя обыкновенные числа. Поэтому мы не будем использовать термин «отрицательные числа» применительно к конечным арифметикам, поскольку каждое число одновременно является и положительным и отрицательным. Например, раз 3 + 2 = 0, то −3 = 2, и в тоже время −2 = 3. Лучше говорить, что 2 и 3 противоположны друг другу.
Из симметрии, которую образуют противоположные числа, следует симметрия таблицы умножения относительно диагонали, идущей из левого нижнего угла в правый верхний. А то что эта таблица симметрична относительно другой диагонали, идущей от левого верхнего угла до правого нижнего, значит, что для умножения выполняется перестановочный закон. Алгебраисты говорят, что в таком случае »умножение коммутативно». Кроме того, для умножения выполняется и сочетательный закон: 
. Это свойство у алгебраистов называется ассоциативностью, оно позволяет не писать лишних скобок. Кроме того, для умножения в ℤ/5ℤ выполняется распределительный закон, который алгебраисты зовут дистрибутивностью.
В отличие от привычной нам арифметики, геометрически продемонстрировать эти два закона для конечной арифметики не так просто. Но поскольку она конечна, то можно просто перебрать все сочетания из трёх элементов и убедиться в их справедливости. Сейчас поверьте мне, или проверьте сами, но все эти законы выполняются.
А ещё обратите внимание на то, что все «звёздочки» в ℤ/5ℤ честно проходят через все числа. Это интересно: многократным вычитанием любого числа из любого можно попасть в ноль, а это значит, что в нашем кольце любое число делится на любое число. Но об этом мы подробнее поговорим позже.
Перед тем, как продолжать, надо поговорить про правильные имена и названия. У нас тут не учебник, а занимательные заметки, однако термины — вещь нужная и точность в них небесполезна. С этого момента я буду избегать слова «арифметика», а вместо этого стану использовать более точный математический термин кольцо, который придумал Рихард Дедекинд, а в широкий обиход ввел великий Давид Гильберт.
Кольцом в математике называются числовые системы, в которых определена операция сложения с перестановочным и сочетательным законами, а также операция умножения с сочетательным и распределительным законами.
Все эти законы те же самые, что мы проходили в школе. Кроме того, все элементы кольца можно разбить на пары противоположных друг другу так, что числа в этих парах в сумме дают ноль.
Легко убедиться, что числовое кольцо образуют целые числа. А любимые нами натуральные — не образуют, поскольку среди них нет противоположных (отрицательных) чисел. Рациональные и вещественные числа тоже образуют кольца. Исследованием свойств этих и куда более сложных объектов занимается весьма содержательный раздел алгебры: теория колец.
Так что мы теперь можем сказать, что числа на круглом циферблате с пятью делениями образуют кольцо ℤ/5ℤ с циклическим сдвигом в качестве операции сложения и многократным повторением сдвига в качестве умножения. И вообще, циферблаты с любым числом одинаковых делений и описанными выше операциями, образуют кольца. Такие арифметики называются кольцами вычетов или модулярными арифметиками. Кроме них можно строить и другие конечные кольца, но этим мы пока заниматься не будем. Хватит с нас пока и алгебры «на пальцах».
Сейчас мы не просто балуемся с отвлечёнными математическими конструкциями, мы следуем путём Леонарда Эйлера, заложившего основы теории делимости, Фридриха Гаусса, детально исследовавшего модулярные арифметики, а также Рихарда Дедекинда, Давида Гильберта, Эмми Нёттер и других замечательных математиков. Результаты теории вычетов и теории колец сейчас лежат в основе алгебраической геометрии и используются для решения ряда прикладных задач геометрии, комбинаторики, криптографии и т.д.
Ну что, посмотрим что у нас делается в кольце ℤ/10ℤ? Опять сначала нарисуем звёздочки:
Шаги по циферблату ℤ/10ℤ.
Тут у нас получился целый цветник разнообразных звёздочек! Симметрия между противоположными числами тут тоже очевидна: все числа делятся на пары противоположных, в сумме дающих 0: (1, 9), (2, 8), (3, 7), (4, 6), (5, 5). Число 5 особенное — оно противоположно самому себе, как число ноль. Ни в ℤ, ни в ℤ/5ℤ таких чисел, кроме нуля, нет.
Таблица сложения в этой арифметике устроена также как и в ℤ/5ℤ: каждая строка получается циклическим сдвигом предыдущей, так что рисовать мы её не будем, а сразу перейдём к таблице умножения:
Таблица умножения для ℤ/10ℤ.
Эта таблица нам уже знакома, она заполнена младшими разрядами привычной таблицы Пифагора. Есть в ней несколько по-настоящему занятных особенностей. Во-первых, в ней появились нули, как результат перемножения чётных чисел с пятёркой. Во-вторых, есть строчки, в которых присутствуют все числа, а есть те, в которых наблюдаются только чётные. В отличие от ℤ/5ℤ, некоторые «звёздочки» проходят не по всем числам, а проскакивают часть из них. Это значит, что в этом кольце некоторые числа могут не делиться на другие, а это значит, что в кольце ℤ/10ℤ имеет смысл рассуждать о простых и составных числах, тогда как в ℤ/5ℤ такого разделения чисел нет.
Заучивать полученные таблицы сложения и умножения не нужно, потому что выбранные нами кольца очень удобны для пятипалых математиков. Чтобы вычислить сумму или произведение двух чисел в ℤ/10ℤ достаточно вычислить его в целых числах и оставить только последнюю цифру. Например, 6×8 + 4 = 52 в ℤ и 6×8 + 4 = 2 в ℤ/10ℤ. В кольце ℤ/5ℤ всë то же самое, как и в ℤ/10ℤ, только если ответ вышел больше пяти, нужно вычесть из него пятерку. Таким образом 6 = 1, 7 = 2, 8 = 3 и 9 = 4.
Задания для дальнейших исследований:
Постройте звёздочки и таблицу умножения для циферблата обычных часов, то есть, для кольца ℤ/12ℤ.
Поищите в кольце ℤ/12ℤ интересные элементы, например, квадратные корни чисел.
Чему равны сумма и произведение всех элементов конечного кольца?
Делители нуля
Главная особенность, которая бросается в глаза: в таблице умножения для ℤ/10ℤ есть нули. Это интересно! Раз 2×5 = 0, то это значит, что произведение двух ненулевых чисел смогло стать нулевым. Получается, что в ℤ/10ℤ все чётные числа и пятёрки являются делителями нуля. Формально значит, можно записать что 2 = 0/5.
Целых чисел очень и очень много, но среди них нет ни одного делителя нуля, то есть такого числа x, которое могло бы быть решением уравнения: 
Школьникам, заучивающим таблицу умножения, делители нуля только на руку: чем больше круглых чисел в ней окажется, тем проще учить. Но с точки зрения алгебры, это, прямо скажем, неприятность. Она означает, что решать уравнения типа 
не так просто, как в целых числах, поскольку никаких гарантий, что какое-то из множителей равно нулю нет. Вместо этого, мы имеем целых 2×4 + 2 = 10 вариантов, которые нужно проанализировать, чтобы получить верное равенство.
А вот в кольце ℤ/5ℤ такого безобразия нет, так что в этом смысле ℤ/5ℤ ближе к целым числам, чем ℤ/10ℤ. Кольца, без делителей нуля называются областями целостности. Самый привычный для нас пример области целостности — целые числа (отсюда и название).
Кто прячется в кольце?
Что ещё интересного можно сказать про делители нуля в ℤ/10ℤ? Давайте выпишем их все: это числа 2, 4, 6, 8 и 5. Вот как выглядят «звездочки» на циферблате для этих чисел:
А теперь сравним их с устройством кольца ℤ/5ℤ:
Смотрите-ка делители нуля образуют внутри ℤ/10ℤ полноценное кольцо идентичное ℤ/5ℤ. А «звездочка» для числа 5 в ℤ/10ℤ соответствует кольцу всего с двумя делениями ℤ/2ℤ.
Подкольца и идеалы
Кольцо ℤ/10ℤ, действительно, содержит внутри себя два полноценных кольца с элементами 
и 
. Мы обозначим их, соответственно, 2ℤ/10ℤ и 5ℤ/10ℤ. Причём, если , опять же, формально, «сократить» числа в обозначении колец, то 2ℤ/10ℤ ≃ ℤ/5ℤ, а 5ℤ/10ℤ ≃ ℤ/2ℤ. Это подобие мы и наблюдали на звёздочках. Обозначение колец имеет такой смысл, чтобы подобное сокращение стало возможным. О смысле знака 
мы поговорим позже.
Давайте обратим внимание вот на что. Если оперировать только чётными числами и нулём, то любая их сумма будет чётной, так же как и любое их произведение. Это же относится и к числам, кратным пяти: сложение и перемножение этих чисел в результате опять производят числа, кратные пяти. Это свойство множеств называется замкнутостью относительно той или иной операции.
Тут важно заметить, что под операциями сложения и умножения в этих кольцах понимаются операции из ℤ/10ℤ. Это тонкий момент. Сумма чисел 2 и 6 будет разной в разных кольцах: например, в кольце ℤ/5ℤ, где 6 = 5 + 1 = 1, их сумма равна 3, то есть, перестаёт быть чётной. А в ℤ/10ℤ или в ℤ чётность при сложении чётных чисел сохраняется.
Итак, в кольце ℤ/10ℤ обнаружились два подкольца, то есть, две числовые системы, замкнутые относительно сложения и умножения, принятых в кольце. Более того, можно заметить, что если умножить любое число из ℤ/10ℤ на любой элемент из подкольца 2ℤ/10ℤ
, то результат обязательно окажется в этом подкольце. Действительно, любое нечётное число, умноженное на чётное даст чётный результат, и оказавшись таким образом внутри подкольца, из него ему уже не выбраться ни сложением, ни умножением с элементами подкольца. То же самое верно и для подкольца 5ℤ/10ℤ: какое бы число мы не умножили на 5, результат будет либо пятёркой, либо нулём.
Подкольца, обладающие такими поглощающими свойствами, называются идеалами и играют очень важную роль в теории колец. Первым понятие идеальных чисел ввел в середине XIX века немецкий алгебраист Эрнст Куммер. Он обнаружил их и описал их замечательные свойства, борясь с Великой теоремой Ферма. За работы над идеальными числами он получил Большой приз Парижской Академии наук. Позже, ученик Гаусса, Дедекинд, которому мы обязаны появлению теории колец, обобщил идеальные числа до идеалов в произвольных кольцах и с тех пор они стали одним из важнейших понятий в алгебре.
А есть ли идеалы в ℤ/5ℤ? Есть, но они не интересные. Один из них состоит из одного только нуля: действительно, сумма и произведение нулей дает только нули, так же как и произведение нуля и любого элемента кольца. А второй идеал — это всё кольцо целиком. Такие идеалы обязаны быть в любом кольце, и никакой информации о кольцах они не несут.
Можно показать, что количество элементов в нетривиальном подкольце обязательно должно быть делителем количества элементов в кольце. Поскольку 10 = 2×5, то кольцо с десятью элементами способно иметь два подкольца: с пятью и двумя элементами. Они же оказались идеалами, что, в общем, не обязательно. В тоже время, число 5 — простое. Поэтому ℤ/5ℤ тоже будет простым кольцом, оно не может иметь нетривиальных подколец, а значит, и идеалов.
Нетривиальные идеалы выявляют структуру колец, наподобие того, как делители числа дают информацию о числе. У них даже есть своя классификация, но мы туда пока не полезем.
В привычном нам кольце целых чисел ℤ тоже есть идеалы. Это все подмножества чисел, кратных какому-то одному. Так, все чётные числа образуют идеал, равно как и все числа, кратные трём или десяти и т.д. Для них принято обозначение nℤ, показывающее, что это множество можно получить умножением каждого целого числа на n. Например, множество чисел, кратных семи {…, −35, −28, −14, −7, 0, 7, 14, 28, 35, …} является идеалом 7ℤ в ℤ.
Вы можете сами проверить, что такие подмножества образуют подкольца, и более того, эти множества обладают свойствами идеалов и способны «поглощать» любые другие числа посредством умножения на любой свой элемент.
Кстати, в обозначении кольца вычетов ℤ/5ℤ, выражение »5ℤ» − это обозначение идеала из кольца ℤ.
Для тех, кому стало любопытно, есть задание:
Поищите делители нуля на циферблате часов, то есть в кольце ℤ/12ℤ, и выпишите его идеалы.
На примере ℤ/12ℤ, убедитесь в ещё одном «идеальном» свойстве идеалов: пересечение идеалов тоже является идеалом.
Делители единицы
Что бы ещё такого поделить! Ноль мы уже делили и получилось интересно. Пора выяснить на что может делиться единица! Для этого обратим наше внимание на единицы в таблицах умножения. Они выделены синим цветом.
Среди целых чисел есть только два числа, которые в произведении дают единицу, это 1 и −1. В ℤ/10ℤ единицу представить в виде произведения, можно тремя разными способами (с точностью до коммутативности):
Эти числа: 1, 3, 7, 9 в ℤ/10ℤ так и называются делители единицы и они же являются обратимыми элементами кольца. Обратимые элементы способны быть решениями уравнения 
. В нашем случае, уравнение решается только если если 
или 
равны 1, 3, 7 или 9. При этом числа 3 и 7 являются взаимно обратными, а 9 — обратно самому себе:
Тут полезно вспомнить, что у всякого элемента в кольце имеется противоположный элемент, такой, что в сумме они дают 0. Причём 1 противоположно 9, а 3 противоположно 7. Это значит, что мы можем формально написать, что 9 = −1 и 7 = −3. Таким образом, делителями единицы в ℤ/10ℤ будут ±1 и ±3. А единицу можно получить такими тремя способами:
Первый и последний способы имеются и в кольце целых чисел, а вот −3×3 — это уже особенность ℤ/10ℤ. Теперь, кстати, становится понятно, что значит, что число 9 обратно самому себе. Если записать его как −1 то выражение 1/9 = 9 запишется как 1/(−1) = −1. Это равенство верно для всех колец.
Ещё вот на что следует обратить внимание: строки и столбцы для делителей единицы содержат все ненулевые элементы кольца. Помните, «звездочки» для 1,3,7 и 9 честно проходили по всем делениям циферблата без пропусков. Это фундаментальное свойство делителей единицы. Оно означает, что любое число в кольце можно представить как произведение какого-либо элемента и делителя единицы, а значит, линейные уравнения вида 
решаются для любого 
из ℤ/10ℤ.
А что в ℤ/5ℤ? Тут единицы встречаются в каждом ряду, так что в ℤ/5ℤ все без иключения ненулевые элементы являются делителями единицы и обратимыми элементами. Это, в свою очередь, означает, что в ℤ/5ℤ можно решить любое линейное уравнение. И если в ℤ/10ℤ. уравнение 
ожидаемо решается только для чётной правой части, в ℤ/5ℤ нет проблем решить уравнение 
, потому что 
— это обратимый элемент, а значит, формально, 
.
Области целостности, в которых все элементы обратимы (а, значит все линейные уравнения имеют решения), называются полями. Как видим, ℤ/5ℤ хоть и маленькая арифметика, но является полем. Самое маленькое поле это кольцо из двух элементов ℤ/2ℤ.
В 1905 году Джозеф Веддербёрн доказал что, все конечные области целостности являются полями. То есть, если в таблице умножения для конечного кольца нет нетривиальных нулей, то все его элементы обратимы и все линейные уравнения разрешимы.
Арифметика на бесконечном множестве целых чисел, хоть и является областью целостности, но поле не образует. Наименьшее поле с бесконечным числом элементов формируют рациональные числа. В рациональных числах можно решить любое корректное линейное уравнение (если не делить на ноль) и не стоит вопрос о делимости чисел: все делятся на всех.
Среди модулярных арифметик те, которые образованы простыми модулями, такие как ℤ/2ℤ, ℤ/3ℤ, ℤ/5ℤ и т.д. являются полями. В то время, как кольца вычетов по составных модулям: ℤ/6ℤ, ℤ/8ℤ, ℤ/10ℤ и т.д. являются просто коммутативными кольцами.
На что ещё похожи делители едницы?
Давайте ещё раз обратим наше внимание на множество делителей единицы в ℤ/10ℤ — 
Не образуют ли и оно идеал? Не похоже. Это даже не подкольцо, потому что сумма любых двух элементов из него выходит за пределы множества. Но зато произведение любых этих чисел замкнуто внутри множества. Посмотрите на таблицу умножения для них (напомню, что умножаются все эти числа в ℤ/10ℤ, то есть 3×7 = 1, как в большой таблице):
Таблица умножения для делителей единицы.
Эта подсистема, образованная делителями единицы, называется мультипликативной группой обратимых элементов кольца ℤ/10ℤ. И вот что замечательно: с точностью до замены 
её таблица умножения эквивалентна таблице умножения из ℤ/5ℤ!
В поле ℤ/5ℤ все элементы делят единицу, значит мультипликативная группа обратимых элементов совпадает с группой умножения в этом кольце, вернее, в поле. Чтобы лучше понять, как она устроена, построим несложный граф, в котором узлы будут соответствовать элементам группы, а стрелки разного цвета — умножению на неединичные элементы:
Такой граф называется графом Кэйли для группы.
Если вы построете такой же граф для таблицы умножения в ℤ/5ℤ, то убедитесь, что эти две алгебраические системы одинаковы.
Ну, и, как обчно, для тех, кому стало интересно, есть задание:
Выпишите для циферблате часов, то есть для кольца ℤ/12ℤ, делители единицы и таблицу умножения для мультипликативной группы обратимых элементов.
Постройте граф Кэйли для мультипликативной группы обратимых элементов ℤ/12ℤ.
Приступаем к делёжке
Как известно, если попытаться разделить пять яблок на двоих енотов, появится остаток из одного яблока из-за которого может случиться драка. Пятый класс, вторая четверть. А как обстоят дела с делимостью в других кольцах?
Разговор о делимости надо сразу начать с того, что появившееся понятие поля проводит черту между алгебраическими системами, в которых вопрос делимости актуален, и теми, где он теряет смысл.
Мы привыкли к тому, что натуральные и целые числа бывают чётными и нечётными, круглыми (кратными 10) и нет, составными и простыми. В этих числах мы решаем задачи на поиск наибольшего общего делителя и наименьшего общего кратного, используем алгоритм Евклида и так к этому привыкли, что уже подчас не замечаем, что в рациональных числах всего этого нет. При том, что в целых числителях и натуральных знаменателях дробей вопросы делимости актуальны, сами дроби делятся друг на друга в любых сочетаниях и без всяких проблем. И связано это с тем, что любое ненулевое рациональное число обратимо и входит в мультипликативную группу обратимых элементов, а значит, с точки зрения алгебры, рациональные числа образуют уже не кольцо, а поле.
На школьном пути постижения алгебраических структур мы приучаемся к мысли о том, что расширение наших возможностей связано с пополнением привычной числовой системы чем-то новым. От натуральных чисел мы переходим к целым, добавляя отрицательные (противоположные) числа и это даёт нам возможность вычитать любые числа друг из друга. Далее от целых переходим к рациональным, добавляя пары чисел, называемые дробями, которые позволяют формально делить любые числа на любые ненулевые. От рациональных переходим к вещественным, пополняя их корнями неразрешимых рациональных уравнений и трансцендентными величинами, а на самом деле, просто разрешая существовать пределам всех мыслимых сходящихся последовательностей. И, наконец, добавляя мнимую единицу, то есть корень ещё одного неразрешимого вещественного уравнения, переходим к комплексным числам, алгебраически замыкая числовую систему, и позволяя возводить любые числа в любые степени.
Однако, в самом начале этого пути, можно было получить полноценное поле не пополняя систему натуральных чисел, а напротив, сокращая её, и переходя в конечную арифметику вычетов. Так, полем может быть любое конечное кольцо без делителей нуля, а значит, все кольца вычетов ℤ/pℤ с простым p, позволяют не только складывать, вычитать и перемножать любые входящие в них числа, но и находить их отношения (решать любые корректные линейные уравнения), а так же возводить любые числа в любые доступные степени. И хотя сами эти системы не являются алгебраически замкнутыми (в них нельзя выразить решение произвольного алгебраического уравнения), в начале XIX века французский математик Эварист Галуа показал, каким образом их можно пополнять, оставляя полями. А почти век спустя, немецкий математик Курт Гензель показал способ перейти от них к комплексным числам минуя вещественные, через p-адические числа.
Так что наши игрушечные поля вовсе не игрушки, а способны стать мощным инструментом в теории чисел и алгебре. Но, повторю, в полях любые вопросы делимости «уже всё». Тривиальны. Таким образом, мы заключаем, что в ℤ/5ℤ нет не только простых чисел, но даже разделение чисел на чётные и нечётные не имеет смысла. Выходит, теорию делимости на пяти пальцах толком не объяснить. А на десяти?
В кольце ℤ/10ℤ есть шанс. Давайте начнём наши соображения со знаменитого алгоритма Евклида, который мы используем в школе для того, чтобы выявлять общие делители и взаимно простые числа.
В целых и натуральных числах, желая выяснить остаток от деления одного числа на другое, мы можем вычитать из большего числа меньшее, до тех пор, пока не получим число, не превышающее делитель.
Давайте выясним с помощью вычитания, как делится, например, 7 на 2 в целых числах и в кольце ℤ/10ℤ:
Вычисление остатка от деления 7 на 2.
Можем сказать, что у нас всё получилось 7 = 3×2 + 1 в обеих арифметиках. Вроде бы, всё в порядке. И вообще, если начиная с единицы построить в ℤ/10ℤ звёздочку с шагом 2, то мы получим все числа, дающие в остатке от деления на 2 единицу, то есть, нечётные числа: 
, а если начнём с нуля, — то все чётные: 
. Полученные нами подмножества не пересекаются, а их объединение равно всему множеству чисел. В таких случаях говорят, что всё множество удалось разбить на смежные классы.
Чётные и нечётные числа в ℤ/10ℤ.
