Арифметика гауссовых чисел

8

Арифметика гауссовых чисел

А. В. ГОНЧАРОВ

Об одной из красивейших арифметических теории, построенной величим немецким математиком К. Ф. Гауссом, рассказано в этой статье. Гауссовы числа (точки с целыми координатами на плоскости) можно определенным образом складывать и умножать. Возникающая при этом теория делимости, которая наполняет общую арифметiku числа, но имеет и свой характерные особенности, вохциает внутренней стройностью и красотой. Однако теория гауссовых чисел не просто изящная математическая игрушка — это и полезный аппарат, позволяющий находить красные доказательства различных фактов из теории чисел (пифародовый тройки, число представления натурального числа в виде суммы двух квадратов), и даже кристаллографини (см. статью А. Л. Петелина и А. И. Федосеева в этом номере «Кванта»).

Натуральные числа 0, 1, 2, 3, … являются основой всей математики. Относительно сложения они устроены весом просто, а именно: 1, 2=1+1, 3=1+1+1, …, так что единственным исходным исходным кирпичом является 1.

Вводя в игру вычитание, мы попадаем в область целых чисел — 3, — 2, —1, 0, 1, 2, 3 … Относительно же умножения тот же ряд целых чисел устроен уже гораддо сложнее. А именно, простейших кирпичей, из которых строятся умножением все ненулевые целые числа, бесконечного много — это все простые числа: 2, 3, 5, 7, 11, 13, …. Natуральные числа, большие 1, получаются из них умножением: 2, 3, 2×2, 5, 2×3, 7, 2×2×2, 3×3, …. Для того же, чтобы умножением получить все целые рациональные числа, надо еще привлечь обе единицы 1 и —1.

Следующая теорема обязывает, в каком смысле простые числа являются строительным материалом для мультитипикативного (то есть относаяся к умножению) построения натуральных чисел.

Основная теорема арифметики целых чисел. Каждое ненулевое число число a = εp₁ᵢ p₂ᵢ … pₙᵢ (1)

zdе n≥0, pᵢ — различные простые числа, eᵢ — положительные целые числа, a ε — одна из единиц. Это представление определяено однозначно с точностью до порядка сомножителей.

Если простые числа p₁, p₂, …, pₙ располагаать в порядке возрастания (что естественно), то равенство (1) полностью определяется числом a: и число ε (равное ±1), и простые множители p₁<p₂<…<pₙ, и их показатели e₁, e₂, …, eₙ однозначно определяются выбором a.

Эта теорема*) была известна еще в древности.

Долгое время математики получили доказательства арифметических теorem о натуральных числах, работа лишь с целыми числами. Однако в начале XIX века Гаусс обнаружил, что некоторые вопросы теории чисел только тогда выступают во всей своей ясности и естественной красоте, когда область арифметики распространяется также и на «числа», которые мы сейчас называем целыми гауссовыми. Что это за числа?

Гауссовы числа G — это простой пары целых чисел

G = {(a, b)|a, b∈Z},

которые складывают и умножают по следующим правилам

(a; b)+(c; d)=(a+c; b+d), (2)
(a; b)·(c; d)=(ac-bd; ad+bc). (3)

Для нагладности можно представить себе множество G как «целочисленную решетку на плоскости», то есть как множество всех точек на координатной плоскости, у которых и абсцисса, и ordinата — целые (рис. 1), или — что то же самое — как множество всех векторов с началом O и концами в этих точках. Тогда сложение гауссовых чисел (2) представляется как общное сложение векторов по правлу параллелограмма, а вот умножение выглядит несколько сложной — читателью, не значаеме на c.11).

10

Рис. 4. Гауссовы числа, делящее на 2+3i.

$$5 - 3i = 1 + 1 + 1 + 1 + (-i) + (-i).$$

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

Простые гауссовы числа и делимость. Если для двух гауссовых чисел $a, b$ найдется трете число $c \in G$ такое, что $a = b \cdot c$, говорят, что $a$ делится на $b$ (запись $a \div b$) или $b$ делит $a$ (запись $b \mid a$). Например, $2 \div 1 + i$ и $2 = (1 + i) \cdot (1 - i)$. На рисунке 4 показаны гауссовы числа, которые делятся на $2 + 3i$.

Упражнение 4. а) Проверьте, что $1 + i \div 1 - i$. 6) Доказите, что для гауссовых чисел выполненые обычные свойства делимости:

$$a \div b \Rightarrow ac \div bc,$$
$$ac \div bc, c \neq 0 \Rightarrow a \div b,$$
$$a \div b, b \div c \Rightarrow a \div c.$$

в) Отметьте на координатной плоскости все гауссовы числа, которые делятся на $3 - 2i$.

В области целых чисел из соответствия $a \div b$ и $b \div a$ следует, что $a = \pm b$. В области гауссовых чисел, это уже не так, например $a \div \pm a, a \div \pm ia$. Однако верно следующее:

$$a \div b, b \div a \Rightarrow a = \pm ib$$

Доказательство. Пусть $a \mid b = c$, тогда $c$ и $c^{-1} = b \mid a$ гауссовы числа. Очевидно

$$1 = N(1) = N(c \cdot c^{-1}) = N(c)N(c^{-1})$$,

откуда $N(c) = N(c^{-1}) = 1$ (ибо $N(c)$ и $N(c^{-1})$ обычные целые положительные числа). Но существует лишь 4 гауссовых числа с нормой $1 -$ числа $1, -1, i, -i$, которые мы в дальнейшем будем называть единицами.

Назовем два гауссовых числа союзными, если их частное — одно из единиц (рис. 5). Гауссово число называется простым, если она не имеет других неулевых делителей, кроме союзных с ним чисел и единиц. Например, числа 3 и $2 + 3i$ — простые, а число 5 — нет: $5 = (2 + i)(2 - i)$. (Для доказательства простоты чисел 3 и $2 + 3i$ нужно воспользоваться соответствием $N(a)N(b) = N(ab)$ и перебрать все гауссовы числа, чья норма является делителем нормы данных чисел.)

Упражнение 5. Разберите, какие простые числа от 2 до 30 — простые гауссовы.

Основная теорема арифметики гауссовых чисел. Какое ненулевое гауссовую числа g представляется в виде

$$g = \varepsilon \cdot g_1^{e_1} g_2^{e_2} \dots g_n^{e_n}$$

еде $\varepsilon$ — одна из единиц, $g_1, g_2, \dots g_n$ — различные (то есть не союзные) простые гауссовые числа, а $e_1, e_2, \dots e_n$ — положительные показатели. Такое разложение единственно в том смысле, что всякое другое разложение g на простые компоненты имеет вид $a = \varepsilon' \cdot h_1^{e_1} h_2^{e_2} \dots h_n^{e_n}$, где набор простых компонентов и заменой некоторых из них на союзные, а набор показателей состоит из тех же чисел, отличая лишь порядком.

Доказательство. Чтобы доказать существование разложения (6), проведем индукцию по норме $N(g)$ числа g. База индукции: единственное числа c норми

13

Найдем теперь число разложений $n=a^2+b^2$ для произвольного натурального $n$. Нам будет удобно считать различными разложения, отличующаяся изменением знаков у $a$ и $b$ или порядком слагаемых. Тогда это число будет равным числу точек с целыми координатами на окружности радиуса $\sqrt{n}$ с центром 0.

Теорема 3. Число целых точек на окружности радиуса $\sqrt{n}$, $n \in \mathbb{N}$ или (что то же самое) число разложений целого числа $n$ на сумму двух квадратов равно учетверенному изображению числа делитель $n$ вида $4k+1$ над числом делитель вида $4k+3$.

Например, легко видеть, что окружности радиусов $\sqrt{5}, \sqrt{13}, \sqrt{17}, 5$ проходят через 4, 4, 4, 12 точек соответствующего (проверьте, что во всех трех случаях это число равно соответствующему учетверенному изображению числа делитель $n$ вида $4k+1$ над числом делитель вида $4k+3$.

Например, легко видеть, что окружности радиусов $\sqrt{5}, \sqrt{13}, \sqrt{17}, 5$ проходят через 4, 4, 4, 12 точек соответствующего (проверьте, что во всех трех случаях это число равно соответствующему учетверенному изображению числа делитель $n$ вида $4k+1$ над числом делитель вида $4k+3$.

Доказательство. Представим $n$ в виде $n=2^a q_1^{a_1} \cdots q_k^{a_k} p_1^{e_1} p_1^{e_1} \cdots p_m^{e_m} p_m^{e_m}$,

где $q_j=q_j>0$ и $p_j, p_j$ — простые гуссовы числа ($p_j$ и $p_j$ — несоответные). Пусть $n=a^2+b^2=(a+bi)(a-bi)$. Из основной теоремы легко следует, что $a+bi$ союзно с числом $(1+i)^a \cdot q_1^{a_1/2} \cdots q_k^{a_k/2} \cdot p_1^{f_1} \cdot p_1^{e_1}-f_1 \cdot \cdots \cdot p_m^{f_m} p_m^{e_m}-f_m$,

где $0 \leq f_j \leq e_j$.

Отсюда видно, что число представлен $n$ в виде суммы двух квадратов равно

$$\begin{cases} 0 - \text{если среди чисел } a_i \text{ есть нечетные числа}, \\ 4(e_1+1) \cdot \cdots \cdot (e_m+1) - \text{если все } (13) \\ a_i \text{ четные} \end{cases}$$

(4 появляется в результате того, что выражение (12) отличается от $a+bi$ на единицу, а единицу всего 4).

С другой стороны, любой нечетный делитель $x$ числа $n$ имеет разложение на простые гуссовы числа вида

$$x=q_1^{q_1} \cdot \cdots \cdot q_k^{q_k} p_1^{p_1} p_1^{p_1} \cdots p_m^{p_m} p_m^{p_m},$$

где $b_1 \leq a_1, \cdots, b_k \leq a_k; f_1 \leq e_1, \cdots, f_m \leq e_m$.

Но $q_i$ — натуральные числа, являющиеся простыми гуссовыми, поэтому $q_i$ имеет остаток 3 при делении на 4 и

$$(b_1+\cdots+b_k):2 \Leftrightarrow x=4k+1 \quad (k \in \mathbb{Z}).$$

Отсюда уже легко вывести (выведите!), что изображение числа делитель вида $4k+1$ над числом делитель вида $4k+3$ равен

$$\begin{cases} 0, \text{ если среди чисел } a_i \text{ есть нечетное}, \\ (e_1+1) \cdot \cdots \cdot (e_m+1), \text{ если все } a_i - \quad (14) \\ \text{ четные числа.} \end{cases}$$

Сравнивая (13) и (14), получаем доказательство теоремы.

Заключение. Мы не обьясили,откуда возникла изложенная выше теория. А дело было так: в 1796 году девятнадцатилетний Гаусс доказал квадратический закон взаимности, являющийся одной из прекраснейших жемчужин теории чисел. Об истории его возникновения и доказательстве рассказано в статье С. Г. Гиндикина «Золотая теорема» (в «Кванте», 1973, № 1).

Квадратический закон взаимности позволяет исчерпивающим образом исследовать уравнение вида $x^2-a \equiv 0(\text{mod } b)$, то есть найти все $x \in N$ такие, что число $x^2-a$ делится на $b$.

Естественно, что аналогичную теорию Гаусс хотел иметь и для уравнения более высокой степени, например $x^4-a \equiv 0(\text{mod } b)$, и поэтому начало поиск «биквадратического закона взаимности». И тут-то выяснили, что хотя это уравнение первого анализа в области натуральных чисел, законченый результат практической необходимости даже формулировать (!) без целых гуссовых чисел. Воспледствии (1832 г.), Гаусс писал:

«После того, как мы начали исследовать эти вопросы в 1805 г., (…) мы скоро пришли к убежданию, что (…) для общей теории необходимо в некоторых смысле бесконечно расширить область вышей арифметики. Как только мы вступаем в эту область, точас же обнаруживается подход к индутивному нахождению веса простых и исчерпивающих всего теории теории; однако доказательства их скрыты столглубоко, что их удалось излечь на свет только после бесконечно попыток».

Области, о которой пишет Гаусс, и есть теория тех чисел, которые сейчас носят его имя.