РЕШУ ОЛИМП: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 21 № 1980 Добавить в вариант

Сюжет 3.

В этом сюжете разрешается использовать (без обоснования) так называемую малую теорему Ферма, гласящую, что для всякого целого числа а и простого натурального числа p справедливо соотношение «a−a^p делится на p без остатка».

Итак, $p больше 2$   — простое число. Маша должна понять, есть ли среди чисел

$a в степени левая круглая скобка 1 правая круглая скобка плюс b в степени левая круглая скобка 1 правая круглая скобка ,$ $\quad a в квадрате плюс b в квадрате ,$ $\quad \ldots,$ $\quad a в степени левая круглая скобка p минус 1 правая круглая скобка плюс b в степени левая круглая скобка p минус 1 правая круглая скобка$

значения, дающие одинаковые остатки от деления на p.

3.2 Пусть a  =  4, b  =  3. Докажите, что найдётся искомая пара, содержащая одно из крайних чисел.

Спрятать решение

Решение.

Случаи $p меньше или равно 7$ разбираются руками. Дальше, аналогично предыдущим пунктам, если $7 в степени левая круглая скобка дробь: числитель: левая круглая скобка p минус 1 правая круглая скобка , знаменатель: 2 конец дроби правая круглая скобка \equiv 1,$ то всё ясно. Иначе $7 в степени левая круглая скобка дробь: числитель: левая круглая скобка p минус 1 правая круглая скобка , знаменатель: 2 конец дроби правая круглая скобка \equiv минус 1,$ а тогда для $k=1, \ldots, дробь: числитель: p минус 1, знаменатель: 2 конец дроби ,$ получаем

$4 в степени левая круглая скобка k правая круглая скобка плюс 7 в степени левая круглая скобка k правая круглая скобка плюс 4 в степени левая круглая скобка дробь: числитель: p минус 1, знаменатель: 2 конец дроби плюс k правая круглая скобка плюс 7 в степени левая круглая скобка дробь: числитель: p минус 1, знаменатель: 2 конец дроби плюс k правая круглая скобка \equiv 4 в степени левая круглая скобка k правая круглая скобка плюс 4 в степени левая круглая скобка дробь: числитель: p минус 1, знаменатель: 2 конец дроби плюс k правая круглая скобка \equiv 2 умножить на 4 в степени левая круглая скобка k правая круглая скобка .$

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

$2 левая круглая скобка 4 плюс 4 в квадрате плюс \ldots плюс 4 в степени левая круглая скобка дробь: числитель: p минус 1, знаменатель: 2 конец дроби правая круглая скобка правая круглая скобка =2 умножить на дробь: числитель: 4 в степени левая круглая скобка дробь: числитель: p плюс 1, знаменатель: 2 конец дроби правая круглая скобка минус 4, знаменатель: 4 минус 1 конец дроби \equiv дробь: числитель: 4, знаменатель: 3 конец дроби умножить на левая круглая скобка 4 в степени левая круглая скобка дробь: числитель: p минус 1, знаменатель: 2 конец дроби правая круглая скобка минус 2 правая круглая скобка \equiv дробь: числитель: 4, знаменатель: 3 конец дроби умножить на минус 1 \not \equiv 0 .$ $2 левая круглая скобка 4 плюс 4 в квадрате плюс \ldots плюс 4 в степени левая круглая скобка дробь: числитель: p минус 1, знаменатель: 2 конец дроби правая круглая скобка правая круглая скобка =2 умножить на дробь: числитель: 4 в степени левая круглая скобка дробь: числитель: p плюс 1, знаменатель: 2 конец дроби правая круглая скобка минус 4, знаменатель: 4 минус 1 конец дроби \equiv дробь: числитель: 4, знаменатель: 3 конец дроби умножить на левая круглая скобка 4 в степени левая круглая скобка дробь: числитель: p минус 1, знаменатель: 2 конец дроби правая круглая скобка минус 2 правая круглая скобка \equiv дробь: числитель: 4, знаменатель: 3 конец дроби умножить на минус$
$минус 1 \not \equiv 0 .$

Олимпиада Юношеской математической школы, 11 класс, 2 тур (заключительный), 2020 год

Классификатор: Алгебра: числа. Делимость, признаки делимости

Спрятать решение · Помощь

Тип 21 № 1979 Добавить в вариант

3.1 Пусть a  =  4, b  =  9. Докажите, что искомая пара найдётся.

Решение · Помощь