Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/s43/math/uroki/2010_2011/9mat_1011/spec/110_Integers.doc Дата изменения: Sun Sep 2 21:25:13 2012 Дата индексирования: Tue Feb 5 06:52:23 2013 Кодировка: koi8-r Поисковые слова: внешние планеты

Гимназия 1543, 9-В класс
Листик 11, 4 сентября 2010.
Целые числа 3.

Определение 1. Два целых числа a и b называются сравнимыми по модулю m,
если при делении на m они дают одинаковые остатки.
Определение 2. Два целых числа a и b называются сравнимыми по модулю m,
если их разность делится на m.
Записывается это так [pic]. (иногда используют обозначение [pic])
1. Докажите, что определения 1 и 2 равносильны.

2. (Свойства сравнений)
а) (транзитивность) Если a ( b (mod m) и b ( с (mod m), то a ( с (mod m);
б) (сложение) Если a ( b (mod m) и c ( d (mod m), то a ± с ( b ± d (mod
m);
в) (умножение) Если a ( b (mod m) и c ( d (mod m), то ac ( bd (mod m);
г) (возведение в степень) Если a ( b (mod m), то ak ( bk (mod m);

3. Посчитайте, используя свойства сравнений, следующие остатки от деления
а) числа 9100 на 8 б) числа 1299 на 13 в) числа 2349 на 7 г) числа
[pic] на 5

4. а) Докажите, что [pic]
б) Докажите, что [pic]

5. Найдите натуральное число, которые сравнимо с -1 по каждому из модулей
1,2,3,4,5,6,7,8. Найдите еще несколько таких чисел.

6. (Деление) а) Пусть p - простое, c не кратно p. Докажите, что если
[pic], то [pic].
б) Пусть c не кратно m, но m не обязательно простое. Следует ли теперь из
сравнения [pic] сравнение [pic]?
в) Придумайте и докажите обобщение пункта а) на случай составного модуля.

7. Решите сравнения (т.е. найдите все x такие что)
а) [pic] б) [pic] в) [pic]

8. а) Докажите, что [pic]
б) Пусть p - простое число. Докажите, что [pic]
в) (Малая теорема Ферма). Пусть p - простое число. Докажите, [pic]



9. (Важная задача.) Пусть a взаимно просто с m. Тогда числа a, 2a, 3a,.,
(m-1)a дают все ненулевые остатки по модулю m.

10. (Линейные сравнения) а) Опишите все решения сравнения [pic], если
НОД(a,m)=1. (когда существуют решения, сколько их)
б) Что можно сказать в общем случае, когда (НОД(a,m)=d)?

11. а) Пусть p простое число и a не кратно p. Докажите, что [pic].
(Указание - воспользуйтесь задачей 9)
б) (Малая теорема Ферма) Докажите, что [pic].

12. а) Найдите остаток деления 8900 на 29.
б) Докажите, что 3003000-1 делится на 1001.

13. Пусть p>5 простое, не равно 2 и 5. Докажите, что число [pic] кратно p.



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

14. Натуральное число при делении на 25 дает в остатке 24, а при делении на
4 дает в остатке 3. Найдите наименьшее такое число. Найдите все такие
числа, меньшие 1000.

Теорема. (Китайская теорема об остатках (сокращенно КТО) для двух модулей.)
Пусть m1 и m2 взаимно простые числа, m=m1m2,. Тогда для любых [pic] и
[pic], существует единственное [pic] такое, что [pic] и [pic].

В следующих двух задачах даны два доказательства КТО.
15. (Подсчет по количеству) а) Докажите от противного, что r -
единственное.
б) Докажите, что r существует.
в) Придумайте и докажите КТО для большего числа модулей.

16. (Конструктивное доказательство). Докажите, что одно из чисел r1, r1+m1,
r1+2m1,..,r1+(m1-1)m1 дает остаток r2 по модулю m2. Докажите КТО для двух
модулей.
б) Докажите общую КТО этим методом.

17. Найдите все решения системы сравнений а) [pic] б)[pic]
18. Сколько остатков являются решениями сравнения [pic]


Еще задачи.
19. (Теорема Вильсона). Какой остаток может давать [pic] при делении на p?
(Указание. Сначала угадайте ответ. Для доказательства попробуйте разбить
остатки на пары с произведением 1)
20. Докажите, что для любого простого p>2 числитель дроби [pic] делится
на p.

21. (Московская математическая олимпиада 2005) Дана последовательность
[pic]. Существуют ли 5 идущих подряд её членов, делящихся на 2005?

22. У Сени есть бесконечно много купюр двух видов - a и b рублей, причем
НОД(a,b)=1. Докажите, что Сеня может заплатить этими монетами любую,
достаточно большую сумму без сдачи.

23. Про натуральное число a известно, что [pic]. Докажите, что найдется
натуральное b такое, что [pic].