ВУЗ:
Составители:
Рубрика:
44
В качестве примера рассмотрим х
≡ 5 (mod 6), х
≡ 9 (mod 10) и
х ≡ 2 (mod 9). Гипотезы п. 10.12 удовлетворены, и мы решим последова-
тельной подстановкой. Таким образом, выражение х = 5 + 6 u, подставлен-
ное во второе сравнение, даёт 6u
≡ 4 (mod 10), т. е., 3u ≡ 2 (mod 5), так что
получим u
≡ 4 (mod 5), u = 4 + 5 v, что дает х = 29 + + 30 v. Подстановка в
третье сравнение даёт 30v
≡ 0 (mod 9), т. е., 10v ≡ 0 (mod 3), так что v
≡
≡ 0 (mod 3) и, наконец, х
≡ 29 (mod 90) является решением. Заметим, что
данные сравнения можно привести к системе х ≡ 1 (mod 2), х ≡ 4 (mod 5) и
х ≡ 2 (mod 9), которая может быть решена по формуле из доказательства ки-
тайской теоремы об остатках.
10.13*. Проект. Напишите программу для решения системы из трёх
сравнений х
≡ a (mod m), х
≡ b (mod n), х
≡ c (mod k), сначала проверяя, су-
ществует ли решение на основе критерия п. 10.12. Проверьте, что решением
системы сравнений х
≡ 20 (mod 28), х
≡ 10 (mod 90), х ≡ 55 (mod 105) будет
х ≡ 1000 (mod 1260), и предложите Ваш собственный пример для дальней-
шей проверки программы.
11. Дальнейшие примеры сравнений
11.1. Проект: простые числа в арифметической прогрессии. Пусть
r ≥ 3 и пусть d будет чётным и ≥ 4. Нужно найти r последовательных про-
стых чисел арифметической прогрессии:
p, p + d, p + 2d, . . . , p + (r – 1) d.
1. Пусть r = 3d, d = 6. Таким образом, р, р + 6, р + 12 являются последова-
тельными простыми числами. Покажите, что если 3 | (p + 1), 5 | (p + 3) и 7 | (p +
+ 2), тогда
p + i будет составное число для 1 ≤ i ≤ 11, i ≠ 6. Покажите, что эти
условия делимости обеспечивают р ≡ 47 (mod 105). Напишите программу для
нахождения р, которое < 10 000 и, удовлетворяя этому сравнению, дает три по-
следовательных простых числа в арифметической прогрессии.
2. Принимая, что p > 3 и р, р + d, p + 2d – все простые числа (так r
= 3
cнова), покажите, что d ≡ 0 (mod 3). [Подсказка: покажите, что если 3 не де-
лит d, тогда р, р + d, p + 2d будут различными по модулю 3. Почему это яв-
ляется противоречием?) Так как d – чётное число, это даёт d = 0 (mod 6).
[Получен результат, аналогичный для пяти простых чисел (все >5), обра-
зующих арифметическую прогрессию с разностью
d: мы имеем
2 × 3 × 5 = 30 | d. Без сомнения здесь Вы можете увидеть главный результат!
По-видимому, первое упоминание об этом найдено у Варинга в 1770 г.].
3. Пусть r = 4, d = 6. Покажите, что если 3 | (p + 1), 5 | (p + 4), 7 | (p + 2)
и 11 | (p + 8), тогда p + i составное число для 1 ≤ i ≤ 17, i ≠ 6, 12. Покажите,
что эти
условия делимости выполняются для р ≡ 971 (mod 1155), и найдите
такое наименьшее р, которое обеспечивает получение четырех последова-
тельных простых чисел в арифметической прогрессии. (Подсказка: это про-
Страницы
- « первая
- ‹ предыдущая
- …
- 42
- 43
- 44
- 45
- 46
- …
- следующая ›
- последняя »
