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

До­ка­за­тель­ство леммы 1. Под­став­ляя по­лу­ча­ем, что k чётно, а зна­чит kx все­гда чётно, тогда оста­ток kx имеет ту же чет­ность, что и не­пол­ное част­ное Те­перь под­став­ля­ем тогда и не­чет­но, то есть Те­перь под­став­ля­ем тогда и четно, то етсь Про­дол­жая это, до­хо­дим до ра­вен­ства

что не­воз­мож­но при зна­чит,

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

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

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

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

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

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

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

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

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

Дей­стви­тель­но, при по­лу­ча­ем, учи­ты­вая что так как де­лит­ся на 2q. С дру­гой сто­ро­ны, если при не­ко­то­ром то, деля, по­лу­ча­ем то есть По­лу­ча­ем, что

зна­чит, равен 1 или 2, что может быть лишь при этот слу­чай про­ве­ря­ет­ся не­по­сред­ствен­но.