ВУЗ:
Составители:
Рубрика:
43
Вы могли упорядочить сравнения выбором модулей пар взаимно простых
чисел и начать с ответа!
2. Предположим, что р – простое число, и существует а такое, что
a
≡ –1 (mod р). (Мы увидим позднее, что это абсолютно справедливо для
простых чисел вида 4k + 1). Используйте лемму Тью (п. 10.8) для доказа-
тельства того, что существуют х и у такие, что х
2
+ у
2
≡ 0 (mod р). (Так как
р – сумма двух квадратов).
3. Пусть m и n – взаимно простые целые числа, и m – нечётное. Про-
верьте, используя китайскую теорему об остатках, что мы можем найти це-
лые числа a > 0, b > 0 c делителем m для обоих чисел 2а + 1 и b, и с n – со-
множителем для обоих
a и b + 1.
Теперь рассмотрим уравнение X
2
+ Y = Z
2
, которое, конечно, имеет
решение в целых числах X, Y, Z – все > 0. Умножая обе части на Y
2a
Z
2b
, от-
сюда найдём целочисленные решения уравнения x
2
+ y
m
= z
2n
. Существует
ли соответствующий результат для чётных m?
10.11. Проект: представление простых чисел вида 4k + 1 в виде
суммы двух квадратов.
Существует прекрасный алгоритм для нахождения
целых чисел х и у таких, что х
2
+ у
2
= р, где р – есть заданное простое число
вида 4k + 1. Мы только установим это здесь и предложим Вам написать для
него компьютерную программу. Нам необходимо найти а с условием а
2
≡
≡ –1 (mod p). Теперь для некоторого с, удовлетворяющего условию p | c, по-
лучим
(1)
2
1(mod )
p
cp
−
≡±
; начиная с с = 2, мы найдём с, которое будет
(1)
2
1(mod )
p
cp
−
≡−
. (Полученный результат говорит о том, что с не является
точным квадратом по mod p). Мы тогда выберем
4
)1( −
=
p
ca , помня, что
p – 1 делится на 4.
Прекрасным алгоритмом будет следующий: применим алгоритм Евк-
лида к р и а; первыми двумя остатками, которые меньше
p
, будут подхо-
дящие целые числа х и у, для которых х
2
+ у
2
= р. (Заметим, что остатки в
конце концов достигают 1, так как они, несомненно, будут остатками,
меньшими, чем
p
).
Несложно расширить китайскую теорему об остатках до главных мо-
дулей, хотя и отсутствует простая привлекательная формула для решения.
Мы уже встречались с некоторыми с подобными примерами ранее. Резуль-
тат отражен в п. 10.12.
10.12*. Система линейных сравнений с произвольным модулем
.
Сравнения х ≡ a
i
(mod m
i
), i = 1, . . . , r имеют систему решений, если и
только если для всех i ≠ j, (m
i
, m
j
) | (a
i
– a
j
). Решение тогда единственно по
mod [m
1
, . . . , m
r
] = наименьшему общему кратному m
1
, . . . , m
r
.
Страницы
- « первая
- ‹ предыдущая
- …
- 41
- 42
- 43
- 44
- 45
- …
- следующая ›
- последняя »
