Гауссовы целые числа
Га́уссовы це́лые чи́сла (гауссовы числа, целые комплексные числа) — это комплексные числа, у которых как вещественная, так и мнимая часть — целые числа[1].
Примеры: [math]\displaystyle{ 1+2i;\quad -4+11i;\quad 4i;\quad 5;\quad 1-i }[/math].
Впервые введены Гауссом в монографии «Теория биквадратичных вычетов» (1828—1832)[2] [3]. Множество гауссовых целых чисел принято обозначать [math]\displaystyle{ \mathbb{Z}[i], }[/math] отражая тем самым тот факт, что оно получается из множества целых чисел [math]\displaystyle{ \mathbb{Z} }[/math] добавлением в него мнимой единицы [math]\displaystyle{ i }[/math] и комбинаций её с целыми числами. Свойства гауссовых чисел похожи на свойства обычных целых чисел, однако имеются и существенные отличия.
Общие свойства
Определение и классификация
Формальное определение:
- [math]\displaystyle{ \mathbb{Z}[i] = \{a+bi \mid a,b\in \mathbb{Z} \} }[/math].
Множество [math]\displaystyle{ \mathbb{Z}[i] }[/math] содержит множество обычных целых чисел [math]\displaystyle{ \mathbb{Z} }[/math] и представляет собой его расширение[4]. Сумма, разность и произведение гауссовых чисел являются гауссовыми числами; для них, как и для целых чисел, сохраняются свойства ассоциативности, коммутативности и дистрибутивности — такая алгебраическая структура называется в общей алгебре коммутативным кольцом[5]. Ввести в этом комплексном кольце упорядоченность, согласованную с порядком вещественных чисел, невозможно.
Сопряжённое к гауссовому числу [math]\displaystyle{ a+bi }[/math] есть также гауссово число [math]\displaystyle{ a-bi }[/math].
Каждое гауссово число [math]\displaystyle{ z=a+bi }[/math] удовлетворяет квадратному уравнению:
- [math]\displaystyle{ (z-a)^2+b^2=0 }[/math]
Поэтому гауссово число есть целое алгебраическое число.
Норма
Норма для гауссова числа [math]\displaystyle{ a + bi }[/math] определяется как квадрат его модуля[6]:
- [math]\displaystyle{ N \left(a+bi \right) = a^2+b^2 = (a+bi)\overline{(a+bi)} }[/math].
Свойства нормы[7]:
- Норма равна нулю только для нуля. В остальных случаях норма — положительное целое число.
- Нормы сопряжённых чисел совпадают.
- Норма обычного целого числа равна его квадрату.
- Если норма нечётна, то она имеет вид [math]\displaystyle{ 4 n + 1 }[/math], то есть при делении её на 4 получается остаток 1. Никакое гауссово число не может иметь норму вида [math]\displaystyle{ 4 n + 3 }[/math].
Норма, как и модуль, обладает важным свойством мультипликативности[7]:
- [math]\displaystyle{ N(u\cdot v) = N(u)\cdot N(v) }[/math]
Отсюда следует[8], что обратимыми элементами кольца (делителями единицы) являются те элементы, у которых норма равна 1, то есть [math]\displaystyle{ \{1; -1; i; -i \} }[/math].
Два гауссовых числа называются ассоциированными, если одно получается из другого умножением на делитель единицы. Легко видеть, что ассоциированность — отношение эквивалентности[8]. Пример: гауссовы числа [math]\displaystyle{ 1+i }[/math] и [math]\displaystyle{ 1-i }[/math] ассоциированы, поскольку:
- [math]\displaystyle{ 1+i = i(1-i) }[/math].
У каждого ненулевого гауссова числа есть три ассоциированных с ним. Нормы всех четырёх ассоциированных между собой чисел совпадают.
Теория делимости
Деление нацело
Деление нацело гауссовых чисел определяется обычным образом[7]:
Говорят, что гауссово число [math]\displaystyle{ u }[/math] делится (нацело) на гауссово число [math]\displaystyle{ v }[/math], если существует третье гауссово число [math]\displaystyle{ q }[/math] такое, что [math]\displaystyle{ u=vq }[/math]. Обозначение: [math]\displaystyle{ v \mid u }[/math]. |
Произношение: один из трёх равносильных вариантов.
- [math]\displaystyle{ u }[/math] делится на [math]\displaystyle{ v }[/math];
- [math]\displaystyle{ v }[/math] делит [math]\displaystyle{ u }[/math];
- [math]\displaystyle{ v }[/math] — делитель [math]\displaystyle{ u }[/math].
Используются традиционные термины: делимое или кратное ([math]\displaystyle{ u }[/math]), делитель ([math]\displaystyle{ v }[/math]) и частное от деления ([math]\displaystyle{ q }[/math]). Количество делителей гауссова числа всегда конечно, количество кратных бесконечно.
Пример: число 2 делится нацело на [math]\displaystyle{ 1+i }[/math], потому что [math]\displaystyle{ 2=(1+i)(1-i) }[/math].
Все гауссовы числа делятся на делители единицы, поэтому любое гауссово число, отличное от делителей единицы, имеет как минимум 8 делителей: 4 делителя единицы и 4 их произведения на само это число. Эти делители называются тривиальными[9].
Деление нацело в [math]\displaystyle{ \mathbb{Z}[i] }[/math] по своим свойствам похоже на аналогичное деление целых чисел. Некоторые специфические для гауссовых чисел особенности[8][7]:
- Если гауссово число [math]\displaystyle{ z }[/math] делится нацело на обычное целое число, то на это целое число делятся как вещественная, так и мнимая часть [math]\displaystyle{ z }[/math].
- Если [math]\displaystyle{ u \mid v }[/math] и [math]\displaystyle{ v \mid u }[/math], то эти числа ассоциированы.
- Если [math]\displaystyle{ u \mid v }[/math], то любое из 3 чисел, ассоциированных с [math]\displaystyle{ v }[/math], делится на любое из 3 чисел, ассоциированных с [math]\displaystyle{ u }[/math].
- Если [math]\displaystyle{ u }[/math] делится на [math]\displaystyle{ v\; (u=vq) }[/math], то сопряжённое к делимому число [math]\displaystyle{ \overline u }[/math] делится на сопряжённое к делителю [math]\displaystyle{ \overline v \; (\overline u=\overline v\overline q) }[/math].
- Все делители гауссова числа [math]\displaystyle{ z }[/math] являются также делителями его нормы [math]\displaystyle{ N(z)=z \cdot \overline{z} }[/math].
- Норма гауссова числа чётна тогда и только тогда, когда это число делится на [math]\displaystyle{ 1+i }[/math].
- Если [math]\displaystyle{ v \mid u }[/math], то и норма делимого, в силу мультипликативности, делится нацело на норму делителя. При этом:
- [math]\displaystyle{ N\left(\frac{u}{v}\right) = \frac {N(u)} {N(v)} }[/math]
Геометрическое представление делимости
У каждого гауссова числа [math]\displaystyle{ z }[/math] есть 4 кратных с той же нормой (и, соответственно, тем же модулем) — это само [math]\displaystyle{ z }[/math] и ассоциированные с ним 3 числа, которые получаются последовательным умножением [math]\displaystyle{ z }[/math] на [math]\displaystyle{ i }[/math]:
- [math]\displaystyle{ z;\ iz;\ -z;\ -iz }[/math]
Но умножение на [math]\displaystyle{ i }[/math] означает на комплексной плоскости поворот радиус-вектора числа на 90° против часовой стрелки, причём модуль результата будет тем же. Таким образом, все 4 числа образуют равносторонний крест (выделен красным на рисунке), центр и вершины которого кратны [math]\displaystyle{ z }[/math]. Последовательно сдвигая этот крест во все стороны на одну из 4 величин, ассоциированных с [math]\displaystyle{ z }[/math], мы получаем на всей плоскости квадратную решётку, все узлы которой (вершины квадратов) кратны [math]\displaystyle{ z }[/math]. Обратно, любое кратное [math]\displaystyle{ z }[/math] совпадает с одним из узлов решётки. Ширина каждого квадрата решётки равна [math]\displaystyle{ |z| }[/math]. Далее для краткости эта решётка будет называться «решёткой кратных» (или, если требуется уточнение, «[math]\displaystyle{ z }[/math]-решёткой кратных»).
Пример: на рисунке одним из узлов решётки является число [math]\displaystyle{ 4-2i }[/math], кратное [math]\displaystyle{ 1+2i }[/math]:
- [math]\displaystyle{ 4-2i=-2i(1+2i) }[/math].
Простые гауссовы числа
Простое гауссово число — это ненулевое число, не имеющее других делителей, кроме тривиальных. Число, не являющееся простым, называется составным. При этом делители единицы, подобно натуральной единице, не считаются ни простыми, ни составными числами[10].
Некоторые свойства простых гауссовых чисел:
- Если [math]\displaystyle{ a+bi }[/math] — простое гауссово число, то противоположное [math]\displaystyle{ -a-bi }[/math] и сопряжённое к нему [math]\displaystyle{ a-bi }[/math] гауссовы числа тоже являются простыми.
- Если простое гауссово число является делителем произведения гауссовых чисел, то оно является делителем по крайней мере одного из сомножителей.
- Норма любого простого гауссова числа, кроме ассоциированных с [math]\displaystyle{ 1+i }[/math], всегда нечётна и поэтому имеет вид [math]\displaystyle{ 4n+1 }[/math].
Натуральное простое число может не быть гауссовым простым числом. Например, числа 2 и 5 в [math]\displaystyle{ \mathbb{Z}[i] }[/math] уже не простые:
- [math]\displaystyle{ 2 = (1+i)(1-i);\quad 5 = (2+i)(2-i) }[/math]
Разложение гауссовых чисел с нормой от 2 до 100 на простые гауссовы множители см. в таблице Факторизация гауссовых чисел.
Взаимно простые числа
Если гауссово число [math]\displaystyle{ w }[/math] является делителем для двух гауссовых чисел [math]\displaystyle{ u }[/math] и [math]\displaystyle{ v }[/math], оно называется их общим делителем. Множество общих делителей двух чисел всегда содержит 4 делителя единицы; если других общих делителей нет, эти числа называются взаимно простыми[11].
Отметим, что если нормы гауссовых чисел [math]\displaystyle{ u, v }[/math] взаимно просты как целые числа, то и сами числа [math]\displaystyle{ u, v }[/math] взаимно просты как гауссовы числа. Обратное неверно: нормы взаимно простых гауссовых чисел могут иметь общие делители — например, [math]\displaystyle{ 5+2i }[/math] и [math]\displaystyle{ 5-2i }[/math] взаимно просты, но их нормы совпадают и поэтому не взаимно просты.
Укажем два свойства, аналогичные свойствам целых чисел.
- Если каждое из двух гауссовых чисел [math]\displaystyle{ u,v }[/math] взаимно просто с гауссовым числом [math]\displaystyle{ w, }[/math] то и их произведение [math]\displaystyle{ uv }[/math] тоже взаимно просто[11] с [math]\displaystyle{ w }[/math].
- Если [math]\displaystyle{ z|uv }[/math] и при этом [math]\displaystyle{ z }[/math] взаимно просто с [math]\displaystyle{ u }[/math], то[12] [math]\displaystyle{ z|v }[/math].
Критерий Гаусса
Гаусс указал определяющие признаки простого числа в [math]\displaystyle{ \mathbb{Z}[i] }[/math][13].
Гауссово число [math]\displaystyle{ a+bi }[/math] является простым тогда и только тогда, когда:
|
Примеры простых гауссовых чисел:
- к первой части критерия: [math]\displaystyle{ \pm 3;\ \pm 7;\ \pm 3i }[/math];
- ко второй части критерия: [math]\displaystyle{ 1 \pm i;\ 1 \pm 2i;\ 1 \pm 4i;\ 4+5i;\ 2-3i;\ 15+22i }[/math].
Некоторые источники для большей ясности разделяют вторую часть критерия на две[14]:
- Числа, ассоциированные с [math]\displaystyle{ 1+i }[/math]. Их норма равна 2.
- Числа, норма которых есть простое натуральное число вида [math]\displaystyle{ 4n+1 }[/math].
Сам Гаусс такого разделения не делал[15].
Следствия:
- Никакое простое натуральное число вида [math]\displaystyle{ 4n+1 }[/math] не может быть простым гауссовым числом. Простые натуральные числа вида [math]\displaystyle{ 4n+3 }[/math] являются и простыми гауссовыми числами.
- Норма простого гауссова числа является либо простым натуральным числом, либо квадратом простого натурального числа[16].
- Простое натуральное число вида [math]\displaystyle{ 4n+1 }[/math] можно представить как произведение сопряжённых простых гауссовых чисел [math]\displaystyle{ (a+b i)(a-b i) }[/math] или, что то же самое, как сумму квадратов [math]\displaystyle{ a^2+b^2 }[/math]. Этот факт известен как Теорема Ферма — Эйлера. Именно при исследовании данной темы, а также теории биквадратичных вычетов, Гаусс с успехом применил целые комплексные числа. Обратно, если простое натуральное число представимо в виде суммы натуральных квадратов, то в [math]\displaystyle{ \mathbb{Z}[i] }[/math] оно составное и разлагается на два сопряжённых гауссовых простых[17].
- Каждое простое гауссово число является делителем одного и только одного простого натурального числа[17]. Это значит, что разлагая натуральные простые на гауссовы множители, получаются все гауссовы простые.
Разложение на простые множители
В [math]\displaystyle{ \mathbb{Z}[i] }[/math] имеет место аналог основной теоремы арифметики: каждое гауссово число, не являющееся нулём или делителем единицы, разлагается на простые множители, причём это разложение однозначно с точностью до порядка и ассоциированности множителей[1][18].
Пример: [math]\displaystyle{ 5=(1+2i)(1-2i)=(2-i)(2+i) }[/math]. Множители этих двух, по виду разных, разложений попарно ассоциированы: [math]\displaystyle{ 1+2i=i(2-i);\ 1-2i=(-i)(2+i), }[/math] так что однозначность не нарушается.
Чтобы практически разложить гауссово число [math]\displaystyle{ z }[/math] на простые множители, можно использовать приведённое выше свойство: все делители гауссова числа являются также делителями его нормы. При этом норма содержит также «лишние» простые множители, соответствующие сопряжённому к [math]\displaystyle{ z }[/math] числу.
Таким образом, начать следует с разложения нормы числа [math]\displaystyle{ z }[/math] на простые натуральные множители[19].
- Множитель 2, если он присутствует в разложении нормы, разлагается как [math]\displaystyle{ (1+i)(1-i) }[/math]. Следует включить в результирующее разложение те из этих множителей (в соответствующей степени), на которые [math]\displaystyle{ z }[/math] делится нацело.
- Кроме 2, остальные множители нормы — нечётные. Множитель вида [math]\displaystyle{ 4n+3 }[/math] является простым гауссовым числом, поэтому он делит не только норму [math]\displaystyle{ N(z)=~z \overline{z} }[/math], но и само [math]\displaystyle{ z }[/math]. Но тогда этот множитель делит и сопряжённое число [math]\displaystyle{ \overline{z} }[/math]. Отсюда вытекает, что множитель вида [math]\displaystyle{ 4n+3 }[/math] входит в разложение нормы всегда в чётной степени, а в разложение самого [math]\displaystyle{ z }[/math] — в степени, вдвое меньшей.
- Множитель вида [math]\displaystyle{ 4n+1 }[/math] можно разложить на произведение сопряжённых простых гауссовых чисел (или, что то же самое, на сумму квадратов натуральных чисел). И здесь следует делением выяснить, какой из сомножителей относится к исходному числу, а какой — к сопряжённому.
Например, для разложения на простые множители [math]\displaystyle{ 9+12i }[/math] (норма — 225) выделяются простые натуральные множители: [math]\displaystyle{ 225=3^2 \cdot 5^2 }[/math]. По предыдущему, [math]\displaystyle{ 5=(2-i)(2+i) }[/math]. При этом [math]\displaystyle{ 9+12i }[/math] делится только на [math]\displaystyle{ 2+i }[/math] и не делится на [math]\displaystyle{ 2-i }[/math]. Частное от деления [math]\displaystyle{ 9+12i }[/math] на [math]\displaystyle{ 3(2+i) }[/math] равно [math]\displaystyle{ 2+i, }[/math] поэтому окончательный результат:
- [math]\displaystyle{ 9+12i=3\cdot(2+i)^2 }[/math].
Теория сравнений
Сравнения по гауссовому модулю
Понятие сравнения по модулю определяется в [math]\displaystyle{ \mathbb{Z}[i] }[/math] аналогично тому, как это делается для целых чисел[20]:
Пусть [math]\displaystyle{ w }[/math] — некоторое гауссово число. Два гауссовых числа [math]\displaystyle{ u, v }[/math] называются сравнимыми по модулю [math]\displaystyle{ w }[/math], если разность [math]\displaystyle{ u-v }[/math] делится (нацело) на [math]\displaystyle{ w }[/math]. Запись: [math]\displaystyle{ u\equiv v\pmod w }[/math]. |
Свойства сравнений в [math]\displaystyle{ \mathbb{Z}[i] }[/math] в основном такие же, как у целых чисел. Отношение сравнимости есть отношение эквивалентности, поэтому [math]\displaystyle{ \mathbb{Z}[i] }[/math] разбивается на непересекающиеся классы вычетов — каждый такой класс содержит все сравнимые друг с другом (по заданному модулю) гауссовы числа. Для классов, как в случае целых чисел, можно определить сложение и умножение, так что получается кольцо вычетов по гауссову модулю.
Пример. Возьмём в качестве модуля сравнения [math]\displaystyle{ 1+i }[/math]. Тогда [math]\displaystyle{ \mathbb{Z}[i] }[/math] разбивается на два класса вычетов: числа [math]\displaystyle{ a+bi }[/math], у которых [math]\displaystyle{ a,b }[/math] одинаковой чётности, попадут в один класс (содержащий кратные для модуля), а числа с разной чётностью [math]\displaystyle{ a,b }[/math] — в другой.
У гауссова сравнения имеются некоторые особенности. Например, если для целых чисел по модулю 3 существуют 3 класса вычетов с представителями [math]\displaystyle{ 0;\ 1;\ 2, }[/math] то для гауссовых чисел по тому же модулю количество классов значительно больше. Их представители:
- [math]\displaystyle{ 0;\ 1;\ 2;\ i;\ 1 + i;\ 2 + i;\ 2i;\ 1 + 2i;\ 2 + 2i }[/math]
Как обнаружил Гаусс, кольцо вычетов по модулю [math]\displaystyle{ a+bi }[/math] содержит [math]\displaystyle{ N(a+bi)=a^2+b^2 }[/math] элементов[20]. Этот факт вынуждает модифицировать некоторые классические теоремы. Например, малая теорема Ферма для целых чисел утверждает, что [math]\displaystyle{ (a^p-a) }[/math] делится на [math]\displaystyle{ p }[/math] для любого простого [math]\displaystyle{ p }[/math] и натурального [math]\displaystyle{ a }[/math]. Для гауссовых чисел это неверно, даже если ограничиться натуральными значениями [math]\displaystyle{ p }[/math]; например, для целых чисел [math]\displaystyle{ a^3-a }[/math] всегда делится на 3, а для гауссовых [math]\displaystyle{ i^3-i=-2i }[/math], и это значение на 3 не делится. Модифицированный аналог малой теоремы Ферма формулируется следующим образом[20]:
|
На том же примере с [math]\displaystyle{ w=3; u=i }[/math] результат: [math]\displaystyle{ (i^9-i)=0 }[/math] — делится на 3.
Назовём класс вычетов по модулю [math]\displaystyle{ w, }[/math] содержащий число [math]\displaystyle{ u, }[/math] обратимым, если сравнение [math]\displaystyle{ ux \equiv 1\pmod w }[/math] имеет решение относительно [math]\displaystyle{ x }[/math]. Класс обратим тогда и только тогда, когда гауссовы числа [math]\displaystyle{ u }[/math] и [math]\displaystyle{ w }[/math] взаимно просты[20]. В частности, если модуль сравнений [math]\displaystyle{ w }[/math] — гауссово простое число, то каждый ненулевой класс вычетов имеет обратный элемент, а это значит, что классы вычетов по простому модулю в [math]\displaystyle{ \mathbb{Z}[i] }[/math], как и в [math]\displaystyle{ \mathbb{Z}, }[/math] образуют поле.
Функция Эйлера для гауссовых чисел
Введём аналог функции Эйлера для гауссовых чисел. Определение для целых чисел не годится хотя бы потому, что содержащееся в нём выражение «от [math]\displaystyle{ 1 }[/math] до [math]\displaystyle{ n }[/math]» не имеет смысла для комплексных чисел. Новое определение[20]:
Функция Эйлера [math]\displaystyle{ \varphi(z) }[/math] для гауссова числа [math]\displaystyle{ z }[/math] определяется как число обратимых классов вычетов по модулю [math]\displaystyle{ z }[/math]. |
Определённая таким образом функция, как и её прототип для целых чисел, мультипликативна, поэтому достаточно знать её значения для простых чисел и их натуральных степеней. Если [math]\displaystyle{ z }[/math] — простое гауссово число, то[20]:
- [math]\displaystyle{ \varphi(z)=N(z)-1; \quad \varphi(z^k)=N(z)^{k-1}(N(z)-1) }[/math]
Пример: [math]\displaystyle{ \varphi(3+4i) = \varphi((2+i)^2) = N(2+i)(N(2+i)-1) = 5\cdot 4 = 20 }[/math].
Теперь можно обобщить приведённую в предыдущем разделе малую теорему Ферма на случай произвольного (не обязательно простого) модуля сравнения, то есть привести аналог теоремы Эйлера[20]:
Если гауссово число [math]\displaystyle{ z }[/math] взаимно просто с модулем [math]\displaystyle{ w, }[/math], то:
|
Геометрическое представление сравнения по модулю
Рассмотрим для примера сравнения по модулю [math]\displaystyle{ w=1+2i }[/math]. Как сказано в разделе о геометрическом представлении делимости, можно разбить комплексную плоскость на квадраты так, что узлы этой решётки (вершины квадратов) представляют всевозможные комплексные кратные [math]\displaystyle{ 1+2i }[/math]. Тогда, по определению, числа сравнимы по модулю [math]\displaystyle{ w }[/math], если их разность совпадает с одним из узлов решётки кратных.
Каждый квадрат решётки получается из любого другого квадрата сдвигом (переносом) на величину, кратную [math]\displaystyle{ w, }[/math] поэтому разность любой точки квадрата и результата её сдвига тоже кратна [math]\displaystyle{ w }[/math]. Отсюда следует окончательный вывод[20]:
Гауссовы числа сравнимы по модулю [math]\displaystyle{ w }[/math] тогда и только тогда, когда они занимают одно и то же относительное положение в своих квадратах решётки кратных. |
Например, сравнимы все центры квадратов, или все середины их соответствующих сторон и т. п.
Деление с остатком
Определение
В кольце [math]\displaystyle{ \mathbb{Z}[i] }[/math] можно определить деление с остатком (на любое ненулевое гауссово число), потребовав, чтобы норма остатка была меньше нормы делителя[21]:
Любое гауссово число [math]\displaystyle{ u }[/math] можно разделить с остатком на любое ненулевое гауссово число [math]\displaystyle{ v }[/math], то есть представить в виде:
где частное [math]\displaystyle{ q }[/math] и остаток [math]\displaystyle{ r }[/math] — гауссовы числа, причём [math]\displaystyle{ N(r)\lt N(v) }[/math]. |
Несложно показать, что в качестве частного от деления с остатком можно взять гауссово число, ближайшее к частному от обычного деления комплексных чисел[22].
Необходимо отметить, что условия «норма остатка меньше нормы делителя» недостаточно для того, чтобы гарантировать однозначность остатка от деления, поэтому в [math]\displaystyle{ \mathbb{Z}[i] }[/math] остаток неоднозначен. Например, [math]\displaystyle{ 7+2i }[/math] можно разделить на [math]\displaystyle{ 3-i }[/math] тремя способами:
- [math]\displaystyle{ 7+2i = (3-i)(2+i)+i = (3-i)(1+i)+3 = (3-i)(2+2i)+(-1-2i) }[/math]
Можно гарантировать только то, что все остатки попадают в один класс вычетов по модулю делителя. Впрочем, похожая ситуация имеет место и для обычных целых чисел — например, разделить с остатком 8 на 3 можно двумя способами: [math]\displaystyle{ 8=3\cdot 2 + 2 }[/math] или [math]\displaystyle{ 8=3\cdot 3 - 1 }[/math] (оба остатка по модулю меньше делителя) поэтому в арифметике целых чисел введено дополнительное условие, обеспечивающее однозначность операции: остаток должен быть неотрицательным.
Пример. Для деления с остатком [math]\displaystyle{ 11+10i }[/math] на [math]\displaystyle{ 4+i }[/math] вначале находится частное от обычного комплексного деления:
- [math]\displaystyle{ \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]\displaystyle{ 3+2i, }[/math] тогда остаток равен [math]\displaystyle{ 11+10i - (4+i)(3+2i) = 1-i }[/math]. В итоге:
- [math]\displaystyle{ 11+10i = (4+i)(3+2i) + 1-i }[/math]
Для гауссовых чисел имеет место аналог китайской теоремы об остатках, поскольку она доказывается с помощью алгоритма Евклида.
Геометрическое представление
Из определения деления с остатком [math]\displaystyle{ u }[/math] на [math]\displaystyle{ v }[/math] следует, что [math]\displaystyle{ |r|=|u-vq| }[/math], то есть модуль остатка есть расстояние между комплексными числами [math]\displaystyle{ u }[/math] и [math]\displaystyle{ vq }[/math]. Другими словами, [math]\displaystyle{ |r| }[/math] есть расстояние от делимого до одного из узлов [math]\displaystyle{ v }[/math]-решётки кратных. Требование «норма остатка меньше нормы делителя» эквивалентно условию [math]\displaystyle{ |r|\lt |v| }[/math]. Отсюда вытекает:
Деление с остатком [math]\displaystyle{ u }[/math] на [math]\displaystyle{ v }[/math] имеет столько решений, сколько узлов [math]\displaystyle{ v }[/math]-решётки кратных находится от делимого на расстоянии меньше [math]\displaystyle{ |v| }[/math]. |
В вышеприведённом примере деления [math]\displaystyle{ 7+2i }[/math] на [math]\displaystyle{ 3-i }[/math] ближайшими к делимому являются кратные делителя, образующие вершины квадрата решётки, содержащего делимое:
- [math]\displaystyle{ 7+i=(3-i)(2+i) }[/math]
- [math]\displaystyle{ 4+2i=(3-i)(1+i) }[/math]
- [math]\displaystyle{ 8+4i=(3-i)(2+2i) }[/math]
Все они находятся от делимого на расстоянии меньше, чем [math]\displaystyle{ |v|=\sqrt{10} }[/math]. Четвёртая вершина квадрата [math]\displaystyle{ 5+5i }[/math] удалена от делимого больше чем на [math]\displaystyle{ \sqrt{10} }[/math]. Поэтому данная задача деления с остатком имеет три решения.
В общем случае, проведя из вершин квадрата [math]\displaystyle{ v }[/math]-решётки кратных дуги радиусом [math]\displaystyle{ |v|, }[/math] мы получим фигуру, показанную на рисунке. Если делимое находится в центральной области (красная зона), оно удалено от всех вершин менее чем на [math]\displaystyle{ |v|, }[/math] и деление с остатком может быть выполнено четырьмя способами. Если делимое находится в одном из «лепестков» (синяя зона), то одна из вершин отпадает, и число решений равно трём. Для белой зоны получаем два решения. Наконец, если делимое совпадает с одной из вершин, то остаток равен нулю, и решение единственно.
Наибольший общий делитель
Кольцо гауссовых чисел является евклидовым, и в нём всегда можно определить наибольший общий делитель, определённый однозначно с точностью до делителей единицы[23].
Наибольшим общим делителем НОД[math]\displaystyle{ (u, v) }[/math] для гауссовых чисел [math]\displaystyle{ u }[/math] и [math]\displaystyle{ v }[/math], хотя бы одно из которых ненулевое, называется их общий делитель, который делится на любой другой общий делитель [math]\displaystyle{ u }[/math] и [math]\displaystyle{ v }[/math]. |
Эквивалентное определение: НОД[math]\displaystyle{ (u, v) }[/math] есть тот общий делитель [math]\displaystyle{ u, v }[/math], у которого норма максимальна[24].
- Свойства НОД
- Если известен некоторый НОД, то любое из трёх чисел, ассоциированных с ним, также будет НОД. В частности. если один из НОД — делитель единицы, то такими же будут и остальные три НОД.
- Гауссовы числа взаимно просты тогда и только тогда, когда их НОД есть делитель единицы.
- Имеет место аналог соотношения Безу[25]:
Пусть [math]\displaystyle{ u, v }[/math] — гауссовы числа, и хотя бы одно из них не нуль. Тогда существуют такие гауссовы числа [math]\displaystyle{ x, y }[/math], что выполняется соотношение:
|
- Другими словами, наибольший общий делитель двух гауссовых чисел можно всегда представить как линейную комбинацию этих чисел с гауссовыми коэффициентами.
- Следствие соотношения Безу[25]: если гауссовы числа [math]\displaystyle{ u, v }[/math] взаимно просты, то уравнение [math]\displaystyle{ xu + yv = 1 }[/math] относительно [math]\displaystyle{ x, y }[/math] имеет решение в [math]\displaystyle{ \mathbb{Z}[i] }[/math]. Вместо 1 в приведённом уравнении может стоять любой другой делитель единицы, теорема при этом останется верной.
Алгоритм Евклида и практическое вычисление НОД
Для определения НОД в [math]\displaystyle{ \mathbb{Z}[i] }[/math] удобно использовать алгоритм Евклида, вполне аналогичный применяемому для целых чисел. НОД получается в этой схеме как последний ненулевой остаток[26]. Алгоритм Евклида можно также использовать для нахождения коэффициентов [math]\displaystyle{ x, y }[/math] в соотношении Безу[20].
Пример 1. Найдём НОД для [math]\displaystyle{ 32+9i }[/math] и [math]\displaystyle{ 4+11i }[/math].
- Шаг 1: [math]\displaystyle{ 32+9i = (4+11i) (2-2i) + 2-5i }[/math] (разделили с остатком первое число на второе)
- Шаг 2: [math]\displaystyle{ 4+11i = (2-5i) (-2+i) + 3-i }[/math] (разделили с остатком предыдущий делитель на остаток предыдущего шага)
- Шаг 3: [math]\displaystyle{ 2-5i = (3-i) (1-i) -i }[/math] (то же действие)
- Шаг 4: [math]\displaystyle{ 3-i = (-i) (1+3i) }[/math] (то же действие, деление выполнилось нацело)
Отметим, что на каждом шаге норма остатка монотонно уменьшается. Последний ненулевой остаток равен [math]\displaystyle{ -i }[/math], это делитель единицы, поэтому заключаем, что исследуемые числа взаимно просты.
Пример 2. Найдём НОД для [math]\displaystyle{ 11+3i }[/math] и [math]\displaystyle{ 1+8i }[/math].
- Шаг 1: [math]\displaystyle{ 11+3i = (1+8i) (1-i) +2-4i }[/math]
- Шаг 2: [math]\displaystyle{ 1+8i = (2-4i) (-1+i) +(-1+2i) }[/math]
- Шаг 3: [math]\displaystyle{ 2-4i = (-1+2i) (-2) }[/math] (деление выполнилось нацело)
Последний ненулевой остаток равен [math]\displaystyle{ -1+2i }[/math], это и есть искомый НОД. Последовательно подставляя вместо левых частей равенств правые (начиная с предпоследнего равенства, снизу вверх), получается соотношение Безу для НОД:
- [math]\displaystyle{ -1+2i = (11+3i)(1-i) + (1+8i)(1+2i) }[/math]
Некоторые приложения
Гаусс использовал открытую им алгебраическую структуру для глубокого исследования биквадратичных вычетов. Можно указать и другие области успешного применения гауссовых чисел[27]. Примечательно, что значительная их часть относится к теории не комплексных, а натуральных чисел.
Разложение натуральных чисел на сумму двух квадратов
Из критерия Гаусса[math]\displaystyle{ 4n+1 }[/math] можно представить в виде суммы квадратов двух натуральных чисел, причём единственным способом. Пример: [math]\displaystyle{ 29=(2+5i)(2-5i)=2^2+5^2 }[/math].
вытекает, что простое натуральное число видаРазложение натуральных чисел другого вида не всегда возможно — например, [math]\displaystyle{ 15; 19; 27; 103 }[/math] и другие числа вида [math]\displaystyle{ 4n+3 }[/math] нельзя представить в виде суммы квадратов двух натуральных чисел. Составные числа могут также иметь более одного варианта разложения, например[27]: [math]\displaystyle{ 65=4^2+7^2=1^2+8^2 }[/math]. Общая теорема: натуральное число представимо в виде суммы двух квадратов тогда и только тогда, когда в его каноническом разложении все простые множители вида [math]\displaystyle{ 4n+3 }[/math] входят в чётных степенях[17].
Пример: [math]\displaystyle{ 21=3\cdot 7 }[/math] нельзя представить в виде суммы квадратов, потому что число 3 (как и 7) входит в него с нечётной степенью. Но [math]\displaystyle{ 245=5\cdot 7^2 }[/math] представить можно: [math]\displaystyle{ 245=7^2+14^2 }[/math].
Подсчёт числа представлений в виде суммы двух квадратов
Число представлений [math]\displaystyle{ \rho(m) }[/math] натурального числа [math]\displaystyle{ m }[/math] в виде суммы квадратов (или, что то же самое, число гауссовых чисел с нормой [math]\displaystyle{ m }[/math]) можно определить следующим образом[28]. Разложим [math]\displaystyle{ m }[/math] на простые натуральные множители:
- [math]\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} }[/math]
Здесь [math]\displaystyle{ p_i }[/math] — множители вида [math]\displaystyle{ 4n+1, }[/math] а [math]\displaystyle{ q_j }[/math] — множители вида [math]\displaystyle{ 4n+3 }[/math]. Тогда возможны 3 случая.
- Если хотя бы один показатель степени [math]\displaystyle{ \mu_j }[/math] нечётный, число [math]\displaystyle{ m }[/math] не может быть представлено в виде суммы квадратов.
- Пусть все [math]\displaystyle{ \mu_j }[/math] чётные. Окончательная формула зависит от чётности [math]\displaystyle{ \lambda_i }[/math]. Если все они тоже чётные, то формула имеет вид:
- [math]\displaystyle{ \rho(m)=\frac{1}{2} [(\lambda_1+1) (\lambda_2+1) \cdots (\lambda_r+1) + 1 ] }[/math]
- Если не все [math]\displaystyle{ \lambda_i }[/math] чётные, то формула немного отличается:
- [math]\displaystyle{ \rho(m)=\frac{1}{2} (\lambda_1+1) (\lambda_2+1) \cdots (\lambda_r+1) }[/math]
Теория пифагоровых троек
Пифагорова тройка — это одно из целочисленных решений уравнения:
- [math]\displaystyle{ x^2+y^2=z^2 }[/math].
Общее решение уравнения зависит от двух целых параметров [math]\displaystyle{ m,n }[/math]:
- [math]\displaystyle{ x=m^2-n^2; \; y=2mn; \; z=m^2+n^2 }[/math].
Для генерации пифагоровых троек можно использовать такой приём. Пусть [math]\displaystyle{ z=a+bi }[/math] — произвольное гауссово число, у которого обе компоненты [math]\displaystyle{ a,b }[/math] ненулевые. Возведя это число в квадрат, получается некоторое другое гауссово число [math]\displaystyle{ c+di }[/math]. Тогда тройка [math]\displaystyle{ \{|c|; |d|; N(z)\} }[/math] будет пифагоровой[27].
Пример: для исходного числа [math]\displaystyle{ z=17+12i }[/math] получается пифагорова тройка [math]\displaystyle{ (145; 408; 433) }[/math].
Решение диофантовых уравнений
Решение многих диофантовых уравнений удаётся найти, если привлечь аппарат гауссовых чисел. Например, для уравнения [math]\displaystyle{ x^2+y^2=2z^2 }[/math] несложные преобразования дают два типа целых взаимно простых решений[29], зависящих от целых параметров [math]\displaystyle{ a,b }[/math]:
- [math]\displaystyle{ x=a^2-2ab-b^2; \; y=a^2+2ab-b^2 }[/math]
- [math]\displaystyle{ x=-a^2-2ab+b^2; \; y=a^2-2ab-b^2 }[/math]
В 1850 году Виктор Лебег, используя гауссовы числа, исследовал уравнение [math]\displaystyle{ x^2+1=y^n }[/math] и доказал его неразрешимость в натуральных числах. Другими словами, среди натуральных чисел вида [math]\displaystyle{ n^2+1 }[/math] нет ни одного полного куба или иной степени выше второй[27].
Нерешённые проблемы
- Найти количество гауссовых чисел, норма которых меньше заданной натуральной константы [math]\displaystyle{ R }[/math]. В эквивалентной формулировке эта тема известна как «проблема круга Гаусса» в геометрии чисел[30][31].
- Найти прямые на комплексной плоскости, содержащие бесконечно много простых гауссовых чисел. Две такие прямые очевидны — это координатные оси; неизвестно, существуют ли другие[32].
- Вопрос, известный под названием «ров Гаусса»: можно ли дойти до бесконечности, переходя от одного простого гауссова числа к другому скачками заранее ограниченной длины? Задача поставлена в 1962 году и до сих пор не решена[33].
Вариации и обобщения
Ещё одним исторически важным евклидовым кольцом, похожим по свойствам на целые числа, стали «целые числа Эйзенштейна».
Гауссовы рациональные числа, обозначаемые [math]\displaystyle{ \mathbb Q(i) }[/math] — это комплексные числа вида [math]\displaystyle{ a+bi }[/math], где [math]\displaystyle{ a, b }[/math] — рациональные числа. Это множество замкнуто относительно всех 4 арифметических операций, включая деление, и поэтому является полем, расширяющим кольцо гауссовых чисел.
История
В 1820-х годах Карл Фридрих Гаусс исследовал биквадратичный закон взаимности, результатом стала монография «Теория биквадратичных вычетов» (1828—1832). Именно в этом труде целые комплексные числа доказали свою полезность для решения задач теории чисел, хотя формулировка этих задач никак не связана с комплексными числами. Гаусс писал, что «естественный источник общей теории следует искать в расширении области арифметики»[3].
В книге Гаусса было показано, что новые числа по своим свойствам во многом напоминают обычные целые числа. Автор описал четыре делителя единицы, определил отношение ассоциированности, понятие простого числа, дал критерий простоты и доказал аналоги основной теоремы арифметики, малой теоремы Ферма. Далее Гаусс подробно рассмотрел вычеты по комплексному модулю, индексы и первообразные корни. Главным достижением построенной теории стал биквадратичный закон взаимности, который Гаусс обещал доказать в следующем томе; этот том так и не был опубликован, но в рукописях Гаусса была обнаружена подробная схема строгого доказательства[3].
Гаусс использовал введённые им числа также и в других своих трудах, например, по алгебраическим уравнениям[34]. Идеи Гаусса были развиты в трудах Карла Густава Якоба Якоби и Фердинанда Готтхольда Эйзенштейна. В середине XIX века Эйзенштейн, Дирихле и Эрмит ввели и исследовали обобщённое понятие целого алгебраического числа.
Кольцо гауссовых целых чисел было одним из первых примеров алгебраической структуры с непривычными свойствами. Со временем было открыто большое количество структур такого типа, а в конце XIX века появилась абстрактная алгебра, изучающая алгебраические свойства отдельно от объектов-носителей этих свойств.
Примечания
- ↑ 1,0 1,1 Математическая энциклопедия, 1977.
- ↑ Гаусс К. Ф., 1959, с. 655—754.
- ↑ 3,0 3,1 3,2 Математика XIX века. Том I: Математическая логика, алгебра, теория чисел, теория вероятностей, 1978, с. 88—92.
- ↑ Кузьмин Р. О., Фаддеев Д. К., 1939, с. 146.
- ↑ Айерлэнд К., Роузен М., 1987, с. 23.
- ↑ Окунев Л. Я., 1941, с. 27—28.
- ↑ 7,0 7,1 7,2 7,3 Кузьмин Р. О., Фаддеев Д. К., 1939, с. 147—149.
- ↑ 8,0 8,1 8,2 Окунев Л. Я., 1941, с. 29.
- ↑ Окунев Л. Я., 1941, с. 32.
- ↑ Кузьмин Р. О., Фаддеев Д. К., 1939, с. 150.
- ↑ 11,0 11,1 Кузьмин Р. О., Фаддеев Д. К., 1939, с. 155.
- ↑ Кузьмин Р. О., Фаддеев Д. К., 1939, с. 156.
- ↑ Окунев Л. Я., 1941, с. 41, 44.
- ↑ A classification of gaussian primes, с. 10.
- ↑ Гаусс К. Ф., 1959, с. 698.
- ↑ Кузьмин Р. О., Фаддеев Д. К., 1939, с. 158.
- ↑ 17,0 17,1 17,2 Conrad, Keith, Глава 9.
- ↑ Окунев Л. Я., 1941, с. 33—34.
- ↑ Conrad, Keith, Глава 6.
- ↑ 20,0 20,1 20,2 20,3 20,4 20,5 20,6 20,7 20,8 Conrad, Keith, Глава 7.
- ↑ Conrad, Keith, Глава 3.
- ↑ Окунев Л. Я., 1941, с. 30—31.
- ↑ Окунев Л. Я., 1941, с. 35—36.
- ↑ Conrad, Keith, Глава 4.
- ↑ 25,0 25,1 Conrad, Keith, Глава 5.
- ↑ Кузьмин Р. О., Фаддеев Д. К., 1939, с. 153—155.
- ↑ 27,0 27,1 27,2 27,3 Conrad, Keith, Глава 8.
- ↑ Кузьмин Р. О., Фаддеев Д. К., 1939, с. 164—166.
- ↑ Кузьмин Р. О., Фаддеев Д. К., 1939, с. 162—163.
- ↑ Conway J. H., Sloane N. J. A. Sphere Packings, Lattices and Groups. — Springer-Verlag. — P. 106.
- ↑ последовательность A000328 в OEIS
- ↑ 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.
- ↑ Guy Richard K. Unsolved problems in number theory. — 3rd ed. — New York: Springer, 2004. — P. 55—57. — ISBN 978-0-387-20860-2.
- ↑ 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.