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

Кружок для 9-11 классов

Занятие 5. Малая теорема Ферма

Теорема 1. (малая теорема Ферма). Если p — простое число, k — целое и НОД(k,p) = 1, то \[k^{p-1} \equiv 1 \pmod p.\]

Теорема 2. (малая теорема Ферма). Если p — простое число, a — целое , то \[a^{p} \equiv a \pmod p.\]

1.

Найдите остатки от деления на 83 чисел:

a)

\(9^{82}\);

б)

\(9^{84}\);

в)

\(9^{88}\);

г)

\(9^{165}\);

д)

\(9^{100!}\);

2.

Найдите:

a)

\(3^{2015} \pmod {31}\);

б)

\(7^{600} \pmod {31}\).

3.

Будет ли простым число:

a)

\(28^{1013} + 1013^{28}\);

б)

\(1093^{1012} + 1012\)?

4.

Пусть n — натуральное число, не кратное 13. Докажите, что либо \(n^6 - 1\), либо \(n^6 + 1\) делится на 13.

5.

a)

Докажите, что \(13^{160} - 1\) делится на 187.

б)

Докажите, что \(300^{480} - 1\) делится на 1001.

6.

Докажите, что \(m^{31} n - m n^{31}\) кратно 14322 при любых целых m и n.

7.

Пусть p и q — различные простые числа. Докажите, что \(p^q + q^p \equiv {p + q} \pmod {pq}\).

8.

Вам была доказана вторая теорема для натуральных a. Опираясь на это, докажите её для всех целых a.

9.

Если \(k \cdot a \equiv k \cdot b \pmod {n}\) и числа k, n взаимно просты, то \(a \equiv b \pmod n\).

10.

Докажите, что первая и вторая теорема равносильны, то есть если верна одна из них, то верна и другая.