В теории чисел , целое число д называется квадратичным вычетом по модулю п , если оно конгруэнтно к идеальному квадратному по модулю п ; т. е. если существует такое целое число x , что:
В противном случае q называется квадратичным невычетом по модулю n .
Первоначально абстрактная математическая концепция из раздела теории чисел, известного как модульная арифметика , квадратичные вычеты теперь используются в различных приложениях, от акустической инженерии до криптографии и факторизации больших чисел .
Ферма , Эйлер , Лагранж , Лежандр и другие теоретики чисел 17-го и 18-го веков установили теоремы [1] и сформулировали гипотезы [2] о квадратичных вычетах, но первое систематическое рассмотрение - это § IV « Disquisitiones Arithmeticae» Гаусса (1801). . В статье 95 вводятся термины «квадратичный остаток» и «квадратичный невычет», и говорится, что, если контекст проясняет, прилагательное «квадратичный» может быть опущено.
Для данного n список квадратичных вычетов по модулю n может быть получен простым возведением в квадрат чисел 0, 1, ..., n - 1 . Поскольку a 2 ≡ ( n - a ) 2 (mod n ), список квадратов по модулю n симметричен относительно n / 2, и список должен быть только таким высоким. Это можно увидеть в таблице ниже .
Таким образом, количество квадратичных вычетов по модулю n не может превышать n / 2 + 1 ( четное n ) или ( n + 1) / 2 ( нечетное n ). [3]
Продукт двух остатков всегда является остатком.
По модулю 2 каждое целое число является квадратичным вычетом.
По модулю нечетного простого числа p имеется ( p + 1) / 2 вычетов (включая 0) и ( p - 1) / 2 невычетов по критерию Эйлера . В этом случае, принято считать 0 , как частный случай и работой в рамках мультипликативной группы ненулевых элементов в поле Z / р Z . (Другими словами, каждый класс сравнения, кроме нулевого по модулю p, имеет мультипликативный обратный. Это неверно для составных модулей.) [4]
Следуя этому соглашению, мультипликативная обратная величина остатка является остатком, а обратная величина, обратная невычету, является невычетом. [5]
Следуя этому соглашению, по модулю нечетного простого числа имеется равное количество вычетов и невычетов. [4]
По модулю простого числа произведение двух невычетов является остатком, а произведение невычетов и (ненулевого) остатка является невычетом. [5]
Первое дополнение [6] к закону квадратичной взаимности состоит в том, что если p ≡ 1 (mod 4), то −1 - квадратичный вычет по модулю p , а если p ≡ 3 (mod 4), то −1 - невычет по модулю p . Это подразумевает следующее:
Если p ≡ 1 (mod 4), отрицательный результат вычета по модулю p является вычетом, а отрицательный результат нечеткого остатка является невычетом.
Если p ≡ 3 (mod 4), отрицательный результат вычета по модулю p является невычетом, а отрицательный результат нечеткого остатка является остатком.
Все нечетные квадраты равны 1 (mod 8) и, следовательно, также 1 (mod 4). Если a - нечетное число и m = 8, 16 или некоторая более высокая степень двойки, то a является вычетом по модулю m тогда и только тогда, когда a ≡ 1 (mod 8). [7]
Например, mod (32) нечетные квадраты равны
- 1 2 ≡ 15 2 ≡ 1
- 3 2 ≡ 13 2 ≡ 9
- 5 2 ≡ 11 2 ≡ 25
- 7 2 ≡ 9 2 ≡ 49 ≡ 17
и четные
- 0 2 ≡ 8 2 ≡ 16 2 ≡ 0
- 2 2 ≡ 6 2 ≡ 10 2 ≡ 14 2 ≡ 4
- 4 2 ≡ 12 2 ≡ 16.
Таким образом, ненулевое число является остатком по модулю 8, 16 и т. Д. Тогда и только тогда, когда оно имеет вид 4 k (8 n + 1).
Ряд взаимно простой с нечетным простым р представляет собой остаток по модулю любой степени р , если и только если оно представляет собой остаток по модулю р . [8]
Если модуль равен p n ,
Обратите внимание, что правила для степеней двойки и нечетных простых чисел разные.
По модулю нечетной степени простого числа n = p k произведения вычетов и невычетов, взаимно простых с p, подчиняются тем же правилам, что и по модулю p ; p является невычетом, и, как правило, все остатки и невычеты подчиняются одним и тем же правилам, за исключением того, что произведения будут равны нулю, если степень p в произведении ≥ n .
По модулю 8 произведение невычетов 3 и 5 является невычетом 7, а также для перестановок 3, 5 и 7. Фактически, мультипликативная группа невычетов и 1 образуют четырехгруппу Клейна .
Основным фактом в этом случае является
По модулю составного числа произведение двух остатков является остатком. Продукт остатка и неостаточного количества может быть остатком, неостаточным остатком или нулем.
Например, из таблицы для модуля 6 1 , 2, 3 , 4 , 5 (остатки выделены жирным шрифтом ).
Продукт остатка 3 и неостаточного остатка 5 представляет собой остаток 3, тогда как продукт остатка 4 и неостаточного остатка 2 является неостаточным остатком 2.
Кроме того, продукт двух неостаточных остатков может быть остатком, неостаточным остатком или нулем.
Например, из таблицы для модуля 15 упругости 1 , 2, 3, 4 , 5, 6 , 7, 8, 9 , 10 , 11, 12, 13, 14 (остатки выделены жирным шрифтом ).
Продукт неостаточных 2 и 8 представляет собой остаток 1, тогда как продукт неостаточных остатков 2 и 7 представляет собой неостаточный остаток 14.
Это явление лучше всего можно описать с помощью словаря абстрактной алгебры. Классы конгруэнтно взаимно простые с модулем представляют собой группу относительно умножения, называется группой единиц в кольцо Z / п Z , а квадраты представляют собой подгруппу из него. Различные невычеты могут принадлежать разным смежным классам , и не существует простого правила, предсказывающего, в каком из них будет их произведение. По модулю простого числа существует только подгруппа квадратов и один смежный класс.
Тот факт, что, например, по модулю 15 произведение неостаточных остатков 3 и 5, или неостаточных остатков 5 и остатка 9, или два остатка 9 и 10 равны нулю, происходит от работы в полном кольце Z / n Z , что имеет делители нуля для составного n .
По этой причине некоторые авторы [10] добавляют к определению, что квадратичный вычет a должен быть не только квадратом, но и взаимно прост с модулем n . ( a взаимно просто с n тогда и только тогда, когда a 2 взаимно просто с n .)
Несмотря на то, что это упрощает ситуацию, эта статья не настаивает на том, что остатки должны быть взаимно просты с модулем.
Гаусс [11] использовал R и N для обозначения остаточности и неостаточности соответственно;
Хотя это обозначение компактно и удобно для некоторых целей, [12] [13] более полезным обозначением является символ Лежандра , также называемый квадратичным характером , который определяется для всех целых чисел a и положительных нечетных простых чисел p как
Есть две причины, по которым числа ≡ 0 (mod p ) обрабатываются особым образом. Как мы видели, это упрощает формулировку многих формул и теорем. Другая (связанная) причина заключается в том , что квадратичный характером является гомоморфизмом из мультипликативной группы ненулевых классов конгруэнции по модулю р с комплексными числами относительно умножения. Параметр позволяет расширить его область действия до мультипликативной полугруппы всех целых чисел. [14]
Одним из преимуществ этого обозначения перед обозначением Гаусса является то, что символ Лежандра является функцией, которую можно использовать в формулах. [15] Его также можно легко обобщить на кубические , квартичные и более высокие степенные вычеты. [16]
Существует обобщение символа Лежандра для составных значений р , с символом Якоби , но его свойства не так просто: если т составное и символ Якоби , то N м , а если в R м , то но если мы не знаете ли в R м или в N м . Например: а , но 2 N 15 и 4 R 15 . Если m простое, символы Якоби и Лежандра совпадают.
Хотя квадратичные остатки появляются в довольно случайном порядке по модулю n , и это использовалось в таких приложениях, как акустика и криптография , их распределение также демонстрирует некоторые поразительные закономерности.
Используя теорему Дирихле о простых числах в арифметических прогрессиях , закон квадратичной взаимности и китайскую теорему об остатках (CRT), легко увидеть, что для любого M > 0 существуют простые числа p такие, что числа 1, 2, ..., M - все вычеты по модулю p .
Например, если p ≡ 1 (mod 8), (mod 12), (mod 5) и (mod 28), то по закону квадратичной взаимности 2, 3, 5 и 7 все будут вычетами по модулю p , и таким образом все числа 1–10 будут. CRT говорит, что это то же самое, что p ≡ 1 (mod 840), а теорема Дирихле говорит, что существует бесконечное количество простых чисел этой формы. 2521 - наименьшее, и действительно 1 2 ≡ 1, 1046 2 ≡ 2, 123 2 ≡ 3, 2 2 ≡ 4, 643 2 ≡ 5, 87 2 ≡ 6, 668 2 ≡ 7, 429 2 ≡ 8, 3 2 ≡ 9 и 529 2 10 (мод. 2521).
Первая из этих закономерностей проистекает из работы Питера Густава Лежена Дирихле (1830-е годы) по аналитической формуле для числа классов двоичных квадратичных форм . [17] Пусть q - простое число, s - комплексная переменная, и определим L-функцию Дирихле как
Дирихле показал, что если q ≡ 3 (mod 4), то
Следовательно, в этом случае (простое число q 3 (mod 4)) сумма квадратичных вычетов за вычетом суммы невычетов в диапазоне 1, 2, ..., q - 1 является отрицательным числом.
Например, по модулю 11,
- 1 , 2, 3 , 4 , 5 , 6, 7, 8, 9 , 10 (остатки выделены жирным шрифтом )
- 1 + 4 + 9 + 5 + 3 = 22, 2 + 6 + 7 + 8 + 10 = 33, а разница равна −11.
Фактически, разница всегда будет нечетным кратным q, если q > 3. [18] Напротив, для простого q 1 (mod 4) сумма квадратичных вычетов минус сумма невычетов в диапазоне 1, 2, ..., q - 1 равно нулю, что означает, что обе суммы равны . [ необходима цитата ]
Дирихле также доказал, что для простого q 3 (mod 4)
Отсюда следует, что квадратичных вычетов среди чисел 1, 2, ..., ( q - 1) / 2 больше, чем невычетов .
Например, по модулю 11 четыре остатка меньше 6 (а именно 1, 3, 4 и 5), но только один невычет (2).
Любопытный факт об этих двух теоремах состоит в том, что все известные доказательства основаны на анализе; никто никогда не публиковал простых или прямых доказательств того или иного утверждения. [19]
Если p и q нечетные простые числа, то:
(( p является квадратичным вычетом по модулю q ) тогда и только тогда, когда ( q является квадратичным вычетом по модулю p )) тогда и только тогда, когда (хотя бы одно из p и q сравнимо с 1 по модулю 4).
То есть:
где является символом Лежандра .
Таким образом, для чисел a и нечетных простых p, которые не делят a :
а | a является квадратичным вычетом по модулю p тогда и только тогда, когда | а | a является квадратичным вычетом по модулю p тогда и только тогда, когда |
---|---|---|---|
1 | (каждое простое число p ) | −1 | p ≡ 1 (mod 4) |
2 | p ≡ 1, 7 (mod 8) | −2 | p ≡ 1, 3 (mod 8) |
3 | p ≡ 1, 11 (mod 12) | −3 | p ≡ 1 (mod 3) |
4 | (каждое простое число p ) | −4 | p ≡ 1 (mod 4) |
5 | p ≡ 1, 4 (mod 5) | −5 | p ≡ 1, 3, 7, 9 (мод 20) |
6 | p ≡ 1, 5, 19, 23 (мод 24) | −6 | p ≡ 1, 5, 7, 11 (мод 24) |
7 | p ≡ 1, 3, 9, 19, 25, 27 (мод 28) | −7 | p ≡ 1, 2, 4 (мод 7) |
8 | p ≡ 1, 7 (mod 8) | −8 | p ≡ 1, 3 (mod 8) |
9 | (каждое простое число p ) | −9 | p ≡ 1 (mod 4) |
10 | p ≡ 1, 3, 9, 13, 27, 31, 37, 39 (мод 40) | −10 | p ≡ 1, 7, 9, 11, 13, 19, 23, 37 (мод 40) |
11 | p ≡ 1, 5, 7, 9, 19, 25, 35, 37, 39, 43 (мод 44) | −11 | p ≡ 1, 3, 4, 5, 9 (мод 11) |
12 | p ≡ 1, 11 (mod 12) | −12 | p ≡ 1 (mod 3) |
По модулю простого p количество пар n , n + 1, где n R p и n + 1 R p , или n N p и n + 1 R p и т. Д., Почти равны. Точнее, [20] [21] пусть p нечетное простое число. Для i , j = 0, 1 определим множества
и разреши
То есть,
Тогда, если p ≡ 1 (mod 4)
и если p ≡ 3 (mod 4)
Например: (остатки выделены жирным шрифтом )
По модулю 17
- 1 , 2 , 3, 4 , 5, 6, 7, 8 , 9 , 10, 11, 12, 13 , 14, 15 , 16
- A 00 = {1,8,15},
- A 01 = {2,4,9,13},
- A 10 = {3,7,12,14},
- A 11 = {5,6,10,11}.
По модулю 19
- 1 , 2, 3, 4 , 5 , 6 , 7 , 8, 9 , 10, 11 , 12, 13, 14, 15, 16 , 17 , 18
- A 00 = {4,5,6,16},
- A 01 = {1,7,9,11,17},
- A 10 = {3,8,10,15},
- A 11 = {2,12,13,14}.
Гаусс (1828 г.) [22] ввел такой счет, когда доказал, что если p ≡ 1 (mod 4), то x 4 ≡ 2 (mod p ) может быть решено тогда и только тогда, когда p = a 2 + 64 b 2 .
Значения для последовательных значений в мимической случайной величины , как флип монеты . [23] В частности, Полиа и Виноградов доказали [24] (независимо) в 1918 году, что для любого неглавного характера Дирихле χ ( n ) по модулю q и любых целых чисел M и N ,
в большой нотации O . Параметр
это показывает, что количество квадратичных вычетов по модулю q в любом интервале длины N равно
Несложно [25] доказать, что
Фактически, [26]
Монтгомери и Воан улучшили это в 1977 году, показав, что если обобщенная гипотеза Римана верна, то
Этот результат нельзя существенно улучшить, поскольку в 1918 году Шур доказал, что
и Пейли доказал в 1932 году, что
для бесконечного числа d > 0.
Наименьший квадратичный вычет по модулю p , очевидно, равен 1. Вопрос о величине наименьшего квадратичного невычета n ( p ) более тонкий, но он всегда прост, причем 7 впервые появляется на 71.
Приведенное выше неравенство Полиа – Виноградова дает O ( √ p log p ).
Наилучшая безусловная оценка - это n ( p ) ≪ p θ для любого θ> 1/4 √ e , полученная оценками Берджесса на суммах характеров . [27]
Предполагая обобщенную гипотезу Римана , Анкени получил n ( p ) ≪ (log p ) 2 . [28]
Линник показал, что число p меньше X таких, что n ( p )> X ε , ограничено константой, зависящей от ε. [27]
Наименьшие квадратичные невычеты по модулю p для нечетных простых чисел p :
Пусть p нечетное простое число. Квадратичная избыток Е ( р ) число квадратичных вычетов на интервале (0, р / 2) минус число в диапазоне ( р / 2, р ) (последовательность A178153 в OEIS ). Для p, конгруэнтного 1 mod 4, избыток равен нулю, так как −1 - квадратичный вычет, а вычеты симметричны относительно r ↔ p - r . Для p, конгруэнтного 3 mod 4, избыток E всегда положителен. [29]
То есть, учитывая число a и модуль n , насколько это сложно
Здесь проявляется важное различие между простыми и составными модулями. По модулю простого p квадратичный вычет a имеет 1 + ( a | p ) корней (т.е. ноль, если a N p , один, если a ≡ 0 (mod p ), или два, если a R p и gcd ( a, p ) = 1.)
В общем случае, если составной модуль n записан как произведение степеней различных простых чисел, и есть n 1 корней по модулю первого, n 2 по модулю второго, ..., будет n 1 n 2 ... корней по модулю п .
Теоретический способ объединения решений по модулю простых степеней для получения решений по модулю n называется китайской теоремой об остатках ; это может быть реализовано с помощью эффективного алгоритма. [30]
Например:
- Решите x 2 ≡ 6 (mod 15).
- x 2 ≡ 6 (mod 3) имеет одно решение, 0; x 2 ≡ 6 (mod 5) имеет два, 1 и 4.
- и есть два решения по модулю 15, а именно 6 и 9.
- Решите x 2 ≡ 4 (mod 15).
- x 2 ≡ 4 (mod 3) имеет два решения: 1 и 2; x 2 ≡ 4 (mod 5) имеет два, 2 и 3.
- и есть четыре решения по модулю 15, а именно 2, 7, 8 и 13.
- Решите x 2 ≡ 7 (mod 15).
- x 2 ≡ 7 (mod 3) имеет два решения: 1 и 2; x 2 ≡ 7 (mod 5) не имеет решений.
- и решений по модулю 15 нет.
Во-первых, если модуль n является простым, символ Лежандра может быть быстро вычислен с использованием варианта алгоритма Евклида [31] или критерия Эйлера . Если он равен -1, решения нет. Во-вторых, полагая, что если n ≡ 3 (mod 4), Лагранж обнаружил, что решения задаются формулами
и Лежандр нашел аналогичное решение [32], если n 5 (mod 8):
Однако для простого n 1 (mod 8) нет известной формулы. Тонелли [33] (в 1891 г.) и Чиполла [34] нашли эффективные алгоритмы, работающие для всех простых модулей. Оба алгоритма требуют нахождения квадратичного невычета по модулю n , и для этого не существует известного детерминированного алгоритма. Но поскольку половина чисел от 1 до n не являются остатками, выбор числа x наугад и вычисление символа Лежандра до тех пор, пока не будет найден невычет, быстро произведет единицу. Небольшой вариант этого алгоритма - алгоритм Тонелли – Шанкса .
Если модуль n представляет собой степень простого числа n = p e , решение может быть найдено по модулю p и «поднято» до решения по модулю n с использованием леммы Гензеля или алгоритма Гаусса. [8]
Если модуль n был разложен на простые степени, решение обсуждалось выше.
Если n не сравнимо с 2 по модулю 4 и символу Кронекера, то решения нет; если n сравнимо с 2 по модулю 4 и , то решения также не существует. Если n не сравнимо с 2 по модулю 4 и , или n сравнимо с 2 по модулю 4 и , может быть, а может и не быть.
Если полное разложение по п не известна, а и п не сравнимо с 2 по модулю 4, или п сравнимо с 2 по модулю 4 и , проблема , как известно, эквивалентна целочисленной факторизации из п (т.е. эффективное решение либо проблема может быть использована для эффективного решения другой проблемы).
Вышеупомянутое обсуждение показывает, как знание факторов n позволяет нам эффективно находить корни. Скажем, существует эффективный алгоритм нахождения квадратных корней по модулю составного числа. В статье о сравнении квадратов обсуждается, как найти два числа x и y, где x 2 ≡ y 2 (mod n ) и x ≠ ± y, достаточно для эффективного факторизации n . Сгенерируйте случайное число, возведите его в квадрат по модулю n и попросите эффективный алгоритм извлечения квадратного корня найти корень. Повторяйте, пока он не вернет число, не равное тому, которое мы изначально возводили в квадрат (или его отрицательное значение по модулю n), затем следуйте алгоритму сравнения квадратов. Эффективность алгоритма факторизации зависит от точных характеристик средства поиска корней (например, возвращает ли он все корни? Только самый маленький? Случайный?), Но он будет эффективным. [35]
Определение того является квадратичным вычетом по модулю или невычет п (обозначается в R н или с N п ) может быть сделано эффективна для простого п путем вычисления символа Лежандра. Однако для составного n это формирует проблему квадратичной остаточности , которая, как известно, не так сложна, как факторизация, но считается довольно сложной.
С другой стороны, если мы хотим знать, существует ли решение для x, меньшего некоторого заданного предела c , эта проблема является NP-полной ; [36], однако, это решаемая проблема с фиксированным параметром , где c - параметр.
В общем, чтобы определить , является ли квадратичный вычет по модулю композит п , можно использовать следующую теорему: [37]
Пусть n > 1 и gcd ( a , n ) = 1 . Тогда x 2 ≡ a (mod n ) разрешимо тогда и только тогда, когда:
Примечание: эта теорема по существу требует, чтобы факторизация n была известна. Также обратите внимание, что если gcd ( a , n ) = m , то сравнение может быть уменьшено до a / m ≡ x 2 / m (mod n / m ) , но тогда это снимает проблему с квадратичных вычетов (если m не является квадрат).
Список количества квадратичных вычетов по модулю n для n = 1, 2, 3 ... выглядит так:
Формула для подсчета количества квадратов по модулю n дается Штанглом. [38]
Звуковые диффузоры были основаны на теоретико-числовых концепциях, таких как первообразные корни и квадратичные вычеты. [39]
Графы Пэли - это плотные неориентированные графы, по одному на каждое простое число p ≡ 1 (mod 4), которые образуют бесконечное семейство конференц-графов , которые дают бесконечное семейство симметричных конференц-матриц .
Орграфы Пэли являются направленными аналогами графов Пэли, по одному для каждого p ≡ 3 (mod 4), которые дают антисимметричные матрицы конференций.
При построении этих графов используются квадратичные вычеты.
Тот факт, что нахождение квадратного корня из числа по модулю большого составного n эквивалентно разложению на множители (которое, как многие полагают, является сложной проблемой ), использовался для построения криптографических схем, таких как криптосистема Рабина и незаметный перенос . Проблема квадратичной остаточности является основой криптосистемы Голдвассера-Микали .
Дискретный логарифм аналогичной проблема , которая также используется в криптографии.
Критерий Эйлера - это формула для символа Лежандра ( a | p ), где p простое число. Если p составное, формула может вычислить или не вычислить ( a | p ) правильно. Тест Соловея-Штрассен простоты чисел для того , данное число п простым или составным выбирает случайное A и вычисляет ( | п ) с использованием модификации алгоритма Евклида, [40] , а также с помощью критерия Эйлера. [41] Если результаты не совпадают, n составное; если они согласны, nможет быть составным или простым. Для составного n по крайней мере 1/2 значения a в диапазоне 2, 3, ..., n - 1 вернут « n составное»; для простого n никто не будет. Если после использования множества различных значений a , n не оказалось составным, это называется « вероятным простым числом ».
Тест на простоту Миллера – Рабина основан на тех же принципах. Есть детерминированная версия этого, но доказательство того, что это работает, зависит от обобщенной гипотезы Римана ; результат этого теста: « n определенно составное» или «либо n простое, либо GRH ложно». Если второй результат когда-либо произойдет для составного n , тогда GRH будет ложным, что повлияет на многие разделы математики.
В § VI Disquisitiones Arithmeticae [42] Гаусс обсуждает два алгоритма факторизации, которые используют квадратичные вычеты и закон квадратичной взаимности .
Несколько современных алгоритмов факторизации (включая алгоритм Диксона , метод непрерывных дробей , квадратичное решето и решето числового поля ) генерируют небольшие квадратичные вычеты (по модулю факторизуемого числа) в попытке найти конгруэнтность квадратов, которая даст факторизацию. Сито числовых полей - это самый быстрый из известных алгоритмов факторизации общего назначения.
В следующей таблице (последовательность A096008 в OEIS ) перечислены квадратичные остатки по модулю от 1 до 75 ( красное число означает, что он не взаимно прост с n ). (О квадратичных вычетах, взаимно простых с n , см. OEIS : A096103 , а о ненулевых квадратичных вычетах см. OEIS : A046071 .)
п | квадратичные вычеты по модулю n | п | квадратичные вычеты по модулю n | п | квадратичные вычеты по модулю n |
---|---|---|---|---|---|
1 | 0 | 26 | 0 , 1, 3, 4 , 9, 10 , 12 , 13 , 14 , 16 , 17, 22 , 23, 25 | 51 | 0 , 1, 4, 9 , 13, 15 , 16, 18 , 19, 21 , 25, 30 , 33 , 34 , 36 , 42 , 43, 49 |
2 | 0 , 1 | 27 | 0 , 1, 4, 7, 9 , 10, 13, 16, 19, 22, 25 | 52 | 0 , 1, 4 , 9, 12 , 13 , 16 , 17, 25, 29, 36 , 40 , 48 , 49 |
3 | 0 , 1 | 28 год | 0 , 1, 4 , 8 , 9, 16 , 21 , 25 | 53 | 0 , 1, 4, 6, 7, 9, 10, 11, 13, 15, 16, 17, 24, 25, 28, 29, 36, 37, 38, 40, 42, 43, 44, 46, 47, 49, 52 |
4 | 0 , 1 | 29 | 0 , 1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28 | 54 | 0 , 1, 4 , 7, 9 , 10 , 13, 16 , 19, 22 , 25, 27 , 28 , 31, 34 , 36 , 37, 40 , 43, 46 , 49, 52 |
5 | 0 , 1, 4 | 30 | 0 , 1, 4 , 6 , 9 , 10 , 15 , 16 , 19, 21 , 24 , 25 | 55 | 0 , 1, 4, 5 , 9, 11 , 14, 15 , 16, 20 , 25 , 26, 31, 34, 36, 44 , 45 , 49 |
6 | 0 , 1, 3 , 4 | 31 год | 0 , 1, 2, 4, 5, 7, 8, 9, 10, 14, 16, 18, 19, 20, 25, 28 | 56 | 0 , 1, 4 , 8 , 9, 16 , 25, 28 , 32 , 36 , 44 , 49 |
7 | 0 , 1, 2, 4 | 32 | 0 , 1, 4 , 9, 16 , 17, 25 | 57 год | 0 , 1, 4, 6 , 7, 9 , 16, 19 , 24 , 25, 28, 30 , 36 , 39 , 42 , 43, 45 , 49, 54 , 55 |
8 | 0 , 1, 4 | 33 | 0 , 1, 3 , 4, 9 , 12 , 15 , 16, 22 , 25, 27 , 31 | 58 | 0 , 1, 4 , 5, 6 , 7, 9, 13, 16 , 20 , 22 , 23, 24 , 25, 28 , 29 , 30 , 33, 34 , 35, 36 , 38 , 42 , 45, 49, 51, 52 , 53, 54 , 57 |
9 | 0 , 1, 4, 7 | 34 | 0 , 1, 2 , 4 , 8 , 9, 13, 15, 16 , 17 , 18 , 19, 21, 25, 26 , 30 , 32 , 33 | 59 | 0 , 1, 3, 4, 5, 7, 9, 12, 15, 16, 17, 19, 20, 21, 22, 25, 26, 27, 28, 29, 35, 36, 41, 45, 46, 48, 49, 51, 53, 57 |
10 | 0 , 1, 4 , 5 , 6 , 9 | 35 год | 0 , 1, 4, 9, 11, 14 , 15 , 16, 21 , 25 , 29, 30 | 60 | 0 , 1, 4 , 9 , 16 , 21 , 24 , 25 , 36 , 40 , 45 , 49 |
11 | 0 , 1, 3, 4, 5, 9 | 36 | 0 , 1, 4 , 9 , 13, 16 , 25, 28 | 61 | 0 , 1, 3, 4, 5, 9, 12, 13, 14, 15, 16, 19, 20, 22, 25, 27, 34, 36, 39, 41, 42, 45, 46, 47, 48, 49, 52, 56, 57, 58, 60 |
12 | 0 , 1, 4 , 9 | 37 | 0 , 1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36 | 62 | 0 , 1, 2 , 4 , 5, 7, 8 , 9, 10 , 14 , 16 , 18 , 19, 20 , 25, 28 , 31 , 32 , 33, 35, 36 , 38 , 39, 40 , 41, 45, 47, 49, 50 , 51, 56 , 59 |
13 | 0 , 1, 3, 4, 9, 10, 12 | 38 | 0 , 1, 4 , 5, 6 , 7, 9, 11, 16 , 17, 19 , 20 , 23, 24 , 25, 26 , 28 , 30 , 35, 36 | 63 | 0 , 1, 4, 7 , 9 , 16, 18 , 22, 25, 28 , 36 , 37, 43, 46, 49 , 58 |
14 | 0 , 1, 2 , 4 , 7 , 8 , 9, 11 | 39 | 0 , 1, 3 , 4, 9 , 10, 12 , 13 , 16, 22, 25, 27 , 30 , 36 | 64 | 0 , 1, 4 , 9, 16 , 17, 25, 33, 36 , 41, 49, 57 |
15 | 0 , 1, 4, 6 , 9 , 10 | 40 | 0 , 1, 4 , 9, 16 , 20 , 24 , 25 , 36 | 65 | 0 , 1, 4, 9, 10 , 14, 16, 25 , 26 , 29, 30 , 35 , 36, 39 , 40 , 49, 51, 55 , 56, 61, 64 |
16 | 0 , 1, 4 , 9 | 41 год | 0 , 1, 2, 4, 5, 8, 9, 10, 16, 18, 20, 21, 23, 25, 31, 32, 33, 36, 37, 39, 40 | 66 | 0 , 1, 3 , 4 , 9 , 12 , 15 , 16 , 22 , 25, 27 , 31, 33 , 34 , 36 , 37, 42 , 45 , 48 , 49, 55 , 58 , 60 , 64 |
17 | 0 , 1, 2, 4, 8, 9, 13, 15, 16 | 42 | 0 , 1, 4 , 7 , 9 , 15 , 16 , 18 , 21 , 22 , 25, 28 , 30 , 36 , 37, 39 | 67 | 0 , 1, 4, 6, 9, 10, 14, 15, 16, 17, 19, 21, 22, 23, 24, 25, 26, 29, 33, 35, 36, 37, 39, 40, 47, 49, 54, 55, 56, 59, 60, 62, 64, 65 |
18 | 0 , 1, 4 , 7, 9 , 10 , 13, 16 | 43 год | 0 , 1, 4, 6, 9, 10, 11, 13, 14, 15, 16, 17, 21, 23, 24, 25, 31, 35, 36, 38, 40, 41 | 68 | 0 , 1, 4 , 8 , 9, 13, 16 , 17 , 21, 25, 32 , 33, 36 , 49, 52 , 53, 60 , 64 |
19 | 0 , 1, 4, 5, 6, 7, 9, 11, 16, 17 | 44 год | 0 , 1, 4 , 5, 9, 12 , 16 , 20 , 25, 33 , 36 , 37 | 69 | 0 , 1, 3 , 4, 6 , 9 , 12 , 13, 16, 18 , 24 , 25, 27 , 31, 36 , 39 , 46 , 48 , 49, 52, 54 , 55, 58, 64 |
20 | 0 , 1, 4 , 5 , 9, 16 | 45 | 0 , 1, 4, 9 , 10 , 16, 19, 25 , 31, 34, 36 , 40 | 70 | 0 , 1, 4 , 9, 11, 14 , 15 , 16 , 21 , 25 , 29, 30 , 35 , 36 , 39, 44 , 46 , 49 , 50 , 51, 56 , 60 , 64 , 65 |
21 год | 0 , 1, 4, 7 , 9 , 15 , 16, 18 | 46 | 0 , 1, 2 , 3, 4 , 6 , 8 , 9, 12 , 13, 16 , 18 , 23 , 24 , 25, 26 , 27, 29, 31, 32 , 35, 36 , 39, 41 | 71 | 0 , 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 19, 20, 24, 25, 27, 29, 30, 32, 36, 37, 38, 40, 43, 45, 48, 49, 50, 54, 57, 58, 60, 64 |
22 | 0 , 1, 3, 4 , 5, 9, 11 , 12 , 14 , 15, 16 , 20 | 47 | 0 , 1, 2, 3, 4, 6, 7, 8, 9, 12, 14, 16, 17, 18, 21, 24, 25, 27, 28, 32, 34, 36, 37, 42 | 72 | 0 , 1, 4 , 9 , 16 , 25, 28 , 36 , 40 , 49, 52 , 64 |
23 | 0 , 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18 | 48 | 0 , 1, 4 , 9 , 16 , 25, 33 , 36 | 73 | 0 , 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 19, 23, 24, 25, 27, 32, 35, 36, 37, 38, 41, 46, 48, 49, 50, 54, 55, 57, 61, 64, 65, 67, 69, 70, 71, 72 |
24 | 0 , 1, 4 , 9 , 12 , 16 | 49 | 0 , 1, 2, 4, 8, 9, 11, 15, 16, 18, 22, 23, 25, 29, 30, 32, 36, 37, 39, 43, 44, 46 | 74 | 0 , 1, 3, 4 , 7, 9, 10 , 11, 12 , 16 , 21, 25, 26 , 27, 28 , 30 , 33, 34 , 36 , 37 , 38 , 40 , 41, 44 , 46 , 47, 48 , 49, 53, 58 , 62 , 63, 64 , 65, 67, 70 , 71, 73 |
25 | 0 , 1, 4, 6, 9, 11, 14, 16, 19, 21, 24 | 50 | 0 , 1, 4 , 6 , 9, 11, 14 , 16 , 19, 21, 24 , 25 , 26 , 29, 31, 34 , 36 , 39, 41, 44 , 46 , 49 | 75 | 0 , 1, 4, 6 , 9 , 16, 19, 21 , 24 , 25 , 31, 34, 36 , 39 , 46, 49, 51 , 54 , 61, 64, 66 , 69 |
Икс | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 год | 22 | 23 | 24 | 25 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
х 2 | 1 | 4 | 9 | 16 | 25 | 36 | 49 | 64 | 81 год | 100 | 121 | 144 | 169 | 196 | 225 | 256 | 289 | 324 | 361 | 400 | 441 | 484 | 529 | 576 | 625 |
мод 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
мод 2 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
мод 3 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
мод 4 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
мод 5 | 1 | 4 | 4 | 1 | 0 | 1 | 4 | 4 | 1 | 0 | 1 | 4 | 4 | 1 | 0 | 1 | 4 | 4 | 1 | 0 | 1 | 4 | 4 | 1 | 0 |
мод 6 | 1 | 4 | 3 | 4 | 1 | 0 | 1 | 4 | 3 | 4 | 1 | 0 | 1 | 4 | 3 | 4 | 1 | 0 | 1 | 4 | 3 | 4 | 1 | 0 | 1 |
мод 7 | 1 | 4 | 2 | 2 | 4 | 1 | 0 | 1 | 4 | 2 | 2 | 4 | 1 | 0 | 1 | 4 | 2 | 2 | 4 | 1 | 0 | 1 | 4 | 2 | 2 |
мод 8 | 1 | 4 | 1 | 0 | 1 | 4 | 1 | 0 | 1 | 4 | 1 | 0 | 1 | 4 | 1 | 0 | 1 | 4 | 1 | 0 | 1 | 4 | 1 | 0 | 1 |
мод 9 | 1 | 4 | 0 | 7 | 7 | 0 | 4 | 1 | 0 | 1 | 4 | 0 | 7 | 7 | 0 | 4 | 1 | 0 | 1 | 4 | 0 | 7 | 7 | 0 | 4 |
мод 10 | 1 | 4 | 9 | 6 | 5 | 6 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 6 | 5 | 6 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 6 | 5 |
мод 11 | 1 | 4 | 9 | 5 | 3 | 3 | 5 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 5 | 3 | 3 | 5 | 9 | 4 | 1 | 0 | 1 | 4 | 9 |
мод 12 | 1 | 4 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 4 | 1 | 0 | 1 |
мод 13 | 1 | 4 | 9 | 3 | 12 | 10 | 10 | 12 | 3 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 3 | 12 | 10 | 10 | 12 | 3 | 9 | 4 | 1 |
мод 14 | 1 | 4 | 9 | 2 | 11 | 8 | 7 | 8 | 11 | 2 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 2 | 11 | 8 | 7 | 8 | 11 | 2 | 9 |
мод 15 | 1 | 4 | 9 | 1 | 10 | 6 | 4 | 4 | 6 | 10 | 1 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 1 | 10 | 6 | 4 | 4 | 6 | 10 |
мод 16 | 1 | 4 | 9 | 0 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 0 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 0 | 9 | 4 | 1 | 0 | 1 |
мод 17 | 1 | 4 | 9 | 16 | 8 | 2 | 15 | 13 | 13 | 15 | 2 | 8 | 16 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 16 | 8 | 2 | 15 | 13 |
мод 18 | 1 | 4 | 9 | 16 | 7 | 0 | 13 | 10 | 9 | 10 | 13 | 0 | 7 | 16 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 16 | 7 | 0 | 13 |
мод 19 | 1 | 4 | 9 | 16 | 6 | 17 | 11 | 7 | 5 | 5 | 7 | 11 | 17 | 6 | 16 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 16 | 6 | 17 |
мод 20 | 1 | 4 | 9 | 16 | 5 | 16 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 16 | 5 | 16 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 16 | 5 |
мод 21 | 1 | 4 | 9 | 16 | 4 | 15 | 7 | 1 | 18 | 16 | 16 | 18 | 1 | 7 | 15 | 4 | 16 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 16 |
мод 22 | 1 | 4 | 9 | 16 | 3 | 14 | 5 | 20 | 15 | 12 | 11 | 12 | 15 | 20 | 5 | 14 | 3 | 16 | 9 | 4 | 1 | 0 | 1 | 4 | 9 |
мод 23 | 1 | 4 | 9 | 16 | 2 | 13 | 3 | 18 | 12 | 8 | 6 | 6 | 8 | 12 | 18 | 3 | 13 | 2 | 16 | 9 | 4 | 1 | 0 | 1 | 4 |
мод 24 | 1 | 4 | 9 | 16 | 1 | 12 | 1 | 16 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 16 | 1 | 12 | 1 | 16 | 9 | 4 | 1 | 0 | 1 |
мод 25 | 1 | 4 | 9 | 16 | 0 | 11 | 24 | 14 | 6 | 0 | 21 год | 19 | 19 | 21 год | 0 | 6 | 14 | 24 | 11 | 0 | 16 | 9 | 4 | 1 | 0 |
Disquisitiones Arithmeticae был переведен из Гаусса Цицерона латыни в английском и немецком языках . Немецкое издание включает все его работы по теории чисел: все доказательства квадратичной взаимности, определение знака суммы Гаусса , исследования биквадратичной взаимности и неопубликованные заметки.