Факторизация гауссовых чисел
Факторизация гауссовых чисел — разложение целых гауссовых чисел на простые гауссовы множители.
Предварительные замечания
Особенность делимости в кольце гауссовых чисел Z [ i ] , {displaystyle mathbb {Z} [i],} отличающая её от делимости натуральных чисел: кольцо Z [ i ] {displaystyle mathbb {Z} [i]} содержит четыре делителя единицы ( 1 ; − 1 ; i ; − i ) , {displaystyle (1; -1; i; -i),} норма которых (квадрат комплексного модуля) равна 1. Два гауссовых числа называются ассоциированными, если одно получается из другого умножением на делитель единицы. Легко видеть, что ассоциированность — отношение эквивалентности. Пример: гауссовы числа 1 + i {displaystyle 1+i} и 1 − i {displaystyle 1-i} ассоциированы, поскольку:
1 + i = i ( 1 − i ) {displaystyle 1+i=i(1-i)} .У каждого ненулевого гауссова числа есть три ассоциированных с ним, и делители у них у всех совпадают. Все делители чисел также определены с точностью до ассоциированности.
Для гауссовых чисел имеет место аналог основной теоремы арифметики: каждое гауссово число, не являющееся нулём или делителем единицы, разлагается на простые множители, причём это разложение однозначно с точностью до порядка и ассоциированности множителей.
Пример: 5 = ( 1 + 2 i ) ( 1 − 2 i ) = ( 2 − i ) ( 2 + i ) {displaystyle 5=(1+2i)(1-2i)=(2-i)(2+i)} . Множители этих двух, по виду разных, разложений попарно ассоциированы: 1 + 2 i = i ( 2 − i ) ; 1 − 2 i = ( − i ) ( 2 + i ) , {displaystyle 1+2i=i(2-i); 1-2i=(-i)(2+i),} так что однозначность не нарушается.
Алгоритм разложения гауссового числа на простые множители
Чтобы практически разложить гауссово число z {displaystyle z} на простые множители, можно использовать следующее их свойство: все делители гауссова числа z {displaystyle z} являются также делителями его нормы. При этом норма содержит также «лишние» простые множители, соответствующие сопряжённому к z {displaystyle z} числу.
Таким образом, начать следует с разложения нормы числа z {displaystyle z} на простые натуральные множители.
Например, для разложения на простые множители 9 + 12 i {displaystyle 9+12i} (норма — 225) выделяются простые натуральные множители: 225 = 3 2 ⋅ 5 2 {displaystyle 225=3^{2}cdot 5^{2}} . По предыдущему, 5 = ( 2 − i ) ( 2 + i ) {displaystyle 5=(2-i)(2+i)} . При этом 9 + 12 i {displaystyle 9+12i} делится только на 2 + i {displaystyle 2+i} и не делится на 2 − i {displaystyle 2-i} . Частное от деления 9 + 12 i {displaystyle 9+12i} на 3 ( 2 + i ) {displaystyle 3(2+i)} равно 2 + i , {displaystyle 2+i,} поэтому окончательный результат:
9 + 12 i = 3 ⋅ ( 2 + i ) 2 {displaystyle 9+12i=3cdot (2+i)^{2}} .Таблица разложения гауссовых чисел с нормой до 1000
Соглашения
Данная таблица показывает для всех гауссовых чисел с нормой от 2 до 1000, является ли это число простым гауссовым. Если да, то такое число помечено в таблице кодом: простое, а если нет, то приводится его разложение на простые гауссовы множители. Отметим, что простое натуральное число не обязано быть простым гауссовым числом; например, числа 2 и 5 как гауссовы числа не являются простыми: 2 = ( 1 + i ) ( 1 − i ) ; 5 = ( 2 + i ) ( 2 − i ) . {displaystyle 2=(1+i)(1-i);quad 5=(2+i)(2-i).}
В первой колонке таблицы — норма гауссова числа (не всякое натуральное число может быть нормой гауссова числа). Во второй — числа, имеющие эту норму, с точностью до ассоциированности — из 4 чисел, ассоциированных с числом x: ( x , − x , i x , − i x {displaystyle x,-x,ix,-ix} ) в таблице представлено одно, у которого вещественная часть положительна, а мнимая — неотрицательна. Например, во второй строке таблицы разложение числа 2 {displaystyle 2} охватывает также разложения − 2 ; 2 i ; − 2 i . {displaystyle -2; 2i;-2i.}
Каждое разложение, показанное в строке таблицы, имеет ещё по крайней мере три варианта, получаемых заменой простых множителей на ассоциированные с ними. Пример:
1 + 3 i = ( 1 + i ) ( 2 + i ) = i ( 1 − i ) ( 2 + i ) = − i ( 1 + i ) ( − 1 + 2 i ) = … {displaystyle 1+3i=(1+i)(2+i)=i(1-i)(2+i)=-i(1+i)(-1+2i)=dots }Поэтому принято следующее соглашение: из 4 вариаций каждого простого множителя представлена та, что находится в правой полуплоскости комплексной плоскости, и у которой абсолютное значение вещественной части не меньше, чем абсолютное значение мнимой части.
Гауссовы числа упорядочены по возрастанию их нормы (последовательность A001481 в OEIS). Не всякое натуральное число может быть гауссовой нормой (см. A055025, A103431 и A103432).