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

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

Листок 5. Разные задачи

1.

Рассмотрите все числа вида 2ⁿ. Получатся ли все ненулевые остатки от деления этих чисел: а) на 7? б) на 11?

2.

Рассмотрите все числа вида 3ⁿ. Получатся ли все ненулевые остатки от деления этих чисел: а) на 17? б) на 23?

3.

Пусть целое число a не делится на простое число p. Рассмотрим последовательность остатков от деления a, a², …, aⁿ, … на p. Периодом этой последовательности называется такое наименьшее натуральное число T, что для любого n выполнено a^n+T ≡ aⁿ (mod p). Докажите, что: а) a^T ≡ 1 (mod p); б) p − 1 делится на T.

4.

Пусть простое число p является делителем числа вида a⁴ + a³ + a² + a + 1. Докажите, что тогда p = 5 или p = 5k + 1.

5.

Пусть f(a) = ^{ap − 1 − 1}/_p. Докажите, что f(ab) ≡ f(a) + f(b) (mod p).

6.

Пусть p — нечетное простое число. Докажите, что: а) если a² + 1 делится на p, то p = 4k + 1; б) если a²ⁿ + 1 делится на p, то p = 2^{n + 1}k + 1.

7.

Пусть p — простое число. Докажите, что: а) φ(p) = p − 1; б) φ(p^k) = p ^k − p^k−1.

8.

Пусть m и n — взаимно простые числа. Рассмотрим числа вида mx + ny, где 0 ≤ x < n и 0 ≤ y < m. Докажите, что:

а)

остатки от деления на mn у всех этих чисел разные;

б)

НОД(mx + ny, m) = НОД(y, m) и НОД(mx + ny, n) = НОД(x, n);

в)

φ(mn) = φ(m) φ(n).