сайты - меню - вход - но­во­сти


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

Сюжет 3.

В этом сю­же­те раз­ре­ша­ет­ся ис­поль­зо­вать (без обос­но­ва­ния) так на­зы­ва­е­мую малую тео­ре­му Ферма, гла­ся­щую, что для вся­ко­го це­ло­го числа а и про­сто­го на­ту­раль­но­го числа p спра­вед­ли­во со­от­но­ше­ние «aa 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 .

1

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