Гауссовское целое число - Gaussian integer

В теории чисел , Gaussian целое представляет собой комплексное число , действительные и мнимые части являются целыми числами . Гауссовские целые числа, с обычным добавлением и умножения на комплексные числа , образуют область целостности , как правило , записывается в виде Z [ я ] . Эта область целостности является частным случаем коммутативного кольца из квадратичных целых . В нем нет полного упорядочивания, которое бы соответствовало арифметике.

Целые гауссовы числа как точки решетки на комплексной плоскости

Основные определения

Целые числа Гаусса - это множество

Другими словами, гауссовское целое число - это комплексное число , у которого действительная и мнимая части являются целыми числами . Поскольку гауссовские целые числа замкнуты относительно сложения и умножения, они образуют коммутативное кольцо , которое является подкольцом поля комплексных чисел. Таким образом, это целостная область .

Если рассматривать в комплексной плоскости , гауссовы целые числа составляют 2- мерную целочисленную решетку .

Конъюгат гауссовского целого числа в + би является гауссами целочисленным - би .

Норма гауссовского целого является продуктом с его конъюгату.

Норма гауссовского целого числа, таким образом, представляет собой квадрат его абсолютного значения как комплексного числа. Норма гауссовского целого числа - неотрицательное целое число, которое представляет собой сумму двух квадратов . Таким образом, норма не может иметь вид 4 k + 3 с целым числом k .

Норма мультипликативна , то есть

для каждой пары целых гауссовских чисел z , w . Это можно показать напрямую или с помощью мультипликативного свойства модуля комплексных чисел.

В единицы кольца гауссовых целых чисел (то есть гауссовы целые числа, мультипликативный обратный также гауссово целое число) в точности гауссовы целые числа с нормой 1, то есть, 1, -1, я и - я .

Евклидово деление

Визуализация максимального расстояния до некоторого гауссовского целого числа

Гауссовские целые числа имеют евклидово деление (деление с остатком), подобное делению целых чисел и многочленов . Это делает гауссовские целые числа евклидовой областью и подразумевает, что гауссовские целые числа разделяют с целыми числами и многочленами многие важные свойства, такие как существование евклидова алгоритма для вычисления наибольших общих делителей , тождество Безу , свойство главного идеала , лемма Евклида , уникальная факторизация Теорема и китайская теорема об остатках , все из которых можно доказать, используя только евклидово деление.

Алгоритм евклидова деления берет в кольце гауссовских целых чисел делимое a и делитель b 0 и производит частное q и остаток r такие, что

Фактически, можно уменьшить остаток:

Даже при этом лучшем неравенстве частное и остаток не обязательно уникальны, но можно уточнить выбор, чтобы гарантировать уникальность.

Чтобы доказать это, можно рассмотреть частное комплексных чисел x + iy = а/б. Существуют уникальные целые числа m и n такие, что -1/2< х - м1/2и -1/2< у - п1/2, а значит, N ( x - m + i ( y - n )) ≤1/2. Взяв q = m + in , имеем

с участием

а также

Выбор x - m и y - n в полуоткрытом интервале необходим для уникальности. Это определение евклидова деления можно интерпретировать геометрически в комплексной плоскости (см. Рисунок), отметив, что расстояние от комплексного числа ξ до ближайшего гауссовского целого числа не превышает2/2.

Основные идеалы

Поскольку кольцо G целых гауссовских чисел является евклидовой областью, G является областью главных идеалов , что означает, что каждый идеал группы G является главным . Явный, идеал я это подмножество кольца R такой , что каждая сумма элементов I и каждый продукт элемента I на элемент из R принадлежит I . Идеал является главным , если он состоит из всех кратных одного элемента g , то есть имеет вид

В этом случае говорят , что идеал генерируется с помощью г или , что г является генератором идеала.

Каждый идеал I в кольце целых гауссовских чисел является главным, потому что, если выбрать в I ненулевой элемент g минимальной нормы для каждого элемента x из I , остаток от евклидова деления x на g также принадлежит I и имеет норма меньше, чем у g ; из-за выбора g эта норма равна нулю, и, следовательно, остаток также равен нулю. То есть x = qg , где q - частное.

Для любого г , идеал , порожденный г также порождается любым ассоциированным с г , то есть, например , г , - г , - Г ; никакой другой элемент не порождает такого же идеала. Поскольку все образующие идеала имеют одну и ту же норму, норма идеала - это норма любого из его образующих.

В некоторых случаях полезно раз и навсегда выбрать генератор для каждого идеала. Есть два классических способа сделать это, и оба рассматривают сначала идеалы нечетной нормы. Если g = a + bi имеет нечетную норму a 2 + b 2 , то один из a и b нечетный, а другой четный. Таким образом, g имеет ровно один ассоциированный элемент с нечетной и положительной действительной частью a . В своей оригинальной статье Гаусс сделал другой выбор, выбрав единственного ассоциированного члена так, что остаток от его деления на 2 + 2 i равен единице. Фактически, поскольку N (2 + 2 i ) = 8 , норма остатка не больше 4. Поскольку эта норма нечетная, а 3 не является нормой гауссовского целого числа, норма остатка равна единице, то есть остаток - это единица. Умножая g на величину, обратную этой единице, можно найти ассоциата, который имеет единицу в качестве остатка при делении на 2 + 2 i .

Если норма g четная, то либо g = 2 k h, либо g = 2 k h (1 + i ) , где k - натуральное число, а N ( h ) - нечетное. Таким образом, выбирается ассоциат g для получения h, который соответствует выбору ассоциатов для элементов нечетной нормы.

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

Поскольку гауссовские целые числа образуют область главного идеала, они также образуют уникальную область факторизации . Это означает, что гауссовское целое число неприводимо (то есть не является произведением двух неединиц ) тогда и только тогда, когда оно простое (то есть порождает простой идеал ).

В простые элементы из Z [ я ] также известны как гауссовых простых чисел . Ассоциированный элемент гауссовского простого числа также является гауссовским простым числом. Сопряжение гауссовского простого числа также является гауссовским простым числом (это означает, что гауссовские простые числа симметричны относительно действительной и мнимой осей).

Положительное целое число является гауссовским простым числом тогда и только тогда, когда это простое число , сравнимое с 3 по модулю 4 (то есть может быть записано 4 n + 3 , где n неотрицательное целое число) (последовательность A002145 в OEIS ). Остальные простые числа не являются гауссовскими простыми числами, но каждое из них является произведением двух сопряженных гауссовских простых чисел.

Гауссовское целое число a + bi является гауссовским простым числом тогда и только тогда, когда:

  • одно из a , b равно нулю, а абсолютное значение другого - простое число в форме 4 n + 3 (где n неотрицательное целое число), или
  • оба отличны от нуля, и a 2 + b 2 является простым числом (которое не будет иметь форму 4 n + 3 ).

Другими словами, гауссовское целое число является гауссовским простым числом тогда и только тогда, когда либо его норма является простым числом, либо оно является произведением единицы ( ± 1, ± i ) и простого числа формы 4 n + 3 .

Отсюда следует, что существует три случая факторизации простого числа p в целых гауссовских числах:

  • Если p сравнимо с 3 по модулю 4, то это простое число Гаусса; на языке теории алгебраических чисел , р называется инертен в гауссовых целых числах.
  • Если p сравнимо с 1 по модулю 4, то это произведение гауссовского простого числа на его сопряженное, оба из которых являются несвязанными гауссовскими простыми числами (ни одно из них не является произведением другого на единицу); p называется разложенным простым числом в целых гауссовских числах. Например, 5 = (2 + i ) (2 - i ) и 13 = (3 + 2 i ) (3 - 2 i ) .
  • Если p = 2 , имеем 2 = (1 + i ) (1 - i ) = i (1 - i ) 2 ; то есть 2 - произведение квадрата гауссовского простого числа на единицу; это единственное разветвленное простое число в гауссовых целых числах.

Уникальная факторизация

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

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

где u - единица (то есть u ∈ {1, –1, i , - i } ), e 0 и k - неотрицательные целые числа, e 1 ,…, e k - положительные целые числа, а p 1 ,…, p k - различные гауссовские простые числа, такие, что, в зависимости от выбора выбранных ассоциатов,

  • либо р к = а K + IB K с нечетным и положительным, и б даже,
  • или остаток от евклидова деления p k на 2 + 2 i равен 1 (это первоначальный выбор Гаусса).

Преимущество второго выбора состоит в том, что выбранные партнеры хорошо себя ведут под произведениями для гауссовских целых чисел нечетной нормы. С другой стороны, выбранный ассоциированный элемент для вещественных гауссовских простых чисел - отрицательные целые числа. Например, факторизация 231 в целых числах и при первом выборе ассоциатов составляет 3 × 7 × 11 , в то время как это (–1) × (–3) × (–7) × (–11) со вторым выбор.

Гауссовские рациональные числа

Поле из гауссовых рациональных чисел является полем частных кольца гауссовых целых чисел. Он состоит из комплексных чисел, действительная и мнимая части которых рациональны .

Кольцо гауссовских целых чисел является целым замыканием целых чисел в гауссовских рациональных числах.

Это означает, что гауссовские целые числа являются квадратичными целыми числами и что гауссовское рациональное число является гауссовским целым числом тогда и только тогда, когда оно является решением уравнения

с целыми числами c и d . Фактически a + bi является решением уравнения

и это уравнение имеет целые коэффициенты тогда и только тогда, когда a и b оба являются целыми числами.

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

Как и для любой уникальной области факторизации , наибольший общий делитель (НОД) двух гауссовских целых чисел a , b - это гауссовское целое число d, которое является общим делителем a и b , которое имеет все общие делители a и b в качестве делителя. То есть (где | обозначает отношение делимости ),

  • d | а и г | б , и
  • c | а и с | b влечет c | d .

Таким образом, наибольшее значение подразумевается относительно отношения делимости, а не порядка кольца (для целых чисел оба значения наибольшего совпадают).

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

Наибольший общий делитель двух целых гауссовских чисел не уникален, но определяется с точностью до умножения на единицу . То есть, учитывая наибольший общий делитель д из и Ь , наибольшие общие делители и б являются д , - д , идентификатор , а - идентификатор .

Существует несколько способов вычисления наибольшего общего делителя двух целых гауссовских чисел a и b . Когда кто-то знает разложение на простые множители a и b ,

где простые числа p m попарно не ассоциированы, а показатели μ m не ассоциированы, наибольший общий делитель равен

с участием

К сожалению, за исключением простых случаев, разложение на простые множители трудно вычислить, а алгоритм Евклида приводит к гораздо более простым (и более быстрым) вычислениям. Этот алгоритм состоит из замены входа ( a , b ) на ( b , r ) , где r - остаток от евклидова деления a на b , и повторения этой операции до получения нулевого остатка, то есть пары ( d , 0) . Этот процесс прекращается, потому что на каждом шаге норма второго гауссовского целого числа уменьшается. Результирующий d является наибольшим общим делителем, потому что (на каждом шаге) b и r = a - bq имеют те же делители, что и a и b , и, следовательно, один и тот же наибольший общий делитель.

Этот метод вычисления работает всегда, но он не так прост, как для целых чисел, потому что евклидово деление сложнее. Поэтому для рукописных вычислений часто предпочитают третий метод. Он состоит в том, чтобы заметить, что норма N ( d ) наибольшего общего делителя a и b является общим делителем N ( a ) , N ( b ) и N ( a + b ) . Когда наибольший общий делитель D из этих трех целых чисел есть несколько факторов, то это легко проверить, для общего делителя, все гауссовые числа с нормой деления D .

Например, если a = 5 + 3 i и b = 2-8 i , у одного N ( a ) = 34 , N ( b ) = 68 и N ( a + b ) = 74 . Поскольку наибольший общий делитель трех норм равен 2, наибольший общий делитель a и b имеет норму 1 или 2. Поскольку гауссовское целое число нормы 2 необходимо связать с 1 + i , а поскольку 1 + i делит a и b , то наибольший общий делитель равен 1 + i .

Если заменить b его сопряженным b = 2 + 8 i , то наибольший общий делитель трех норм равен 34, норме a , поэтому можно догадаться, что наибольший общий делитель равен a , то есть a | б . Фактически, 2 + 8 i = (5 + 3 i ) (1 + i ) .

Конгруэнции и классы остатков

Принимая во внимание гауссов целочисленный г 0 , называемый модуль , два гауссовых целых чисел г 1 , г 2 являются сравнимыми по модулю г 0 , если их разность является кратным г 0 , то есть , если существует гауссов целочисленный д такой , что г 1 - г 2 = qz 0 . Другими словами, два гауссовских целых числа конгруэнтны по модулю z 0 , если их разность принадлежит идеалу, порожденному z 0 . Это обозначается как z 1z 2 (mod z 0 ) .

Сравнение по модулю z 0 является отношением эквивалентности (также называемым отношением конгруэнтности ), которое определяет разбиение гауссовских целых чисел на классы эквивалентности , называемые здесь классами конгруэнции или классами вычетов . Набор классов вычетов обычно обозначают Z [ я ] / г 0 Z [ я ] или Z [ я ] / ⟨ Z 0 , или просто Z [ я ] / г 0 .

Класс вычетов гауссовского целого числа a - это множество

всех гауссовских целых чисел, конгруэнтных a . Отсюда следует, что a = b тогда и только тогда, когда ab (mod z 0 ) .

Сложение и умножение совместимы со сравнениями. Это означает, что a 1b 1 (mod z 0 ) и a 2b 2 (mod z 0 ) влекут a 1 + a 2b 1 + b 2 (mod z 0 ) и a 1 a 2b 1 b 2 (по модулю z 0 ) . Это определяет четко определенные операции (которые не зависят от выбора представителей) над классами вычетов:

С помощью этих операций классы вычетов образуют коммутативное кольцо , фактор-кольцо гауссовских целых чисел по идеалу, порожденному z 0 , которое также традиционно называют кольцом классов вычетов по модулю  z 0 (подробнее см. Кольцо частных ).

Примеры

  • Для модуля 1 + i существует ровно два класса вычетов , а именно 0 = {0, ± 2, ± 4,…, ± 1 ± i , ± 3 ± i ,…} (все кратны 1 + i ) и 1 = {± 1, ± 3, ± 5,…, ± i , ± 2 ± i ,…} , которые образуют узор шахматной доски на комплексной плоскости. Таким образом, эти два класса образуют кольцо с двумя элементами, которое, по сути, является полем , единственным (с точностью до изоморфизма) полем с двумя элементами, и, таким образом, их можно отождествить с целыми числами по модулю 2 . Эти два класса можно рассматривать как обобщение разбиения целых чисел на четные и нечетные целые числа. Таким образом, можно говорить о четных и нечетных гауссовских целых числах (Гаусс разделил далее четные гауссовские целые числа на четные , которые делятся на 2, и половинные четные ).
  • Для модуля 2 существует четыре класса вычетов, а именно 0 , 1 , i , 1 + i . Они образуют кольцо из четырех элементов, в котором x = - x для каждого x . Таким образом, это кольцо не изоморфно кольцу целых чисел по модулю 4, другому кольцу с четырьмя элементами. Один имеет 1 + i 2 = 0 , и, таким образом, это кольцо не является конечным полем с четырьмя элементами или прямым произведением двух копий кольца целых чисел по модулю 2.
  • Для модуля 2 + 2i = ( i - 1) 3 существует восемь классов вычетов, а именно 0 , ± 1 , ± i , 1 ± i , 2 , из которых четыре содержат только четные целые гауссовские числа, а четыре содержат только нечетные целые гауссовы числа.

Описание классов остатков

Все 13 классов вычетов с их минимальными вычетами (синие точки) в квадрате Q 00 (светло-зеленый фон) для модуля z 0 = 3 + 2 i . Один класс остатка с z = 2-4 i ≡ - i (mod z 0 ) выделен желтыми / оранжевыми точками.

При заданном модуле z 0 все элементы класса вычетов имеют одинаковый остаток от евклидова деления на z 0 , при условии, что используется деление с уникальным частным и остатком, которое описано выше . Таким образом, перечисление классов остатков эквивалентно перечислению возможных остатков. Геометрически это можно сделать следующим образом.

В комплексной плоскости можно рассмотреть квадратную сетку , квадраты которой разделены двумя линиями

с целыми числами s и t (синие линии на рисунке). Они делят плоскость на полуоткрытые квадраты (где m и n - целые числа).

Полуоткрытые интервалы, которые встречаются в определении Q mn , были выбраны таким образом, чтобы каждое комплексное число принадлежало ровно одному квадрату; то есть квадраты Q mn образуют разбиение комплексной плоскости. Надо

Это означает, что каждое гауссовское целое число сравнимо по модулю z 0 с уникальным гауссовским целым числом в Q 00 (зеленый квадрат на рисунке), которое является его остатком от деления на z 0 . Другими словами, каждый класс вычетов содержит ровно один элемент в Q 00 .

Гауссовские целые числа в Q 00 (или на его границе ) иногда называют минимальными вычетами, потому что их норма не больше нормы любого другого гауссовского целого числа в том же классе вычетов (Гаусс называл их абсолютно наименьшими вычетами ).

Из этого можно вывести геометрическими соображениями, что количество классов вычетов по модулю целого гауссовского числа z 0 = a + bi равно его норме N ( z 0 ) = a 2 + b 2 (см. Ниже для доказательства; аналогично, для целых чисел , количество классов вычетов по модулю n равно его модулю | n | ).

Доказательство  -

Соотношение Q mn = ( m + in ) z 0 + Q 00 означает, что все Q mn получаются из Q 00 путем преобразования его в гауссовское целое число. Это означает, что все Q mn имеют одинаковую площадь N = N ( z 0 ) и содержат одинаковое количество n g целых гауссовских чисел.

Как правило, количество узлов сетки (здесь гауссовские целые числа) в произвольном квадрате с площадью A равно A + Θ ( A ) (см. Обозначения в Big theta ). Если рассматривать большой квадрат, состоящий из k × k квадратов Q mn , то он содержит k 2 N + O ( k N ) точек сетки. Отсюда следует, что k 2 n g = k 2 N + Θ ( k N ) , и, следовательно, n g = N + Θ (N/k) , после деления на k 2 . Переход к пределу, когда k стремится к бесконечности, дает n g = N = N ( z 0 ) .

Поля класса остатка

Кольцо классов вычетов по модулю целого гауссова числа z 0 является полем тогда и только тогда, когда является гауссовым простым числом .

Если z 0 - разложенное простое число или разветвленное простое число 1 + i (то есть, если его норма N ( z 0 ) является простым числом, которое либо 2, либо простое число, сравнимое с 1 по модулю 4), то поле классов вычетов имеет простое число элементов (то есть N ( z 0 ) ). Таким образом, оно изоморфно полю целых чисел по модулю N ( z 0 ) .

Если, с другой стороны, z 0 - инертное простое число (то есть N ( z 0 ) = p 2 - квадрат простого числа, которое сравнимо с 3 по модулю 4), то поле классов вычетов имеет p 2 элементов, и это расширение степени 2 (единственное с точностью до изоморфизма) простого поля с p элементами (целые числа по модулю p ).

Группа классов примитивных вычетов и функция Эйлера

Многие теоремы (и их доказательства) для модулей целых чисел можно напрямую перенести на модули целых гауссовских чисел, если заменить модуль модуля нормой. Это особенно верно для примитивной группы классов вычетов (также называемой мультипликативной группой целых чисел по модулю n ) и тотализирующей функции Эйлера . Группа классов примитивных вычетов модуля z определяется как подмножество его классов вычетов, которое содержит все классы вычетов a , взаимно простые с z , т. Е. ( A , z ) = 1 . Очевидно, эта система строит мультипликативную группу . Число его элементов обозначим через ϕ ( z ) (аналогично функции Эйлера φ ( n ) для целых чисел n ).

Для гауссовских простых чисел сразу следует, что ϕ ( p ) = | p | 2 - 1 и для произвольных составных гауссовых чисел

Формула произведения Эйлера может быть получена как

где произведение должно строиться по всем простым делителям p m числа zν m > 0 ). Также можно прямо перенести важную теорему Эйлера :

Для всех a с ( a , z ) = 1 выполняется, что a ϕ ( z ) ≡ 1 (mod z ) .

Историческое прошлое

Кольцо гауссовских целых чисел было введено Карлом Фридрихом Гауссом в его второй монографии о четверной взаимности (1832 г.). Теорема о квадратичной взаимности (которую ему впервые удалось доказать в 1796 году) связывает разрешимость сравнения x 2q (mod p ) с разрешимостью x 2p (mod q ) . Точно так же кубическая взаимность связывает разрешимость x 3q (mod p ) с разрешимостью x 3p (mod q ) , а биквадратичная (или квартичная) взаимность - это отношение между x 4q (mod p ) и x 4.p (mod q ) . Гаусс обнаружил, что закон биквадратичной взаимности и его дополнения легче сформулировать и доказать как утверждения о «целых комплексных числах» (т. Е. Гауссовских целых числах), чем как утверждения об обычных целых числах (т. Е. Целых числах).

В сноске он отмечает, что целые числа Эйзенштейна являются естественной областью для формулирования и доказательства результатов по кубической взаимности, и указывает, что подобные расширения целых чисел являются подходящими областями для изучения более высоких законов взаимности.

Эта статья не только ввела гауссовские целые числа и доказала, что они являются уникальной областью факторизации, но также ввела термины норма, единица, первичный и ассоциированный, которые теперь являются стандартными в алгебраической теории чисел.

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

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

Большинство нерешенных проблем связано с распределением гауссовых простых чисел на плоскости.

  • Задача круга Гаусса не имеет дело с гауссовыми целыми числами как таковыми, а вместо этого запрашивает количество точек решетки внутри круга заданного радиуса с центром в начале координат. Это эквивалентно определению количества гауссовских целых чисел с нормой меньше заданного значения.

Есть также предположения и нерешенные проблемы о простых гауссовских числах. Два из них:

  • Реальная и мнимая оси имеют бесконечный набор гауссовских простых чисел 3, 7, 11, 19, ... и их партнеров. Есть ли какие-нибудь другие линии, на которых есть бесконечно много гауссовских простых чисел? В частности, существует ли бесконечно много гауссовских простых чисел вида 1 + ki ?
  • Можно ли дойти до бесконечности, используя простые числа Гаусса в качестве ступеньки и делая шаги равномерно ограниченной длины? Это известно как проблема рва Гаусса ; он был поставлен в 1962 году Бэзилом Гордоном и остается нерешенным.

Смотрите также

Примечания

использованная литература

внешние ссылки