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

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

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

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 верно a^m ≡ b^m (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:

а)

a² − a делится на 2;

б)

a³ − a делится на 3;

в)

a⁵ − a делится на 5.

5.

Пусть p — простое число, а k — целое число, не делящееся на p. Рассмотрим остатки от деления на p чисел k, 2k, 3k, …, (p − 1)k. Докажите, что:

а)

среди этих остатков нет нулевого;

б)

все эти остатки разные;

в)

это все ненулевые остатки от деления на p.

6.

Используя задачу 5, докажите, что если целое число k не кратно простому числу p, то k^p−1 дает остаток 1 при делении на p.