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

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

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

Листок 4. Малая теорема Ферма

По определению, a сравнимо с b по модулю n, если a − b = kn, где k — целое число. Обозначается это так: a ≡ b (mod n).
1.
Докажите, что если a ≡ b (mod n) и c ≡ d (mod n), то:
а)
a + c ≡ b + d (mod n);
б)
a − c ≡ b − d (mod n);
в)
ac ≡ bd (mod n);
г)
для любого натурального m верно am ≡ bm (mod n).
2.
Докажите, что:
а)
если k ≠ 0 и ka ≡ kb (mod kn), то a ≡ b (mod n);
б)
если ka ≡ kb (mod n) и числа k, n взаимно просты, то a ≡ b (mod n).
3.
Найти остаток от деления
а)
числа 21000 на 7;
б)
числа 2012005 на 17.
4.
Докажите, что для любого целого a:
а)
a2 − a делится на 2;
б)
a3 − a делится на 3;
в)
a5 − a делится на 5.
5.
Пусть p — простое число, а k — целое число, не делящееся на p. Рассмотрим остатки от деления на p чисел k, 2k, 3k, …, (p − 1)k. Докажите, что:
а)
среди этих остатков нет нулевого;
б)
все эти остатки разные;
в)
это все ненулевые остатки от деления на p.
6.
Используя задачу 5, докажите, что если целое число k не кратно простому числу p, то kp−1 дает остаток 1 при делении на p.