Русская Википедия:Гауссовы целые числа

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

Га́уссовы це́лые чи́сла (гауссовы числа, целые комплексные числа) — это комплексные числа, у которых как вещественная, так и мнимая часть — целые числаШаблон:Sfn.

Примеры: <math>1+2i;\quad -4+11i;\quad 4i;\quad 5;\quad 1-i</math>.

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

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

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

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

<math>\mathbb{Z}[i] = \{a+bi \mid a,b\in \mathbb{Z} \}</math>.

Множество <math>\mathbb{Z}[i]</math> содержит множество обычных целых чисел <math>\mathbb{Z}</math> и представляет собой его расширениеШаблон:Sfn. Сумма, разность и произведение гауссовых чисел являются гауссовыми числами; для них, как и для целых чисел, сохраняются свойства ассоциативности, коммутативности и дистрибутивности — такая алгебраическая структура называется в общей алгебре коммутативным кольцом Шаблон:Sfn. Ввести в этом комплексном кольце упорядоченность, согласованную с порядком вещественных чисел, невозможно.

Сопряжённое к гауссовому числу <math>a+bi</math> есть также гауссово число <math>a-bi</math>.

Каждое гауссово число <math>z=a+bi</math> удовлетворяет квадратному уравнению:

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

Норма

Норма для гауссова числа <math>a + bi</math> определяется как квадрат его модуля Шаблон:Sfn:

<math>N \left(a+bi \right) = a^2+b^2 = (a+bi)\overline{(a+bi)}</math>.

Свойства нормыШаблон:Sfn:

Норма равна нулю только для нуля. В остальных случаях норма — положительное целое число.
Нормы сопряжённых чисел совпадают.
Норма обычного целого числа равна его квадрату.
Если норма нечётна, то она имеет вид <math>4 n + 1</math>, то есть при делении её на 4 получается остаток 1. Никакое гауссово число не может иметь норму вида <math>4 n + 3</math>.

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

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

Два гауссовых числа называются ассоциированными, если одно получается из другого умножением на делитель единицы. Легко видеть, что ассоциированность — отношение эквивалентности^[2]. Пример: гауссовы числа <math>1+i</math> и <math>1-i</math> ассоциированы, поскольку:

<math>1+i = i(1-i)</math>.

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

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

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

Деление нацело гауссовых чисел определяется обычным образом^[1]: Шаблон:Рамка Говорят, что гауссово число <math>u</math> делится (нацело) на гауссово число <math>v</math>, если существует третье гауссово число <math>q</math> такое, что <math>u=vq</math>. Обозначение: <math>v \mid u</math>. Шаблон:Конец рамки Произношение: один из трёх равносильных вариантов.

<math>u</math> делится на <math>v</math>;
<math>v</math> делит <math>u</math>;
<math>v</math> — делитель <math>u</math>.

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

Пример: число 2 делится нацело на <math>1+i</math>, потому что <math>2=(1+i)(1-i)</math>.

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

Деление нацело в <math>\mathbb{Z}[i]</math> по своим свойствам похоже на аналогичное деление целых чисел. Некоторые специфические для гауссовых чисел особенностиШаблон:Sfn^[1]:

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

<math>N\left(\frac{u}{v}\right) = \frac {N(u)} {N(v)}</math>

Файл:Gaussian multiples.jpg

Решётка кратных для <math>1+2i</math>

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

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

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

Пример: на рисунке одним из узлов решётки является число <math>4-2i</math>, кратное <math>1+2i</math>:

<math>4-2i=-2i(1+2i)</math>.

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

Файл:Gauss-primes-768x768.png

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

Файл:Gaussian primes.png

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

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

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

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

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

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

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

Если гауссово число <math>w</math> является делителем для двух гауссовых чисел <math>u</math> и <math>v</math>, оно называется их общим делителем. Множество общих делителей двух чисел всегда содержит 4 делителя единицы; если других общих делителей нет, эти числа называются взаимно простымиШаблон:Sfn.

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

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

Если каждое из двух гауссовых чисел <math>u,v</math> взаимно просто с гауссовым числом <math>w,</math> то и их произведение <math>uv</math> тоже взаимно просто^[3] с <math>w</math>.
Если <math>z|uv</math> и при этом <math>z</math> взаимно просто с <math>u</math>, тоШаблон:Sfn <math>z|v</math>.

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

Гаусс указал определяющие признаки простого числа в <math>\mathbb{Z}[i]</math>Шаблон:Sfn. Шаблон:Рамка Гауссово число <math>a+bi</math> является простым тогда и только тогда, когда:

либо одно из чисел <math>a, b</math> нулевое, а другое — целое простое число вида Шаблон:S;
либо <math>a, b</math> оба не нули и норма <math>a^2+b^2</math> — простое натуральное число.

Шаблон:Конец рамки Примеры простых гауссовых чисел:

к первой части критерия: <math>\pm 3;\ \pm 7;\ \pm 3i</math>;
ко второй части критерия: <math>1 \pm i;\ 1 \pm 2i;\ 1 \pm 4i;\ 4+5i;\ 2-3i;\ 15+22i</math>.

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

Числа, ассоциированные с <math>1+i</math>. Их норма равна 2.
Числа, норма которых есть простое натуральное число вида <math>4n+1</math>.

Сам Гаусс такого разделения не делалШаблон:Sfn.

Следствия:

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

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

В <math>\mathbb{Z}[i]</math> имеет место аналог основной теоремы арифметики: каждое гауссово число, не являющееся нулём или делителем единицы, разлагается на простые множители, причём это разложение однозначно с точностью до порядка и ассоциированности множителей^[5]Шаблон:Sfn.

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

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

Таким образом, начать следует с разложения нормы числа <math>z</math> на простые натуральные множителиШаблон:Sfn.

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

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

<math>9+12i=3\cdot(2+i)^2</math>.

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

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

Понятие сравнения по модулю определяется в <math>\mathbb{Z}[i]</math> аналогично тому, как это делается для целых чисел^[6]: Шаблон:Рамка Пусть <math>w</math> — некоторое гауссово число. Два гауссовых числа <math>u, v</math> называются сравнимыми по модулю <math>w</math>, если разность <math>u-v</math> делится (нацело) на <math>w</math>. Запись: <math>u\equiv v\pmod w</math>. Шаблон:Конец рамки Свойства сравнений в <math>\mathbb{Z}[i]</math> в основном такие же, как у целых чисел. Отношение сравнимости есть отношение эквивалентности, поэтому <math>\mathbb{Z}[i]</math> разбивается на непересекающиеся классы вычетов — каждый такой класс содержит все сравнимые друг с другом (по заданному модулю) гауссовы числа. Для классов, как в случае целых чисел, можно определить сложение и умножение, так что получается кольцо вычетов по гауссову модулю.

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

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

Как обнаружил Гаусс, кольцо вычетов по модулю <math>a+bi</math> содержит <math>N(a+bi)=a^2+b^2</math> элементовШаблон:Sfn. Этот факт вынуждает модифицировать некоторые классические теоремы. Например, малая теорема Ферма для целых чисел утверждает, что <math>(a^p-a)</math> делится на <math>p</math> для любого простого <math>p</math> и натурального <math>a</math>. Для гауссовых чисел это неверно, даже если ограничиться натуральными значениями <math>p</math>; например, для целых чисел <math>a^3-a</math> всегда делится на 3, а для гауссовых <math>i^3-i=-2i</math>, и это значение на 3 не делится. Модифицированный аналог малой теоремы Ферма формулируется следующим образом^[6]: Шаблон:Теорема На том же примере с <math>w=3; u=i</math> результат: <math>(i^9-i)=0</math> — делится на 3.

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

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

Введём аналог функции Эйлера для гауссовых чисел. Определение для целых чисел не годится хотя бы потому, что содержащееся в нём выражение «от <math>1</math> до <math>n</math>» не имеет смысла для комплексных чисел. Новое определение^[6]: Шаблон:Рамка Функция Эйлера <math>\varphi(z)</math> для гауссова числа <math>z</math> определяется как число обратимых классов вычетов по модулю <math>z</math>. Шаблон:Конец рамки Определённая таким образом функция, как и её прототип для целых чисел, мультипликативна, поэтому достаточно знать её значения для простых чисел и их натуральных степеней. Если <math>z</math> — простое гауссово число, то^[6]:

<math>\varphi(z)=N(z)-1; \quad \varphi(z^k)=N(z)^{k-1}(N(z)-1)</math>

Пример: <math>\varphi(3+4i) = \varphi((2+i)^2) = N(2+i)(N(2+i)-1) = 5\cdot 4 = 20</math>.

Теперь можно обобщить приведённую в предыдущем разделе малую теорему Ферма на случай произвольного (не обязательно простого) модуля сравнения, то есть привести аналог теоремы Эйлера^[6]: Шаблон:Рамка Если гауссово число <math>z</math> взаимно просто с модулем <math>w,</math>, то:

<math>z^{\varphi(w)} \equiv 1 \pmod w</math>

Шаблон:Конец рамки

Файл:Gaussian congruent.jpg

Сравнение по модулю <math>1+2i</math>

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

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

Каждый квадрат решётки получается из любого другого квадрата сдвигом (переносом) на величину, кратную <math>w,</math> поэтому разность любой точки квадрата и результата её сдвига тоже кратна <math>w</math>. Отсюда следует окончательный вывод^[6]: Шаблон:Рамка Гауссовы числа сравнимы по модулю <math>w</math> тогда и только тогда, когда они занимают одно и то же относительное положение в своих квадратах решётки кратных. Шаблон:Конец рамки Например, сравнимы все центры квадратов, или все середины их соответствующих сторон и т. п.

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

Определение

В кольце <math>\mathbb{Z}[i]</math> можно определить деление с остатком (на любое ненулевое гауссово число), потребовав, чтобы норма остатка была меньше нормы делителяШаблон:Sfn: Шаблон:Рамка Любое гауссово число <math>u</math> можно разделить с остатком на любое ненулевое гауссово число <math>v</math>, то есть представить в виде:

где частное <math>q</math> и остаток <math>r</math> — гауссовы числа, причём <math>N(r)<N(v)</math>. Шаблон:Конец рамки Несложно показать, что в качестве частного от деления с остатком можно взять гауссово число, ближайшее к частному от обычного деления комплексных чиселШаблон:Sfn.

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

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

Пример. Для деления с остатком <math>11+10i</math> на <math>4+i</math> вначале находится частное от обычного комплексного деления:

<math>\frac{11+10i}{4+i} = \frac{(11+10i)(4-i)}{(4+i)(4-i)} = \frac{54+29i}{17} \approx 3{,}17+1{,}7i</math>

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

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

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

Из определения деления с остатком <math>u</math> на <math>v</math> следует, что <math>|r|=|u-vq|</math>, то есть модуль остатка есть расстояние между комплексными числами <math>u</math> и <math>vq</math>. Другими словами, <math>|r|</math> есть расстояние от делимого до одного из узлов <math>v</math>-решётки кратных. Требование «норма остатка меньше нормы делителя» эквивалентно условию <math>|r|<|v|</math>. Отсюда вытекает: Шаблон:Рамка Деление с остатком <math>u</math> на <math>v</math> имеет столько решений, сколько узлов <math>v</math>-решётки кратных находится от делимого на расстоянии меньше <math>|v|</math>. Шаблон:Конец рамки

Файл:Gaussian modulo.jpg

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

В вышеприведённом примере деления <math>7+2i</math> на <math>3-i</math> ближайшими к делимому являются кратные делителя, образующие вершины квадрата решётки, содержащего делимое:

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

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

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

Кольцо гауссовых чисел является евклидовым, и в нём всегда можно определить наибольший общий делитель, определённый однозначно с точностью до делителей единицыШаблон:Sfn. Шаблон:Рамка Наибольшим общим делителем НОД<math>(u, v)</math> для гауссовых чисел <math>u</math> и <math>v</math>, хотя бы одно из которых ненулевое, называется их общий делитель, который делится на любой другой общий делитель <math>u</math> и <math>v</math>. Шаблон:Конец рамки Эквивалентное определение: НОД<math>(u, v)</math> есть тот общий делитель <math>u, v</math>, у которого норма максимальнаШаблон:Sfn.

Свойства НОД

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

Шаблон:Рамка Пусть <math>u, v</math> — гауссовы числа, и хотя бы одно из них не нуль. Тогда существуют такие гауссовы числа <math>x, y</math>, что выполняется соотношение:

НОД<math>(u, v) = xu + yv</math>

Шаблон:Конец рамки

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

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

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

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

Пример 1. Найдём НОД для <math>32+9i</math> и <math>4+11i</math>.

Шаг 1: <math>32+9i = (4+11i) (2-2i) + 2-5i</math> (разделили с остатком первое число на второе)

Шаг 2: <math>4+11i = (2-5i) (-2+i) + 3-i</math> (разделили с остатком предыдущий делитель на остаток предыдущего шага)

Шаг 3: <math>2-5i = (3-i) (1-i) -i</math> (то же действие)

Шаг 4: <math>3-i = (-i) (1+3i)</math> (то же действие, деление выполнилось нацело)

Отметим, что на каждом шаге норма остатка монотонно уменьшается. Последний ненулевой остаток равен <math>-i</math>, это делитель единицы, поэтому заключаем, что исследуемые числа взаимно просты.

Пример 2. Найдём НОД для <math>11+3i</math> и <math>1+8i</math>.

Шаг 1: <math>11+3i = (1+8i) (1-i) +2-4i</math>

Шаг 2: <math>1+8i = (2-4i) (-1+i) +(-1+2i)</math>

Шаг 3: <math>2-4i = (-1+2i) (-2)</math> (деление выполнилось нацело)

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

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

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

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

Из критерия ГауссаШаблон:Переход вытекает, что простое натуральное число вида <math>4n+1</math> можно представить в виде суммы квадратов двух натуральных чисел, причём единственным способом. Пример: <math>29=(2+5i)(2-5i)=2^2+5^2</math>.

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

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

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

Число представлений <math>\rho(m)</math> натурального числа <math>m</math> в виде суммы квадратов (или, что то же самое, число гауссовых чисел с нормой <math>m</math>) можно определить следующим образомШаблон:Sfn. Разложим <math>m</math> на простые натуральные множители:

<math>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}</math>

Здесь <math>p_i</math> — множители вида <math>4n+1,</math> а <math>q_j</math> — множители вида <math>4n+3</math>. Тогда возможны 3 случая.

Если хотя бы один показатель степени <math>\mu_j</math> нечётный, число <math>m</math> не может быть представлено в виде суммы квадратов.
Пусть все <math>\mu_j</math> чётные. Окончательная формула зависит от чётности <math>\lambda_i</math>. Если все они тоже чётные, то формула имеет вид:

<math>\rho(m)=\frac{1}{2} [(\lambda_1+1) (\lambda_2+1) \cdots (\lambda_r+1) + 1 ]</math>

Если не все <math>\lambda_i</math> чётные, то формула немного отличается:

<math>\rho(m)=\frac{1}{2} (\lambda_1+1) (\lambda_2+1) \cdots (\lambda_r+1)</math>

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

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

<math>x^2+y^2=z^2</math>.

Общее решение уравнения зависит от двух целых параметров <math>m,n</math>:

<math>x=m^2-n^2; \; y=2mn; \; z=m^2+n^2</math>.

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

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

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

Решение многих диофантовых уравнений удаётся найти, если привлечь аппарат гауссовых чисел. Например, для уравнения <math>x^2+y^2=2z^2</math> несложные преобразования дают два типа целых взаимно простых решенийШаблон:Sfn, зависящих от целых параметров <math>a,b</math>:

<math>x=a^2-2ab-b^2; \; y=a^2+2ab-b^2</math>
<math>x=-a^2-2ab+b^2; \; y=a^2-2ab-b^2</math>

В 1850 году Виктор Лебег, используя гауссовы числа, исследовал уравнение <math>x^2+1=y^n</math> и доказал его неразрешимость в натуральных числах. Другими словами, среди натуральных чисел вида <math>n^2+1</math> нет ни одного полного куба или иной степени выше второй^[8].

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

Найти количество гауссовых чисел, норма которых меньше заданной натуральной константы <math>R</math>. В эквивалентной формулировке эта тема известна как «проблема круга Гаусса» в геометрии чисел^[9]^[10].
Найти прямые на комплексной плоскости, содержащие бесконечно много простых гауссовых чисел. Две такие прямые очевидны — это координатные оси; неизвестно, существуют ли другие^[11].
Вопрос, известный под названием «ров Гаусса»: можно ли дойти до бесконечности, переходя от одного простого гауссова числа к другому скачками заранее ограниченной длины? Задача поставлена в 1962 году и до сих пор не решена^[12].

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

Файл:Eisenstein integer lattice.png

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

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

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

История

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

Файл:Bendixen - Carl Friedrich Gauß, 1828.jpg

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

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

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

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

Примечания

Шаблон:Примечания

Литература

Ссылки

Шаблон:ВС Шаблон:Алгебраические числа Шаблон:Хорошая статья

↑ ^1,0 ^1,1 ^1,2 Ошибка цитирования Неверный тег <ref>; для сносок KF148 не указан текст
↑ ^2,0 ^2,1 Ошибка цитирования Неверный тег <ref>; для сносок OKU29 не указан текст
↑ Ошибка цитирования Неверный тег <ref>; для сносок KF155 не указан текст
↑ ^4,0 ^4,1 Ошибка цитирования Неверный тег <ref>; для сносок CON9 не указан текст
↑ Ошибка цитирования Неверный тег <ref>; для сносок MATH не указан текст
↑ ^6,0 ^6,1 ^6,2 ^6,3 ^6,4 ^6,5 ^6,6 ^6,7 Ошибка цитирования Неверный тег <ref>; для сносок CON7 не указан текст
↑ Ошибка цитирования Неверный тег <ref>; для сносок CON5 не указан текст
↑ ^8,0 ^8,1 ^8,2 Ошибка цитирования Неверный тег <ref>; для сносок CON8 не указан текст
↑ Шаблон:Книга
↑ Шаблон:OEIS
↑ Шаблон:Книга
↑ Шаблон:Книга
↑ ^13,0 ^13,1 Ошибка цитирования Неверный тег <ref>; для сносок XIX не указан текст

[KF148-1] 1,0 ^1,1 ^1,2 Ошибка цитирования Неверный тег <ref>; для сносок KF148 не указан текст

[OKU29-2] 2,0 ^2,1 Ошибка цитирования Неверный тег <ref>; для сносок OKU29 не указан текст

[KF155-3] Ошибка цитирования Неверный тег <ref>; для сносок KF155 не указан текст

[CON9-4] 4,0 ^4,1 Ошибка цитирования Неверный тег <ref>; для сносок CON9 не указан текст

[MATH-5] Ошибка цитирования Неверный тег <ref>; для сносок MATH не указан текст

[CON7-6] 6,0 ^6,1 ^6,2 ^6,3 ^6,4 ^6,5 ^6,6 ^6,7 Ошибка цитирования Неверный тег <ref>; для сносок CON7 не указан текст

[CON5-7] Ошибка цитирования Неверный тег <ref>; для сносок CON5 не указан текст

[CON8-8] 8,0 ^8,1 ^8,2 Ошибка цитирования Неверный тег <ref>; для сносок CON8 не указан текст

[9] Шаблон:Книга

[10] Шаблон:OEIS

[11] Шаблон:Книга

[12] Шаблон:Книга

[XIX-13] 13,0 ^13,1 Ошибка цитирования Неверный тег <ref>; для сносок XIX не указан текст

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.