Русская Википедия:Факторизация гауссовых чисел
Факторизация гауссовых чисел — разложение целых гауссовых чисел на простые гауссовы множители.
Предварительные замечания
Особенность делимости в кольце гауссовых чисел <math>\mathbb{Z}[i],</math> отличающая её от делимости натуральных чисел: кольцо <math>\mathbb{Z}[i]</math> содержит четыре делителя единицы <math>(1;\ -1;\ i;\ -i),</math> норма которых (квадрат комплексного модуля) равна 1. Два гауссовых числа называются ассоциированными, если одно получается из другого умножением на делитель единицы. Легко видеть, что ассоциированность — отношение эквивалентностиШаблон:Sfn. Пример: гауссовы числа <math>1+i</math> и <math>1-i</math> ассоциированы, поскольку:
- <math>1+i = i(1-i)</math>.
У каждого ненулевого гауссова числа есть три ассоциированных с ним, и делители у них у всех совпадают. Все делители чисел также определены с точностью до ассоциированности.
Для гауссовых чисел имеет место аналог основной теоремы арифметики: каждое гауссово число, не являющееся нулём или делителем единицы, разлагается на простые множители, причём это разложение однозначно с точностью до порядка и ассоциированности множителейШаблон: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> числу.
Таким образом, начать следует с разложения нормы числа <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>.
Таблица разложения гауссовых чисел с нормой до 1000
Соглашения
Данная таблица показывает для всех гауссовых чисел с нормой от 2 до 1000, является ли это число простым гауссовым. Если да, то такое число помечено в таблице кодом: Шаблон:Oncolor, а если нет, то приводится его разложение на простые гауссовы множители. Отметим, что простое натуральное число не обязано быть простым гауссовым числом; например, числа 2 и 5 как гауссовы числа не являются простыми: <math>2 = (1+i)(1-i);\quad 5 = (2+i)(2-i).</math>
В первой колонке таблицы — норма гауссова числа (не всякое натуральное число может быть нормой гауссова числа). Во второй — числа, имеющие эту норму, с точностью до ассоциированности — из 4 чисел, ассоциированных с числом x: (<math>x,-x,ix,-ix</math>) в таблице представлено одно, у которого вещественная часть положительна, а мнимая — неотрицательна. Например, во второй строке таблицы разложение числа <math>2</math> охватывает также разложения <math>-2;\ 2i; -2i.</math>
Каждое разложение, показанное в строке таблицы, имеет ещё по крайней мере три варианта, получаемых заменой простых множителей на ассоциированные с ними. Пример:
- <math>1+3i = (1+i)(2+i) = i(1-i)(2+i) = -i(1+i)(-1+2i) = \dots</math>
Поэтому принято следующее соглашение: из 4 вариаций каждого простого множителя представлена та, что находится в правой полуплоскости комплексной плоскости, и у которой абсолютное значение вещественной части не меньше, чем абсолютное значение мнимой части.
Гауссовы числа упорядочены по возрастанию их нормы (Шаблон:OEIS). Не всякое натуральное число может быть гауссовой нормой (см. Шаблон:OEIS2C, Шаблон:OEIS2C и Шаблон:OEIS2C).
Таблица факторизации
См. также
Примечания
Литература
Ссылки
