|
Также преимущество этой записи состоит в том, что она напоминает форму, в которой мы записываем алгебраические выражения. Вместо арифметической делимости, описание которой может быть громоздким, она дает краткую запись, благодаря которой можно складывать, вычитать и умножать сравнения, если их модуль одинаков, а также решать уравнения вида: ах + b == c (mod m). В заключении к двум первым разделам Гаусс применил эти методы к историческим проблемам, таким как вычисление знаменитой функции ? Эйлера. Функция ?(N) определяется как количество целых положительных чисел, меньших или равных N и взаимно простых с ?. В математике два числа называются взаимно простыми, если у них нет общих делителей, то есть их наибольший общий делитель — 1. Например, 9 = З? является взаимно простым с 10 = 5 · 2, и его нужно было бы найти при вычислении ?( 10). Множество ?( 10) состоит, следовательно, из четырех элементов (1, 3, 7 и 9), и значит, ?( 10) = 4. Гаусс вывел общую формулу для вычисления ?(?). Если мы разложим N на простые множители ?1,?2, ...,рn, то получим N = р1m1, p2m2 · ... · pnmn, где pi простые числа, a mi — кратность их повторения. Формула имеет вид: Если применить формулу к N= 10, то чего и следовало ожидать. Формула зависит от простых чисел, на которые раскладывается N, а не от кратности их повторения. В случае с N = 180 получается, что 180 = 2? · З? · 5, следовательно, Раздел заканчивается доказательством основной теоремы о многочленных сравнениях. Так, сравнение степени m, amxm + am-1xm-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, то np-1 всегда делится на р. Для случая n = 8 np = 5 получается, что 84-1 = 4095, а это делится на 5. Для получения этого результата Гаусс воспользовался формулой бинома Ньютона, сформулированной для сравнений. Следствием является теорема Вильсона, в которой говорится, что если задано простое число р, то — 27 —
|