Если бы числа могли говорить. Гаусс. Теория чисел (Лизана) - страница 27

Также преимущество этой записи состоит в том, что она напоминает форму, в которой мы записываем алгебраические выражения. Вместо арифметической делимости, описание которой может быть громоздким, она дает краткую запись, благодаря которой можно складывать, вычитать и умножать сравнения, если их модуль одинаков, а также решать уравнения вида: ах + b == c (mod m).

В заключении к двум первым разделам Гаусс применил эти методы к историческим проблемам, таким как вычисление знаменитой функции φ Эйлера. Функция φ(N) определяется как количество целых положительных чисел, меньших или равных N и взаимно простых с Ν. В математике два числа называются взаимно простыми, если у них нет общих делителей, то есть их наибольший общий делитель — 1. Например, 9 = З² является взаимно простым с 10 = 5 · 2, и его нужно было бы найти при вычислении φ( 10). Множество φ( 10) состоит, следовательно, из четырех элементов (1, 3, 7 и 9), и значит, φ( 10) = 4.

Гаусс вывел общую формулу для вычисления φ(Ν). Если мы разложим N на простые множители ρ_>1,ρ_>2, ...,р_>n, то получим N = р_>1^>m_>1, p_>2^>m_>2 · ... · p_>n^>m_>n, где p_>i простые числа, a m_>i — кратность их повторения. Формула имеет вид:

Если применить формулу к N= 10, то

чего и следовало ожидать.

Формула зависит от простых чисел, на которые раскладывается N, а не от кратности их повторения. В случае с N = 180 получается, что 180 = 2² · З² · 5, следовательно,

Раздел заканчивается доказательством основной теоремы о многочленных сравнениях. Так, сравнение степени m,

a_>mx^>m + a_>m-1x^>m-1 + ··· +а_>1x + b == 0 (mod р),

модуль которой р — простое число, не являющееся делителем а_>m, может быть решена не более чем m различными способами или не может иметь больше m корней, не сравнимых по модулю р.

В разделе III, озаглавленном De residuis Potestatum («О степенных вычетах»), говорится о квадратичных вычетах и вычетах большей степени. Если заданы целые числа тип, где m не является делителем n, и если существует такое число x, что х² = m (mod n), говорят, что m — квадратичный вычет по модулю n; в противном случае говорят, что m — квадратичный невычет по модулю n. Например: 13 — квадратичный вычет по модулю 17, поскольку уравнение х² == 13 (mod 17) имеет в качестве решений х = 8, 25, 42, поскольку 8² = 64, что при делении на 17 дает 13 в остатке, 25² = 625, что при делении на 17 вновь дает 13 в остатке, и то же самое происходит с 42² = 1764.

В разделе доказывается малая теорема Ферма: np-^>1 == 1 (mod p), где р — простое число, не являющееся делителем n. То есть если р — простое число, которое не является делителем n, то n