Страница:
<< 241 242 243 244
245 246 247 >> [Всего задач: 2468]
|
|
|
Сложность: 4 Классы: 9,10,11
|
Пусть p – простое число и p > 5. Докажите,
что если разрешимо сравнение x4 + x3 + x2 + x + 1 ≡ 0 (mod p), то
p ≡ 1 (mod 5).
Выведите отсюда бесконечность множества простых чисел вида 5n + 1.
|
|
|
Сложность: 4 Классы: 9,10,11
|
Пусть
Докажите равенство φ(n) = n(1 – 1/p1)...(1 – 1/ps).
а) пользуясь мультипликативностью функции Эйлера;
б) пользуясь формулой включения-исключения.
Определение функции Эйлера φ(n) см. в задаче 60758.
|
[Тождество Гаусса]
|
|
Сложность: 4 Классы: 9,10,11
|
Докажите тождество Гаусса
φ(d ) = n. Определение функции φ(n) см. в задаче 60758.
|
[Теорема Эйлера]
|
|
Сложность: 4 Классы: 9,10,11
|
Теорема Эйлера. Пусть m ≥ 1 и (a,
m) = 1. Тогда aφ(m) ≡ 1 (mod m).
Докажите теорему Эйлера с помощью малой теоремы Ферма
а) в случае, когда m = pn;
б) в общем случае.
|
[Китайская теорема об остатках]
|
|
Сложность: 4 |
Докажите китайскую теорему об остатках:
Пусть целые числа m1, ..., mn
попарно взаимно просты, m = m1...mn, и a1, ..., an, A –
произвольные целые числа. Тогда существует ровно одно такое целое число x, что
x ≡ a1 (mod m1),
...
x ≡ an (mod mn)
и
A ≤ x < A + m.
Страница:
<< 241 242 243 244
245 246 247 >> [Всего задач: 2468]