Таблицы Брадиса

Поэтому достаточно научиться решать задачу

Поэтому достаточно научиться решать задачу

Элементы математики в задачах - Г. А. Мерзон

192                             Целые числа 3. Сравнения

Для конкретных прогрессий (см. пункт а) иногда удается найти «школьные» доказательства, но доказательство общей теоремы ис­пользует аппарат математического анализа.

Задача 19*. Найдите количество решений сравнения х2 = 1 (mod n): а) при простом n; б) при произвольном n.

Ш Так как множество решений n-периодично, если есть одно ре­шение, то есть и бесконечно много решений. Поэтому естественно искать количество решений по модулю n.

Ответ. а) 2, если n > 2; 1, если n = 2;

б) если n раскладывается на простые множители как 2n°pj1...рП, то число решений есть

2k, n° = 0,1;

-  2k+1, n° = 2;

2k+2, n° > 2.

V

Решение. а) Заметим, что сравнение х2 = 1 (mod n) равносильно сравнению (х — 1)(х + 1) = 0 (mod n). Так как произведение делится на простое число только тогда, когда на него делится хотя бы один из сомножителей, последнее сравнение дает х = ±1 (mod n). Осталось только не забыть, что по модулю 2 эти случаи совпадают: 1 = — 1.

б)   (Набросок.) Согласно китайской теореме об остатках, если n = 2n° П рП‘ , то исходное уравнение равносильно системе

г х2 = 1 (mod 2n°); х2 = 1 (mod pj1);

кх1 = 1 (mod pn).

Поэтому достаточно научиться решать задачу для n = pk (где p — простое).

Нас интересуют решения уравнения х2 = 1 (mod pk). Разложим его на множители: (х — 1)(х + 1). pk. Выражения в скобках отлича­ются на 2, поэтому при p > 2 даже на p может делиться только одна из них, то есть х = ±1 (mod pk). Таким образом, при p > 2 имеется два различных решения.

При p = 2 все сложнее, но не намного: хотя на 2 могут делиться выражения в обеих скобках, на 4 уже может делиться только одна из

них; таким образом, либо x = ±1 (mod 2к) (причем оба эти остатка совпадают при к = 1), либо x = 2k-1 ± 1 (mod 2k) (последний случай возможен для к > 1, но отличается от первого только при к > 2). Таким образом, при p = 2 имеется одно решение при к = 1, два решения при к = 2 и четыре решения при к > 2.