Факторизация гауссовых чисел


Факторизация гауссовых чисел — разложение целых гауссовых чисел на простые гауссовы множители.

Предварительные замечания

Особенность делимости в кольце гауссовых чисел 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} на простые натуральные множители.

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

    Таблица факторизации