МАЛЫЙ МЕХМАТ МГУ

Кружок 9-10 класса

Руководители Иван Александрович Дорофеев и Степан Львович Кузнецов
2006/2007 учебный год

Листок 1. Китайская теорема об остатках

Все числа, о которых пойдет речь, будут целыми.
Теорема. Пусть даны n попарно взаимно простых чисел m1, m2,... ,mn (то есть каждые два из них взаимно просты) и чисел r1, r2,... ,rn таких, что 0 ≤ rimi − 1 (i = 1, 2, ..., n). Тогда существует единственное число N такое, что 0 ≤ Nm1m2... mn − 1, дающее при делении на mi остаток ri.
Докажите эту теорему по шагам.
1.
Пусть a взаимно просто с b.
a)
докажите, что числа a, 2a, ..., (b − 1)a дают разные остатки при делении на b;
b)
докажите, что среди этих остатков есть 1, то есть существует k такое, что 1 ≤ kb − 1 и ka дает при делении на b остаток 1.
Далее, в следующих задачах, числа m1, m2,... , mn и r1, r2,... , rn из условия Теоремы. Обозначим
Mi= m1m2...mn .
mi
2.
a)
Докажите, что существуют такие числа xi, что xiMi дает при делении на mi в остатке 1.
b)
Какой остаток дает xiMi при делении на mj (ij)?
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 ≤ Nm1m2... mn − 1, дающее при делении на mi остаток ri.
Используя эту Теорему, решите задачу.
6.
Вы предлагаете кому-нибудь задумать двузначное число и сказать Вам остатки от деления этого числа на 3, 5 и 7. Как по этим данным отгадать задуманное число?

Вы видите ошибку? Выделите её и нажмите Ctrl+Enter! Rambler's Top100
liveinternet.ru
Apache
PHP
HTML 4.01
CSS