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


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

Сюжет 3

Миша взял про­стое число p > 2 и вот-вот вы­пи­шет на доску в ряд числа

a в сте­пе­ни 1 плюс b в сте­пе­ни 1 , \quad a в квад­ра­те плюс b в квад­ра­те , \quad \ldots, \quad a в сте­пе­ни p в сте­пе­ни м инус в сте­пе­ни 1 плюс b в сте­пе­ни p в сте­пе­ни м инус в сте­пе­ни 1 .

Затем он хочет отыс­кать среди них пару чисел, да­ю­щих оди­на­ко­вые остат­ки от де­ле­ния на p.

3.4 До­ка­жи­те, что у него по­лу­чит­ся, если  дробь: чис­ли­тель: p минус 1, зна­ме­на­тель: 2 конец дроби   — про­стое, a  =  2 и b  =  3.

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

Ре­ше­ние.

Лемма 1. Пусть q боль­ше 2 про­стое u k мень­ше q та­ко­во, что для лю­бо­го x=1, 2, \ldots, q минус 1 число xu оста­ток kx от де­ле­ния на q имеют раз­ную чётность. Тогда k=q минус 1 .

До­ка­за­тель­ство леммы 1. Под­став­ляя x=1 по­лу­ча­ем, что k чётно, а зна­чит kx все­гда чётно, тогда оста­ток kx имеет ту же чет­ность, что и не­пол­ное част­ное  левая квад­рат­ная скоб­ка дробь: чис­ли­тель: k x, зна­ме­на­тель: q конец дроби пра­вая квад­рат­ная скоб­ка . Те­перь под­став­ля­ем x=2, тогда  левая квад­рат­ная скоб­ка дробь: чис­ли­тель: 2 k, зна­ме­на­тель: q конец дроби пра­вая квад­рат­ная скоб­ка мень­ше 2 и не­чет­но, то есть  левая квад­рат­ная скоб­ка дробь: чис­ли­тель: 2 k, зна­ме­на­тель: q конец дроби пра­вая квад­рат­ная скоб­ка =1. Те­перь под­став­ля­ем x=3, тогда 1 мень­ше или равно левая квад­рат­ная скоб­ка дробь: чис­ли­тель: 3 k, зна­ме­на­тель: q конец дроби пра­вая квад­рат­ная скоб­ка мень­ше 3 и  левая квад­рат­ная скоб­ка дробь: чис­ли­тель: 3 k, зна­ме­на­тель: q конец дроби пра­вая квад­рат­ная скоб­ка четно, то етсь  левая квад­рат­ная скоб­ка дробь: чис­ли­тель: 3 k, зна­ме­на­тель: q конец дроби пра­вая квад­рат­ная скоб­ка =2 . Про­дол­жая это, до­хо­дим до ра­вен­ства

 левая квад­рат­ная скоб­ка дробь: чис­ли­тель: левая круг­лая скоб­ка q минус 1 пра­вая круг­лая скоб­ка x, зна­ме­на­тель: q конец дроби пра­вая квад­рат­ная скоб­ка =q минус 2,

что не­воз­мож­но при k мень­ше или равно q минус 2, зна­чит, k=q минус 1.

След­ствие 1. Пусть q про­стое, k нечётное, k плюс 1 не крат­но 2q. Тогда най­дет­ся l такое, что у обоих чисел l, kl остат­ки по мо­ду­лю 2q стро­го между 0 и q.

До­ка­за­тель­ство. Дей­стви­тель­но, по­про­бу­ем в ка­че­стве l все числа от 1 до q минус 1. Пусть все пары l, kl не по­до­шли, то есть все kl имеют остат­ки по мо­ду­лю 2q, боль­шие q. Это зна­чит, что чётность остат­ка kl по мо­ду­лю q про­ти­во­по­лож­на чет­но­сти остат­ка kl по мо­ду­лю 2q (q  — нечётно), а она сов­па­да­ет с чет­но­стью l (т. к. k нечётно) и мы по­па­да­ем в усло­вия леммы.

Пе­рейдём к ре­ше­нию за­да­чи. Пред­по­ло­жим, что все остат­ки раз­лич­ны. По­смот­рим, на по­ряд­ки 2 и 3 по мо­ду­лю p. По МТФ они могут быть равны лишь 1, 2, q, 2 q=p минус 1 (по­ря­док a по мо­ду­лю p  — ми­ни­маль­ное на­ту­раль­ное k такое, что a в сте­пе­ни левая круг­лая скоб­ка k пра­вая круг­лая скоб­ка минус 1 (или чис­ли­тель со­от­вет­ству­ю­щей не­со­кра­ти­мой дроби, если a  — дробь) крат­но p, это k мы будем обо­зна­чать ord_p левая круг­лая скоб­ка a пра­вая круг­лая скоб­ка пра­вая круг­лая скоб­ка . Пер­вые два слу­чая про­игно­ри­ру­ем, а слу­чаи, когда хотя бы один из по­ряд­ков равен q иден­тич­ны разо­бран­ным в пунк­тах 1 и 3. Пусть по­ряд­ки 2q, в част­но­сти все остат­ки 2, 2 в квад­ра­те , \ldots, 2 в сте­пе­ни левая круг­лая скоб­ка p минус 1 пра­вая круг­лая скоб­ка раз­лич­ны (иначе, если 2a и 2b дают оди­на­ко­вые остат­ки, то 2 в сте­пе­ни левая круг­лая скоб­ка a пра­вая круг­лая скоб­ка минус 2 в сте­пе­ни левая круг­лая скоб­ка b пра­вая круг­лая скоб­ка , а зна­чит и 2 в сте­пе­ни левая круг­лая скоб­ка a минус b пра­вая круг­лая скоб­ка минус 1 крат­но p, но a минус b мень­ше p минус 1 пра­вая круг­лая скоб­ка и найдётся такое m, что 2 в сте­пе­ни левая круг­лая скоб­ка m пра­вая круг­лая скоб­ка =3 . От­ме­тим также, что в этом слу­чае 2 в сте­пе­ни левая круг­лая скоб­ка q пра­вая круг­лая скоб­ка =3 в сте­пе­ни левая круг­лая скоб­ка q пра­вая круг­лая скоб­ка = минус 1, так что если при не­ко­то­ром k имеем 2 в сте­пе­ни левая круг­лая скоб­ка k пра­вая круг­лая скоб­ка плюс 3 в сте­пе­ни левая круг­лая скоб­ка k пра­вая круг­лая скоб­ка =0, то и

2 в сте­пе­ни левая круг­лая скоб­ка k \pm q пра­вая круг­лая скоб­ка плюс 3 в сте­пе­ни левая круг­лая скоб­ка \pm q пра­вая круг­лая скоб­ка = минус левая круг­лая скоб­ка 2 в сте­пе­ни левая круг­лая скоб­ка k пра­вая круг­лая скоб­ка плюс 3 в сте­пе­ни левая круг­лая скоб­ка k пра­вая круг­лая скоб­ка пра­вая круг­лая скоб­ка =0,

так что на­ру­ша­ет­ся усло­вие раз­лич­но­сти остат­ков. По­это­му в нашей по­сле­до­ва­тель­но­сти встре­ча­ют­ся по разу все не­ну­ле­вые остат­ки.

Под­берём по след­ствию 1 такое 0 мень­ше l мень­ше q, что −ml при де­ле­нии на 2q имеет оста­ток мень­ше q, назовём этот оста­ток r, r плюс m l де­лит­ся на 2q.

Те­перь изу­чим сумму

\sum_k=1 в сте­пе­ни левая круг­лая скоб­ка p минус 1 пра­вая круг­лая скоб­ка левая круг­лая скоб­ка 2 в сте­пе­ни левая круг­лая скоб­ка k пра­вая круг­лая скоб­ка плюс 3 в сте­пе­ни левая круг­лая скоб­ка k пра­вая круг­лая скоб­ка пра­вая круг­лая скоб­ка в сте­пе­ни левая круг­лая скоб­ка r плюс l пра­вая круг­лая скоб­ка

по мо­ду­лю p. С одной сто­ро­ны, вы­ра­же­ние в скоб­ках про­бе­га­ет все не­ну­ле­вые остат­ки, а число r плюс l мень­ше q плюс q не крат­но p минус 1=2 q=ord_p левая круг­лая скоб­ка 2 пра­вая круг­лая скоб­ка , так что эту сумму можно по­счи­тать, как сумму гео­мет­ри­че­ской про­грес­сии с не­по­сто­ян­ным зна­ме­на­те­лем 2 в сте­пе­ни левая круг­лая скоб­ка r плюс l пра­вая круг­лая скоб­ка и она равна нулю.

По­счи­та­ем эту же сумму дру­гим спо­со­бом. Рас­крыв все скоб­ки по би­но­му, пе­ре­груп­пи­ро­вав сла­га­е­мые и пе­ре­ста­вив мно­жи­те­ли в по­ка­за­те­лях сте­пе­ней, мы по­лу­чим сумму гео­мет­ри­че­ских про­грес­сий вида

C_r плюс l в сте­пе­ни левая круг­лая скоб­ка i пра­вая круг­лая скоб­ка \sum левая круг­лая скоб­ка 2 в сте­пе­ни левая круг­лая скоб­ка i пра­вая круг­лая скоб­ка 3 в сте­пе­ни левая круг­лая скоб­ка r плюс l минус i пра­вая круг­лая скоб­ка пра­вая круг­лая скоб­ка в сте­пе­ни левая круг­лая скоб­ка k пра­вая круг­лая скоб­ка .

До­ка­жем, что ровно одна из этих про­грес­сий по­сто­ян­на, а зна­чит, ровно одно из ука­зан­ных вы­ра­же­ний не­ну­ле­вое (тут надо от­ме­тить, что r, l мень­ше q, так что r плюс l мень­ше 2 q=p минус 1, по­это­му по­яв­ля­ю­щи­е­ся би­но­ми­аль­ные ко­эф­фи­ци­ен­ты не крат­ны p). Это даст тре­бу­е­мое про­ти­во­ре­чие.

Дей­стви­тель­но, при i=r по­лу­ча­ем, учи­ты­вая 2 в сте­пе­ни левая круг­лая скоб­ка m пра­вая круг­лая скоб­ка =3, что 2 в сте­пе­ни левая круг­лая скоб­ка r пра­вая круг­лая скоб­ка 3 в сте­пе­ни левая круг­лая скоб­ка r плюс l минус r пра­вая круг­лая скоб­ка =2 в сте­пе­ни левая круг­лая скоб­ка r плюс m l пра­вая круг­лая скоб­ка =1, так как r плюс ml де­лит­ся на 2q. С дру­гой сто­ро­ны, если 2 в сте­пе­ни левая круг­лая скоб­ка r плюс s пра­вая круг­лая скоб­ка 3 в сте­пе­ни левая круг­лая скоб­ка r плюс l минус r минус s пра­вая круг­лая скоб­ка =1, при не­ко­то­ром s при­над­ле­жит левая квад­рат­ная скоб­ка минус r; l пра­вая квад­рат­ная скоб­ка то, деля, по­лу­ча­ем 2 в сте­пе­ни левая круг­лая скоб­ка s пра­вая круг­лая скоб­ка 3 в сте­пе­ни левая круг­лая скоб­ка минус s пра­вая круг­лая скоб­ка =1 то есть  левая круг­лая скоб­ка дробь: чис­ли­тель: 2, зна­ме­на­тель: 3 конец дроби пра­вая круг­лая скоб­ка в сте­пе­ни левая круг­лая скоб­ка s пра­вая круг­лая скоб­ка =1 . По­лу­ча­ем, что

\ord_p левая круг­лая скоб­ка дробь: чис­ли­тель: 2, зна­ме­на­тель: 3 конец дроби пра­вая круг­лая скоб­ка мень­ше или равно \max левая круг­лая скоб­ка r; l пра­вая круг­лая скоб­ка мень­ше q,

зна­чит, ord _p левая круг­лая скоб­ка дробь: чис­ли­тель: 2, зна­ме­на­тель: 3 конец дроби пра­вая круг­лая скоб­ка равен 1 или 2, что может быть лишь при p=5; этот слу­чай про­ве­ря­ет­ся не­по­сред­ствен­но.

1

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