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

Задания

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

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

Сюжет 3

Миша взял простое число 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=3,$ то всё ясно. Если $3 в степени левая круглая скобка дробь: числитель: левая круглая скобка p минус 1 правая круглая скобка , знаменатель: 2 конец дроби правая круглая скобка \equiv 1 левая круглая скобка \bmod p правая круглая скобка ,$ то по Малой Теореме Ферма

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

Иначе же $3 в степени левая круглая скобка дробь: числитель: левая круглая скобка p минус 1 правая круглая скобка , знаменатель: 2 конец дроби правая круглая скобка \equiv минус 1 .$ Например, потому что из МТФ $3 в степени левая круглая скобка p минус 1 правая круглая скобка \equiv 1,$ значит,

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

Тогда

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

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

Классификатор: Алгебра: числа. Делимость, признаки делимости, Методы алгебры. Преобразования выражений

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

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

3.1 Пусть p  =  7. Приведите пример таких $a, b \not \vdots7,$   при которых искомой пары не будет.

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