|
Кружок 9-10 класса
Руководители Иван Александрович Дорофеев и Степан Львович Кузнецов 2006/2007 учебный год
Листок 1. Китайская теорема об остатках
Все числа, о которых пойдет речь, будут целыми.
Теорема. Пусть даны n попарно взаимно простых чисел
m1, m2,... ,mn
(то есть каждые два из них взаимно просты) и чисел
r1, r2,... ,rn
таких, что 0 ≤ ri ≤ mi − 1
(i = 1, 2, ..., n). Тогда существует единственное число
N такое, что
0 ≤ N ≤ m1m2...
mn − 1, дающее при делении на mi
остаток ri.
Докажите эту теорему по шагам.
- 1.
-
Пусть a взаимно просто с b.
- a)
- докажите, что числа a, 2a, ..., (b − 1)a
дают разные остатки при делении на b;
- b)
- докажите, что среди этих остатков есть 1, то есть существует k такое,
что 1 ≤ k ≤ b − 1 и ka дает при делении
на b остаток 1.
Далее, в следующих задачах, числа m1, m2,... ,
mn и r1, r2,... ,
rn из условия Теоремы. Обозначим
- 2.
-
- a)
- Докажите, что существуют такие числа xi, что
xiMi дает при делении на mi в остатке 1.
- b)
- Какой остаток дает xiMi при делении на
mj (i ≠ j)?
- 3.
-
Докажите, что A =
x1M1r1 +
x2M2r2 + ... +
xnMnrn дает при делении на
mi остаток ri.
Здесь xi взяты из задачи 2 (i = 1, 2, ..., n).
- 4.
-
Пусть числа a и b дают одинаковые остатки при делении на
m1 и дают одинаковые остатки при делении на m2,
где m1 и m2 взаимно просты. Докажите, что
тогда a и b дают одинаковые остатки при делении на
m1m2.
- 5.
-
Докажите, что в условии Теоремы существует единственное число N такое,
что 0 ≤ N ≤ m1m2...
mn − 1, дающее при делении на mi
остаток ri.
Используя эту Теорему, решите задачу.
- 6.
-
Вы предлагаете кому-нибудь задумать двузначное число и сказать Вам остатки от деления
этого числа на 3, 5 и 7. Как по этим данным отгадать задуманное число?
|