Гауссовы целые числа

Решётка гауссовых чисел на комплексной плоскости

Га́уссовы це́лые чи́сла (гауссовы числа, целые комплексные числа) — это комплексные числа, у которых как вещественная, так и мнимая часть — целые числа^[1].

Примеры: ${\displaystyle 1+2i;\quad -4+11i;\quad 4i;\quad 5;\quad 1-i}$.

Впервые введены Гауссом в монографии «Теория биквадратичных вычетов» (1828—1832)^{[2] [3]}. Множество гауссовых целых чисел принято обозначать ${\displaystyle \mathbb {Z} [i],}$ отражая тем самым тот факт, что оно получается из множества целых чисел ${\displaystyle \mathbb {Z} }$ добавлением в него мнимой единицы ${\displaystyle i}$ и комбинаций её с целыми числами. Свойства гауссовых чисел похожи на свойства обычных целых чисел, однако имеются и существенные отличия.

Общие свойства

Определение и классификация

Формальное определение:

${\displaystyle \mathbb {Z} [i]=\{a+bi\mid a,b\in \mathbb {Z} \}}$.

Множество ${\displaystyle \mathbb {Z} [i]}$ содержит множество обычных целых чисел ${\displaystyle \mathbb {Z} }$ и представляет собой его расширение^[4]. Сумма, разность и произведение гауссовых чисел являются гауссовыми числами; для них, как и для целых чисел, сохраняются свойства ассоциативности, коммутативности и дистрибутивности — такая алгебраическая структура называется в общей алгебре коммутативным кольцом^[5]. Ввести в этом комплексном кольце упорядоченность, согласованную с порядком вещественных чисел, невозможно.

Сопряжённое к гауссовому числу ${\displaystyle a+bi}$ есть также гауссово число ${\displaystyle a-bi}$.

Каждое гауссово число ${\displaystyle z=a+bi}$ удовлетворяет квадратному уравнению:

${\displaystyle (z-a)^{2}+b^{2}=0}$

Поэтому гауссово число есть целое алгебраическое число.

Норма

Норма для гауссова числа ${\displaystyle a+bi}$ определяется как квадрат его модуля^[6]:

${\displaystyle N\left(a+bi\right)=a^{2}+b^{2}=(a+bi){\overline {(a+bi)}}}$.

Свойства нормы^[7]:

• Норма равна нулю только для нуля. В остальных случаях норма — положительное целое число.
• Нормы сопряжённых чисел совпадают.
• Норма обычного целого числа равна его квадрату.
• Если норма нечётна, то она имеет вид ${\displaystyle 4n+1}$, то есть при делении её на 4 получается остаток 1. Никакое гауссово число не может иметь норму вида ${\displaystyle 4n+3}$.

Норма, как и модуль, обладает важным свойством мультипликативности^[7]:

${\displaystyle N(u\cdot v)=N(u)\cdot N(v)}$

Отсюда следует^[8], что обратимыми элементами кольца (делителями единицы) являются те элементы, у которых норма равна 1, то есть ${\displaystyle \{1;-1;i;-i\}}$.

Два гауссовых числа называются ассоциированными, если одно получается из другого умножением на делитель единицы. Легко видеть, что ассоциированность — отношение эквивалентности^[8]. Пример: гауссовы числа ${\displaystyle 1+i}$ и ${\displaystyle 1-i}$ ассоциированы, поскольку:

${\displaystyle 1+i=i(1-i)}$.

У каждого ненулевого гауссова числа есть три ассоциированных с ним. Нормы всех четырёх ассоциированных между собой чисел совпадают.

Теория делимости

Деление нацело

Деление нацело гауссовых чисел определяется обычным образом^[7]:

Говорят, что гауссово число ${\displaystyle u}$ делится (нацело) на гауссово число ${\displaystyle v}$, если существует третье гауссово число ${\displaystyle q}$ такое, что ${\displaystyle u=vq}$. Обозначение: ${\displaystyle v\mid u}$.

Произношение: один из трёх равносильных вариантов.

• ${\displaystyle u}$ делится на ${\displaystyle v}$;
• ${\displaystyle v}$ делит ${\displaystyle u}$;
• ${\displaystyle v}$ — делитель ${\displaystyle u}$.

Используются традиционные термины: делимое или кратное (${\displaystyle u}$), делитель (${\displaystyle v}$) и частное от деления (${\displaystyle q}$). Количество делителей гауссова числа всегда конечно, количество кратных бесконечно.

Пример: число 2 делится нацело на ${\displaystyle 1+i}$, потому что ${\displaystyle 2=(1+i)(1-i)}$.

Все гауссовы числа делятся на делители единицы, поэтому любое гауссово число, отличное от делителей единицы, имеет как минимум 8 делителей: 4 делителя единицы и 4 их произведения на само это число. Эти делители называются тривиальными^[9].

Деление нацело в ${\displaystyle \mathbb {Z} [i]}$ по своим свойствам похоже на аналогичное деление целых чисел. Некоторые специфические для гауссовых чисел особенности^[8][7]:

• Если гауссово число ${\displaystyle z}$ делится нацело на обычное целое число, то на это целое число делятся как вещественная, так и мнимая часть ${\displaystyle z}$.
• Если ${\displaystyle u\mid v}$ и ${\displaystyle v\mid u}$, то эти числа ассоциированы.
• Если ${\displaystyle u\mid v}$, то любое из 3 чисел, ассоциированных с ${\displaystyle v}$, делится на любое из 3 чисел, ассоциированных с ${\displaystyle u}$.
• Если ${\displaystyle u}$ делится на ${\displaystyle v\;(u=vq)}$, то сопряжённое к делимому число ${\displaystyle {\overline {u}}}$ делится на сопряжённое к делителю ${\displaystyle {\overline {v}}\;({\overline {u}}={\overline {v}}{\overline {q}})}$.
• Все делители гауссова числа ${\displaystyle z}$ являются также делителями его нормы ${\displaystyle N(z)=z\cdot {\overline {z}}}$.
• Норма гауссова числа чётна тогда и только тогда, когда это число делится на ${\displaystyle 1+i}$.
• Если ${\displaystyle v\mid u}$, то и норма делимого, в силу мультипликативности, делится нацело на норму делителя. При этом:

${\displaystyle N\left({\frac {u}{v}}\right)={\frac {N(u)}{N(v)}}}$

Решётка кратных для ${\displaystyle 1+2i}$

Геометрическое представление делимости

У каждого гауссова числа ${\displaystyle z}$ есть 4 кратных с той же нормой (и, соответственно, тем же модулем) — это само ${\displaystyle z}$ и ассоциированные с ним 3 числа, которые получаются последовательным умножением ${\displaystyle z}$ на ${\displaystyle i}$:

${\displaystyle z;\ iz;\ -z;\ -iz}$

Но умножение на ${\displaystyle i}$ означает на комплексной плоскости поворот радиус-вектора числа на 90° против часовой стрелки, причём модуль результата будет тем же. Таким образом, все 4 числа образуют равносторонний крест (выделен красным на рисунке), центр и вершины которого кратны ${\displaystyle z}$. Последовательно сдвигая этот крест во все стороны на одну из 4 величин, ассоциированных с ${\displaystyle z}$, мы получаем на всей плоскости квадратную решётку, все узлы которой (вершины квадратов) кратны ${\displaystyle z}$. Обратно, любое кратное ${\displaystyle z}$ совпадает с одним из узлов решётки. Ширина каждого квадрата решётки равна ${\displaystyle |z|}$. Далее для краткости эта решётка будет называться «решёткой кратных» (или, если требуется уточнение, «${\displaystyle z}$-решёткой кратных»).

Пример: на рисунке одним из узлов решётки является число ${\displaystyle 4-2i}$, кратное ${\displaystyle 1+2i}$:

${\displaystyle 4-2i=-2i(1+2i)}$.

Простые гауссовы числа

Распределение гауссовых простых чисел на комплексной плоскости

Распределение гауссовых простых вблизи нуля

Простое гауссово число — ненулевое число, не имеющее других делителей, кроме тривиальных. Число, не являющееся простым, называется составным. При этом делители единицы, подобно натуральной единице, не считаются ни простыми, ни составными числами^[10].

Некоторые свойства простых гауссовых чисел:

• Если ${\displaystyle a+bi}$ — простое гауссово число, то противоположное ${\displaystyle -a-bi}$ и сопряжённое к нему ${\displaystyle a-bi}$ гауссовы числа тоже являются простыми.
• Если простое гауссово число является делителем произведения гауссовых чисел, то оно является делителем по крайней мере одного из сомножителей.
• Норма любого простого гауссова числа, кроме ассоциированных с ${\displaystyle 1+i}$, всегда нечётна и поэтому имеет вид ${\displaystyle 4n+1}$.

Натуральное простое число может не быть гауссовым простым числом. Например, числа 2 и 5 в ${\displaystyle \mathbb {Z} [i]}$ уже не простые:

${\displaystyle 2=(1+i)(1-i);\quad 5=(2+i)(2-i)}$

Разложение гауссовых чисел с нормой от 2 до 100 на простые гауссовы множители см. в таблице Факторизация гауссовых чисел.

Взаимно простые числа

Если гауссово число ${\displaystyle w}$ является делителем для двух гауссовых чисел ${\displaystyle u}$ и ${\displaystyle v}$, оно называется их общим делителем. Множество общих делителей двух чисел всегда содержит 4 делителя единицы; если других общих делителей нет, эти числа называются взаимно простыми^[11].

Отметим, что если нормы гауссовых чисел ${\displaystyle u,v}$ взаимно просты как целые числа, то и сами числа ${\displaystyle u,v}$ взаимно просты как гауссовы числа. Обратное неверно: нормы взаимно простых гауссовых чисел могут иметь общие делители — например, ${\displaystyle 5+2i}$ и ${\displaystyle 5-2i}$ взаимно просты, но их нормы совпадают и поэтому не взаимно просты.

Укажем два свойства, аналогичные свойствам целых чисел.

• Если каждое из двух гауссовых чисел ${\displaystyle u,v}$ взаимно просто с гауссовым числом ${\displaystyle w,}$ то и их произведение ${\displaystyle uv}$ тоже взаимно просто^[11] с ${\displaystyle w}$.
• Если ${\displaystyle z|uv}$ и при этом ${\displaystyle z}$ взаимно просто с ${\displaystyle u}$, то^[12] ${\displaystyle z|v}$.

Критерий Гаусса

Гаусс указал определяющие признаки простого числа в ${\displaystyle \mathbb {Z} [i]}$^[13].

Гауссово число ${\displaystyle a+bi}$ является простым тогда и только тогда, когда: либо одно из чисел ${\displaystyle a,b}$ нулевое, а другое — целое простое число вида ${\displaystyle \pm (4n+3)}$; либо ${\displaystyle a,b}$ оба не нули и норма ${\displaystyle a^{2}+b^{2}}$ — простое натуральное число.

Примеры простых гауссовых чисел:

• к первой части критерия: ${\displaystyle \pm 3;\ \pm 7;\ \pm 3i}$;
• ко второй части критерия: ${\displaystyle 1\pm i;\ 1\pm 2i;\ 1\pm 4i;\ 4+5i;\ 2-3i;\ 15+22i}$.

Некоторые источники для большей ясности разделяют вторую часть критерия на две^[14]:

1. Числа, ассоциированные с ${\displaystyle 1+i}$. Их норма равна 2.
2. Числа, норма которых есть простое натуральное число вида ${\displaystyle 4n+1}$.

Сам Гаусс такого разделения не делал^[15].

Следствия:

• Никакое простое натуральное число вида ${\displaystyle 4n+1}$ не может быть простым гауссовым числом. Простые натуральные числа вида ${\displaystyle 4n+3}$ являются и простыми гауссовыми числами.
• Норма простого гауссова числа является либо простым натуральным числом, либо квадратом простого натурального числа^[16].
• Простое натуральное число вида ${\displaystyle 4n+1}$ можно представить как произведение сопряжённых простых гауссовых чисел ${\displaystyle (a+bi)(a-bi)}$ или, что то же самое, как сумму квадратов ${\displaystyle a^{2}+b^{2}}$. Этот факт известен как Теорема Ферма — Эйлера. Именно при исследовании данной темы, а также теории биквадратичных вычетов, Гаусс с успехом применил целые комплексные числа. Обратно, если простое натуральное число представимо в виде суммы натуральных квадратов, то в ${\displaystyle \mathbb {Z} [i]}$ оно составное и разлагается на два сопряжённых гауссовых простых^[17].
• Каждое простое гауссово число является делителем одного и только одного простого натурального числа^[17]. Это значит, что разлагая натуральные простые на гауссовы множители, получаются все гауссовы простые.

Разложение на простые множители

В ${\displaystyle \mathbb {Z} [i]}$ имеет место аналог основной теоремы арифметики: каждое гауссово число, не являющееся нулём или делителем единицы, разлагается на простые множители, причём это разложение однозначно с точностью до порядка и ассоциированности множителей^[1][18].

Пример: ${\displaystyle 5=(1+2i)(1-2i)=(2-i)(2+i)}$. Множители этих двух, по виду разных, разложений попарно ассоциированы: ${\displaystyle 1+2i=i(2-i);\ 1-2i=(-i)(2+i),}$ так что однозначность не нарушается.

Чтобы практически разложить гауссово число ${\displaystyle z}$ на простые множители, можно использовать приведённое выше свойство: все делители гауссова числа являются также делителями его нормы. При этом норма содержит также «лишние» простые множители, соответствующие сопряжённому к ${\displaystyle z}$ числу.

Таким образом, начать следует с разложения нормы числа ${\displaystyle z}$ на простые натуральные множители^[19].

1. Множитель 2, если он присутствует в разложении нормы, разлагается как ${\displaystyle (1+i)(1-i)}$. Следует включить в результирующее разложение те из этих множителей (в соответствующей степени), на которые ${\displaystyle z}$ делится нацело.
2. Кроме 2, остальные множители нормы — нечётные. Множитель вида ${\displaystyle 4n+3}$ является простым гауссовым числом, поэтому он делит не только норму ${\displaystyle N(z)=~z{\overline {z}}}$, но и само ${\displaystyle z}$. Но тогда этот множитель делит и сопряжённое число ${\displaystyle {\overline {z}}}$. Отсюда вытекает, что множитель вида ${\displaystyle 4n+3}$ входит в разложение нормы всегда в чётной степени, а в разложение самого ${\displaystyle z}$ — в степени, вдвое меньшей.
3. Множитель вида ${\displaystyle 4n+1}$ можно разложить на произведение сопряжённых простых гауссовых чисел (или, что то же самое, на сумму квадратов натуральных чисел). И здесь следует делением выяснить, какой из сомножителей относится к исходному числу, а какой — к сопряжённому.

Например, для разложения на простые множители ${\displaystyle 9+12i}$ (норма — 225) выделяются простые натуральные множители: ${\displaystyle 225=3^{2}\cdot 5^{2}}$. По предыдущему, ${\displaystyle 5=(2-i)(2+i)}$. При этом ${\displaystyle 9+12i}$ делится только на ${\displaystyle 2+i}$ и не делится на ${\displaystyle 2-i}$. Частное от деления ${\displaystyle 9+12i}$ на ${\displaystyle 3(2+i)}$ равно ${\displaystyle 2+i,}$ поэтому окончательный результат:

${\displaystyle 9+12i=3\cdot (2+i)^{2}}$.

Теория сравнений

Сравнения по гауссовому модулю

Понятие сравнения по модулю определяется в ${\displaystyle \mathbb {Z} [i]}$ аналогично тому, как это делается для целых чисел^[20]:

Пусть ${\displaystyle w}$ — некоторое гауссово число. Два гауссовых числа ${\displaystyle u,v}$ называются сравнимыми по модулю ${\displaystyle w}$, если разность ${\displaystyle u-v}$ делится (нацело) на ${\displaystyle w}$. Запись: ${\displaystyle u\equiv v{\pmod {w}}}$.

Свойства сравнений в ${\displaystyle \mathbb {Z} [i]}$ в основном такие же, как у целых чисел. Отношение сравнимости есть отношение эквивалентности, поэтому ${\displaystyle \mathbb {Z} [i]}$ разбивается на непересекающиеся классы вычетов — каждый такой класс содержит все сравнимые друг с другом (по заданному модулю) гауссовы числа. Для классов, как в случае целых чисел, можно определить сложение и умножение, так что получается кольцо вычетов по гауссову модулю.

Пример. Возьмём в качестве модуля сравнения ${\displaystyle 1+i}$. Тогда ${\displaystyle \mathbb {Z} [i]}$ разбивается на два класса вычетов: числа ${\displaystyle a+bi}$, у которых ${\displaystyle a,b}$ одинаковой чётности, попадут в один класс (содержащий кратные для модуля), а числа с разной чётностью ${\displaystyle a,b}$ — в другой.

У гауссова сравнения имеются некоторые особенности. Например, если для целых чисел по модулю 3 существуют 3 класса вычетов с представителями ${\displaystyle 0;\ 1;\ 2,}$ то для гауссовых чисел по тому же модулю количество классов значительно больше. Их представители:

${\displaystyle 0;\ 1;\ 2;\ i;\ 1+i;\ 2+i;\ 2i;\ 1+2i;\ 2+2i}$

Как обнаружил Гаусс, кольцо вычетов по модулю ${\displaystyle a+bi}$ содержит ${\displaystyle N(a+bi)=a^{2}+b^{2}}$ элементов^[20]. Этот факт вынуждает модифицировать некоторые классические теоремы. Например, малая теорема Ферма для целых чисел утверждает, что ${\displaystyle (a^{p}-a)}$ делится на ${\displaystyle p}$ для любого простого ${\displaystyle p}$ и натурального ${\displaystyle a}$. Для гауссовых чисел это неверно, даже если ограничиться натуральными значениями ${\displaystyle p}$; например, для целых чисел ${\displaystyle a^{3}-a}$ всегда делится на 3, а для гауссовых ${\displaystyle i^{3}-i=-2i}$, и это значение на 3 не делится. Модифицированный аналог малой теоремы Ферма формулируется следующим образом^[20]:

Для простого гауссова числа ${\displaystyle w=a+bi}$ и любого гауссова числа ${\displaystyle u}$
${\displaystyle (u^{N(w)}-u)=(u^{a^{2}+b^{2}}-u)}$ делится на ${\displaystyle w}$.

На том же примере с ${\displaystyle w=3;u=i}$ результат: ${\displaystyle (i^{9}-i)=0}$ — делится на 3.

Назовём класс вычетов по модулю ${\displaystyle w,}$ содержащий число ${\displaystyle u,}$ обратимым, если сравнение ${\displaystyle ux\equiv 1{\pmod {w}}}$ имеет решение относительно ${\displaystyle x}$. Класс обратим тогда и только тогда, когда гауссовы числа ${\displaystyle u}$ и ${\displaystyle w}$ взаимно просты^[20]. В частности, если модуль сравнений ${\displaystyle w}$ — гауссово простое число, то каждый ненулевой класс вычетов имеет обратный элемент, а это значит, что классы вычетов по простому модулю в ${\displaystyle \mathbb {Z} [i]}$, как и в ${\displaystyle \mathbb {Z} ,}$ образуют поле.

Функция Эйлера для гауссовых чисел

Введём аналог функции Эйлера для гауссовых чисел. Определение для целых чисел не годится хотя бы потому, что содержащееся в нём выражение «от ${\displaystyle 1}$ до ${\displaystyle n}$» не имеет смысла для комплексных чисел. Новое определение^[20]:

Функция Эйлера ${\displaystyle \varphi (z)}$ для гауссова числа ${\displaystyle z}$ определяется как число обратимых классов вычетов по модулю ${\displaystyle z}$.

Определённая таким образом функция, как и её прототип для целых чисел, мультипликативна, поэтому достаточно знать её значения для простых чисел и их натуральных степеней. Если ${\displaystyle z}$ — простое гауссово число, то^[20]:

${\displaystyle \varphi (z)=N(z)-1;\quad \varphi (z^{k})=N(z)^{k-1}(N(z)-1)}$

Пример: ${\displaystyle \varphi (3+4i)=\varphi ((2+i)^{2})=N(2+i)(N(2+i)-1)=5\cdot 4=20}$.

Теперь можно обобщить приведённую в предыдущем разделе малую теорему Ферма на случай произвольного (не обязательно простого) модуля сравнения, то есть привести аналог теоремы Эйлера^[20]:

Если гауссово число ${\displaystyle z}$ взаимно просто с модулем ${\displaystyle w,}$, то: ${\displaystyle z^{\varphi (w)}\equiv 1{\pmod {w}}}$

Сравнение по модулю ${\displaystyle 1+2i}$

Геометрическое представление сравнения по модулю

Рассмотрим для примера сравнения по модулю ${\displaystyle w=1+2i}$. Как сказано в разделе о геометрическом представлении делимости, можно разбить комплексную плоскость на квадраты так, что узлы этой решётки (вершины квадратов) представляют всевозможные комплексные кратные ${\displaystyle 1+2i}$. Тогда, по определению, числа сравнимы по модулю ${\displaystyle w}$, если их разность совпадает с одним из узлов решётки кратных.

Каждый квадрат решётки получается из любого другого квадрата сдвигом (переносом) на величину, кратную ${\displaystyle w,}$ поэтому разность любой точки квадрата и результата её сдвига тоже кратна ${\displaystyle w}$. Отсюда следует окончательный вывод^[20]:

Гауссовы числа сравнимы по модулю ${\displaystyle w}$ тогда и только тогда, когда они занимают одно и то же относительное положение в своих квадратах решётки кратных.

Например, сравнимы все центры квадратов, или все середины их соответствующих сторон и т. п.

Деление с остатком

Определение

В кольце ${\displaystyle \mathbb {Z} [i]}$ можно определить деление с остатком (на любое ненулевое гауссово число), потребовав, чтобы норма остатка была меньше нормы делителя^[21]:

Любое гауссово число ${\displaystyle u}$ можно разделить с остатком на любое ненулевое гауссово число ${\displaystyle v}$, то есть представить в виде: ${\displaystyle u=vq+r}$ где частное ${\displaystyle q}$ и остаток ${\displaystyle r}$ — гауссовы числа, причём ${\displaystyle N(r)<N(v)}$.

Несложно показать, что в качестве частного от деления с остатком можно взять гауссово число, ближайшее к частному от обычного деления комплексных чисел^[22].

Необходимо отметить, что условия «норма остатка меньше нормы делителя» недостаточно для того, чтобы гарантировать однозначность остатка от деления, поэтому в ${\displaystyle \mathbb {Z} [i]}$ остаток неоднозначен. Например, ${\displaystyle 7+2i}$ можно разделить на ${\displaystyle 3-i}$ тремя способами:

${\displaystyle 7+2i=(3-i)(2+i)+i=(3-i)(1+i)+3=(3-i)(2+2i)+(-1-2i)}$

Можно гарантировать только то, что все остатки попадают в один класс вычетов по модулю делителя. Впрочем, похожая ситуация имеет место и для обычных целых чисел — например, разделить с остатком 8 на 3 можно двумя способами: ${\displaystyle 8=3\cdot 2+2}$ или ${\displaystyle 8=3\cdot 3-1}$ (оба остатка по модулю меньше делителя) поэтому в арифметике целых чисел введено дополнительное условие, обеспечивающее однозначность операции: остаток должен быть неотрицательным.

Пример. Для деления с остатком ${\displaystyle 11+10i}$ на ${\displaystyle 4+i}$ вначале находится частное от обычного комплексного деления:

${\displaystyle {\frac {11+10i}{4+i}}={\frac {(11+10i)(4-i)}{(4+i)(4-i)}}={\frac {54+29i}{17}}\approx 3{,}17+1{,}7i}$

Ближайшее к результату гауссово число есть ${\displaystyle 3+2i,}$ тогда остаток равен ${\displaystyle 11+10i-(4+i)(3+2i)=1-i}$. В итоге:

${\displaystyle 11+10i=(4+i)(3+2i)+1-i}$

Для гауссовых чисел имеет место аналог китайской теоремы об остатках, поскольку она доказывается с помощью алгоритма Евклида.

Геометрическое представление

Из определения деления с остатком ${\displaystyle u}$ на ${\displaystyle v}$ следует, что ${\displaystyle |r|=|u-vq|}$, то есть модуль остатка есть расстояние между комплексными числами ${\displaystyle u}$ и ${\displaystyle vq}$. Другими словами, ${\displaystyle |r|}$ есть расстояние от делимого до одного из узлов ${\displaystyle v}$-решётки кратных. Требование «норма остатка меньше нормы делителя» эквивалентно условию ${\displaystyle |r|<|v|}$. Отсюда вытекает:

Деление с остатком ${\displaystyle u}$ на ${\displaystyle v}$ имеет столько решений, сколько узлов ${\displaystyle v}$-решётки кратных находится от делимого на расстоянии меньше ${\displaystyle |v|}$.

Распределение числа решений задачи деления с остатком

В вышеприведённом примере деления ${\displaystyle 7+2i}$ на ${\displaystyle 3-i}$ ближайшими к делимому являются кратные делителя, образующие вершины квадрата решётки, содержащего делимое:

${\displaystyle 7+i=(3-i)(2+i)}$

${\displaystyle 4+2i=(3-i)(1+i)}$

${\displaystyle 8+4i=(3-i)(2+2i)}$

Все они находятся от делимого на расстоянии меньше, чем ${\displaystyle |v|={\sqrt {10}}}$. Четвёртая вершина квадрата ${\displaystyle 5+5i}$ удалена от делимого больше чем на ${\displaystyle {\sqrt {10}}}$. Поэтому данная задача деления с остатком имеет три решения.

В общем случае, проведя из вершин квадрата ${\displaystyle v}$-решётки кратных дуги радиусом ${\displaystyle |v|,}$ мы получим фигуру, показанную на рисунке. Если делимое находится в центральной области (красная зона), оно удалено от всех вершин менее чем на ${\displaystyle |v|,}$ и деление с остатком может быть выполнено четырьмя способами. Если делимое находится в одном из «лепестков» (синяя зона), то одна из вершин отпадает, и число решений равно трём. Для белой зоны получаем два решения. Наконец, если делимое совпадает с одной из вершин, то остаток равен нулю, и решение единственно.

Наибольший общий делитель

Кольцо гауссовых чисел является евклидовым, и в нём всегда можно определить наибольший общий делитель, определённый однозначно с точностью до делителей единицы^[23].

Наибольшим общим делителем НОД${\displaystyle (u,v)}$ для гауссовых чисел ${\displaystyle u}$ и ${\displaystyle v}$, хотя бы одно из которых ненулевое, называется их общий делитель, который делится на любой другой общий делитель ${\displaystyle u}$ и ${\displaystyle v}$.

Эквивалентное определение: НОД${\displaystyle (u,v)}$ есть тот общий делитель ${\displaystyle u,v}$, у которого норма максимальна^[24].

Свойства НОД

• Если известен некоторый НОД, то любое из трёх чисел, ассоциированных с ним, также будет НОД. В частности. если один из НОД — делитель единицы, то такими же будут и остальные три НОД.
• Гауссовы числа взаимно просты тогда и только тогда, когда их НОД есть делитель единицы.
• Имеет место аналог соотношения Безу^[25]:

Пусть ${\displaystyle u,v}$ — гауссовы числа, и хотя бы одно из них не нуль. Тогда существуют такие гауссовы числа ${\displaystyle x,y}$, что выполняется соотношение: НОД${\displaystyle (u,v)=xu+yv}$

Другими словами, наибольший общий делитель двух гауссовых чисел можно всегда представить как линейную комбинацию этих чисел с гауссовыми коэффициентами.

• Следствие соотношения Безу^[25]: если гауссовы числа ${\displaystyle u,v}$ взаимно просты, то уравнение ${\displaystyle xu+yv=1}$ относительно ${\displaystyle x,y}$ имеет решение в ${\displaystyle \mathbb {Z} [i]}$. Вместо 1 в приведённом уравнении может стоять любой другой делитель единицы, теорема при этом останется верной.

Алгоритм Евклида и практическое вычисление НОД

Для определения НОД в ${\displaystyle \mathbb {Z} [i]}$ удобно использовать алгоритм Евклида, вполне аналогичный применяемому для целых чисел. НОД получается в этой схеме как последний ненулевой остаток^[26]. Алгоритм Евклида можно также использовать для нахождения коэффициентов ${\displaystyle x,y}$ в соотношении Безу^[20].

Пример 1. Найдём НОД для ${\displaystyle 32+9i}$ и ${\displaystyle 4+11i}$.

Шаг 1: ${\displaystyle 32+9i=(4+11i)(2-2i)+2-5i}$ (разделили с остатком первое число на второе)

Шаг 2: ${\displaystyle 4+11i=(2-5i)(-2+i)+3-i}$ (разделили с остатком предыдущий делитель на остаток предыдущего шага)

Шаг 3: ${\displaystyle 2-5i=(3-i)(1-i)-i}$ (то же действие)

Шаг 4: ${\displaystyle 3-i=(-i)(1+3i)}$ (то же действие, деление выполнилось нацело)

Отметим, что на каждом шаге норма остатка монотонно уменьшается. Последний ненулевой остаток равен ${\displaystyle -i}$, это делитель единицы, поэтому заключаем, что исследуемые числа взаимно просты.

Пример 2. Найдём НОД для ${\displaystyle 11+3i}$ и ${\displaystyle 1+8i}$.

Шаг 1: ${\displaystyle 11+3i=(1+8i)(1-i)+2-4i}$

Шаг 2: ${\displaystyle 1+8i=(2-4i)(-1+i)+(-1+2i)}$

Шаг 3: ${\displaystyle 2-4i=(-1+2i)(-2)}$ (деление выполнилось нацело)

Последний ненулевой остаток равен ${\displaystyle -1+2i}$, это и есть искомый НОД. Последовательно подставляя вместо левых частей равенств правые (начиная с предпоследнего равенства, снизу вверх), получается соотношение Безу для НОД:

${\displaystyle -1+2i=(11+3i)(1-i)+(1+8i)(1+2i)}$

Некоторые приложения

Гаусс использовал открытую им алгебраическую структуру для глубокого исследования биквадратичных вычетов. Можно указать и другие области успешного применения гауссовых чисел^[27]. Примечательно, что значительная их часть относится к теории не комплексных, а натуральных чисел.

Разложение натуральных чисел на сумму двух квадратов

Из критерия Гаусса➤ вытекает, что простое натуральное число вида ${\displaystyle 4n+1}$ можно представить в виде суммы квадратов двух натуральных чисел, причём единственным способом. Пример: ${\displaystyle 29=(2+5i)(2-5i)=2^{2}+5^{2}}$.

Разложение натуральных чисел другого вида не всегда возможно — например, ${\displaystyle 15;19;27;103}$ и другие числа вида ${\displaystyle 4n+3}$ нельзя представить в виде суммы квадратов двух натуральных чисел. Составные числа могут также иметь более одного варианта разложения, например^[27]: ${\displaystyle 65=4^{2}+7^{2}=1^{2}+8^{2}}$. Общая теорема: натуральное число представимо в виде суммы двух квадратов тогда и только тогда, когда в его каноническом разложении все простые множители вида ${\displaystyle 4n+3}$ входят в чётных степенях^[17].

Пример: ${\displaystyle 21=3\cdot 7}$ нельзя представить в виде суммы квадратов, потому что число 3 (как и 7) входит в него с нечётной степенью. Но ${\displaystyle 245=5\cdot 7^{2}}$ представить можно: ${\displaystyle 245=7^{2}+14^{2}}$.

Подсчёт числа представлений в виде суммы двух квадратов

Число представлений ${\displaystyle \rho (m)}$ натурального числа ${\displaystyle m}$ в виде суммы квадратов (или, что то же самое, число гауссовых чисел с нормой ${\displaystyle m}$) можно определить следующим образом^[28]. Разложим ${\displaystyle m}$ на простые натуральные множители:

${\displaystyle m=2^{\lambda }p_{1}^{\lambda _{1}}p_{2}^{\lambda _{2}}\dots p_{r}^{\lambda _{r}}q_{1}^{\mu _{1}}q_{2}^{\mu _{2}}\dots q_{s}^{\mu _{s}}}$

Здесь ${\displaystyle p_{i}}$ — множители вида ${\displaystyle 4n+1,}$ а ${\displaystyle q_{j}}$ — множители вида ${\displaystyle 4n+3}$. Тогда возможны 3 случая.

1. Если хотя бы один показатель степени ${\displaystyle \mu _{j}}$ нечётный, число ${\displaystyle m}$ не может быть представлено в виде суммы квадратов.
2. Пусть все ${\displaystyle \mu _{j}}$ чётные. Окончательная формула зависит от чётности ${\displaystyle \lambda _{i}}$. Если все они тоже чётные, то формула имеет вид:

${\displaystyle \rho (m)={\frac {1}{2}}[(\lambda _{1}+1)(\lambda _{2}+1)\cdots (\lambda _{r}+1)+1]}$

3. Если не все ${\displaystyle \lambda _{i}}$ чётные, то формула немного отличается:

${\displaystyle \rho (m)={\frac {1}{2}}(\lambda _{1}+1)(\lambda _{2}+1)\cdots (\lambda _{r}+1)}$

Теория пифагоровых троек

Пифагорова тройка — это одно из целочисленных решений уравнения:

${\displaystyle x^{2}+y^{2}=z^{2}}$.

Общее решение уравнения зависит от двух целых параметров ${\displaystyle m,n}$:

${\displaystyle x=m^{2}-n^{2};\;y=2mn;\;z=m^{2}+n^{2}}$.

Для генерации пифагоровых троек можно использовать такой приём. Пусть ${\displaystyle z=a+bi}$ — произвольное гауссово число, у которого обе компоненты ${\displaystyle a,b}$ ненулевые. Возведя это число в квадрат, получается некоторое другое гауссово число ${\displaystyle c+di}$. Тогда тройка ${\displaystyle \{|c|;|d|;N(z)\}}$ будет пифагоровой^[27].

Пример: для исходного числа ${\displaystyle z=17+12i}$ получается пифагорова тройка ${\displaystyle (145;408;433)}$.

Решение диофантовых уравнений

Решение многих диофантовых уравнений удаётся найти, если привлечь аппарат гауссовых чисел. Например, для уравнения ${\displaystyle x^{2}+y^{2}=2z^{2}}$ несложные преобразования дают два типа целых взаимно простых решений^[29], зависящих от целых параметров ${\displaystyle a,b}$:

1. ${\displaystyle x=a^{2}-2ab-b^{2};\;y=a^{2}+2ab-b^{2}}$
2. ${\displaystyle x=-a^{2}-2ab+b^{2};\;y=a^{2}-2ab-b^{2}}$

В 1850 году Виктор Лебег, используя гауссовы числа, исследовал уравнение ${\displaystyle x^{2}+1=y^{n}}$ и доказал его неразрешимость в натуральных числах. Другими словами, среди натуральных чисел вида ${\displaystyle n^{2}+1}$ нет ни одного полного куба или иной степени выше второй^[27].

Нерешённые проблемы

• Найти количество гауссовых чисел, норма которых меньше заданной натуральной константы ${\displaystyle R}$. В эквивалентной формулировке эта тема известна как «проблема круга Гаусса» в геометрии чисел^[30][31].
• Найти прямые на комплексной плоскости, содержащие бесконечно много простых гауссовых чисел. Две такие прямые очевидны — это координатные оси; неизвестно, существуют ли другие^[32].
• Вопрос, известный под названием «ров Гаусса»: можно ли дойти до бесконечности, переходя от одного простого гауссова числа к другому скачками заранее ограниченной длины? Задача поставлена в 1962 году и до сих пор не решена^[33].

Вариации и обобщения

Треугольная решётка чисел Эйзенштейна

Ещё одним исторически важным евклидовым кольцом, похожим по свойствам на целые числа, стали «целые числа Эйзенштейна».

Гауссовы рациональные числа, обозначаемые ${\displaystyle \mathbb {Q} (i)}$ — это комплексные числа вида ${\displaystyle a+bi}$, где ${\displaystyle a,b}$ — рациональные числа. Это множество замкнуто относительно всех 4 арифметических операций, включая деление, и поэтому является полем, расширяющим кольцо гауссовых чисел.

История

В 1820-х годах Карл Фридрих Гаусс исследовал биквадратичный закон взаимности, результатом стала монография «Теория биквадратичных вычетов» (1828—1832). Именно в этом труде целые комплексные числа доказали свою полезность для решения задач теории чисел, хотя формулировка этих задач никак не связана с комплексными числами. Гаусс писал, что «естественный источник общей теории следует искать в расширении области арифметики»^[3].

Карл Фридрих Гаусс в 1828 году

В книге Гаусса было показано, что новые числа по своим свойствам во многом напоминают обычные целые числа. Автор описал четыре делителя единицы, определил отношение ассоциированности, понятие простого числа, дал критерий простоты и доказал аналоги основной теоремы арифметики, малой теоремы Ферма. Далее Гаусс подробно рассмотрел вычеты по комплексному модулю, индексы и первообразные корни. Главным достижением построенной теории стал биквадратичный закон взаимности, который Гаусс обещал доказать в следующем томе; этот том так и не был опубликован, но в рукописях Гаусса была обнаружена подробная схема строгого доказательства^[3].

Гаусс использовал введённые им числа также и в других своих трудах, например, по алгебраическим уравнениям^[34]. Идеи Гаусса были развиты в трудах Карла Густава Якоба Якоби и Фердинанда Готтхольда Эйзенштейна. В середине XIX века Эйзенштейн, Дирихле и Эрмит ввели и исследовали обобщённое понятие целого алгебраического числа.

Кольцо гауссовых целых чисел было одним из первых примеров алгебраической структуры с непривычными свойствами. Со временем было открыто большое количество структур такого типа, а в конце XIX века появилась абстрактная алгебра, изучающая алгебраические свойства отдельно от объектов-носителей этих свойств.

Примечания

1. Математическая энциклопедия, 1977.
2. Гаусс К. Ф., 1959, с. 655—754.
3. Математика XIX века. Том I: Математическая логика, алгебра, теория чисел, теория вероятностей, 1978, с. 88—92.
4. Кузьмин Р. О., Фаддеев Д. К., 1939, с. 146.
5. Айерлэнд К., Роузен М., 1987, с. 23.
6. Окунев Л. Я., 1941, с. 27—28.
7. Кузьмин Р. О., Фаддеев Д. К., 1939, с. 147—149.
8. Окунев Л. Я., 1941, с. 29.
9. Окунев Л. Я., 1941, с. 32.
10. Кузьмин Р. О., Фаддеев Д. К., 1939, с. 150.
11. Кузьмин Р. О., Фаддеев Д. К., 1939, с. 155.
12. Кузьмин Р. О., Фаддеев Д. К., 1939, с. 156.
13. Окунев Л. Я., 1941, с. 41, 44.
14. A classification of gaussian primes, с. 10.
15. Гаусс К. Ф., 1959, с. 698.
16. Кузьмин Р. О., Фаддеев Д. К., 1939, с. 158.
17. Conrad, Keith, Глава 9.
18. Окунев Л. Я., 1941, с. 33—34.
19. Conrad, Keith, Глава 6.
20. Conrad, Keith, Глава 7.
21. Conrad, Keith, Глава 3.
22. Окунев Л. Я., 1941, с. 30—31.
23. Окунев Л. Я., 1941, с. 35—36.
24. Conrad, Keith, Глава 4.
25. Conrad, Keith, Глава 5.
26. Кузьмин Р. О., Фаддеев Д. К., 1939, с. 153—155.
27. Conrad, Keith, Глава 8.
28. Кузьмин Р. О., Фаддеев Д. К., 1939, с. 164—166.
29. Кузьмин Р. О., Фаддеев Д. К., 1939, с. 162—163.
30. Conway J. H., Sloane N. J. A. Sphere Packings, Lattices and Groups. — Springer-Verlag. — P. 106.
31. последовательность A000328 в OEIS
32. Ribenboim, Paulo. The New Book of Prime Number Records, Ch.III.4.D Ch. 6.II, Ch. 6.IV. — 3rd ed. — New York: Springer, 1996. — ISBN 0-387-94457-5.
33. Guy Richard K. Unsolved problems in number theory. — 3rd ed. — New York: Springer, 2004. — P. 55—57. — ISBN 978-0-387-20860-2.
34. Hardy G. H., Wright E. M., 1968, с. 189.

Литература

• Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. — М.: Мир, 1987. — 416 с.
• Алфутова Н. Б, Устинов А. В. Алгебра и теория чисел. Сборник задач для математических школ. — 3-е изд., испр. и доп. — М.: МЦНМО, 2009. — 336 с. — ISBN 978-5-94057-550-4.
• Гаусс К. Ф. Труды по теории чисел. — М.: Изд-во АН СССР, 1959. — С. 695—754.
• Гауссово число // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1977. — Т. 1.
• Калужнин Л. А. Основная теорема арифметики. — М.: Наука, 1969. — 32 с. — (Популярные лекции по математике).
• Колмогоров А. Н., Юшкевич А. П. (ред.). Математика XIX века. Математическая логика, алгебра, теория чисел, теория вероятностей. — М.: Наука, 1978. — Т. I.
• Кузьмин Р. О., Фаддеев Д. К. Алгебра и арифметика комплексных чисел. Пособие для учителей. — М.: Учпедгиз, 1939. — 187 с.
• Окунев Л. Я. Целые комплексные числа. — М.: Гос. уч.-пед. изд-во Наркомпроса РСФСР, 1941. — 56 с.
• Сендеров В., Спивак А. Суммы квадратов и целые гауссовы числа // Квант. — 1999. — № 3. — С. 14—22.
• Hardy G. H., Wright E. M. An introduction to the theory of numbers (англ.). — 4th edition. — Oxford.: Oxford University Press, 1968. — 421 p.

Ссылки

• Complex Gaussian Integers for 'Gaussian Graphics' (англ.). Дата обращения: 11 сентября 2013. Архивировано из оригинала 14 июня 2006 года.
• Butler, Lee A. A classification of gaussian primes (англ.). Дата обращения: 16 января 2017.
• Conrad, Keith. The gaussian integers (англ.). Дата обращения: 11 сентября 2013.