Тема ЮМШ (олимпиада Юношеской Математической Школы)

ЮМШ - задания по годам → .02 ЮМШ 2020

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела юмш (олимпиада юношеской математической школы)

Разделы подтемы ЮМШ - задания по годам

ЮМШ до 2020

ЮМШ 2020

ЮМШ 2021

ЮМШ 2022

ЮМШ 2023

ЮМШ 2024

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#108600

На $n$ карточках написали по $k$ чисел, сумма на каждой карточке равна $m$ . Оказалось, что любой набор из $k$ неотрицательных чисел с суммой 1 можно получить, уменьшив некоторые числа на одной из карточек (наборы неупорядоченные). Пусть $a(n,k)$ — наименьшее $m$ , при котором это возможно.

1. Найдите $a(2,2)$ .

2. Докажите, что найдется $n$ такое, что $a(n,10100) ≤1+ 10−100$ .

3. Докажите, что $a(2,4)<√3-$ .

4. Ограничена ли последовательность $a(2,k)− a(1,k)$ ?

Источники: ЮМШ-2020, сюжет 1 (см. yumsh.ru)

Подсказки к задаче

Пункт 1, подсказка 1

Для начала попробуйте подобрать такие наборы, у нас 2 карточки, на каждой по 2 числа.

Пункт 1, подсказка 2

Убедитесь, что наборы (1; 1/4) и (3/4; 1/2) подходят. Попробуйте провести оценку. Например, обязательна ли нам единица в одной из пар?

Пункт 1, подсказка 3

Набор с единицей должен быть, поскольку нам надо мажорировать (1; 0). Какой еще набор нам надо мажорировать и какие тогда карточки должны быть?

Пункт 1, подсказка 4

Нам также надо мажорировать (1/2; 1/2). Для этого на одной из карточек должны быть числа, большие 1/2. Что будет, если рассмотренные пары чисел с карточек совпадают?

Пункт 1, подсказка 5

Тогда их сумма — 3/2. Если это разные пары, посмотрите на набор (3/4; 1/4).

Пункт 1, подсказка 6

Для того, чтобы набор (1; x) его мажорировал, x должен быть больше либо равен 1/4. Осталось понять, какой набор нужен, чтобы набор с парой чисел, больших 1/2, мажорировал, и убедиться, что указанный пример подходит.

Пункт 2, подсказка 1

Попробуйте посмотреть, как можно записать число 1 + 10⁻¹⁰⁰ в виде суммы дробей.

Пункт 2, подсказка 2

Давайте добавим, что дроби у нас будут положительные и со знаменателем 10²⁰⁰. Что можно сказать о количестве таких записей?

Пункт 2, подсказка 3

Оно будет конечно. Тогда давайте обозначим его за n и запишем на карточки все соответствующие наборы. Подойдут ли нам такие карточки?

Пункт 2, подсказка 4

Рассмотрите произвольный набор с суммой 1 и замените в нем каждое число на ближайшую сверху дробь со знаменателем 10²⁰⁰. На сколько при округлении увеличится сумма?

Пункт 2, подсказка 5

Сумма увеличится не более, чем на 10¹⁰⁰ ⋅ (1 / 10²⁰⁰) = (1 / 10¹⁰⁰). Что мы тогда получим?

Пункт 2, подсказка 6

Мы получим один из наших наборов или аналогичный набор с меньшей суммой. Как можно во втором случае преобразовать набор, чтобы получить числа с одной из карточек?

Пункт 2, подсказка 7

Можем увеличить числители некоторых дробей, чтобы сумма стала равной 1 + 10⁻¹⁰⁰. Осталось сделать вывод про мажорируемость.

Пункт 3, подсказка 1

Давайте сначала придумаем какой-то пример и прикинем возможные значения a(2,4).

Пункт 3, подсказка 2

Рассмотрите наборы (21/34; 1/2; 1/3; 1/4) и (1; 13/24; 13/68; 13/102). Чему равны их суммы? А чему равен √3?

Пункт 3, подсказка 3

Сумма в каждом наборе меньше 1,71, а √3 = 1,73... . Попробуйте проверить, что эта пара наборов мажорирует все четверки.

Пункт 3, подсказка 4

Пусть у нас есть упорядоченная тройка с суммой x. Что можно сказать про её среднее и меньшее числа?

Пункт 3, подсказка 5

Среднее число будет не больше x/2, а малое — не больше x/3. Распространите это наблюдение на четвёрки. Посмотрите на наборы, которые мы привели ранее.

Пункт 3, подсказка 6

На самом деле, аналогичное верно для четвёрок. Если максимальное число в четверке больше 21/34, то второе по величине будет не больше 13/34. Продолжите оценки на числа четвёрки и докажите, что приведённые 2 набора действительно мажорируют все четвёрки.

Пункт 4, подсказка 1

Нам нужно найти разность между двумя значениями функции a. Давайте для начала попробуем посчитать a(1,k). Вспомните, что мы знаем из прошлых пунктов о числах l≤k.

Пункт 4, подсказка 2

Для каждого такого l должна быть карточка, на которой l-ое по величине число не меньше, чем 1/l. Предположим, что такая карточка одна. Что можно сказать о сумме её чисел?

Пункт 4, подсказка 3

Сумма ее чисел будет не меньше 1 + 1/2 + ... + 1/k. А подойдет ли нам такая карточка?

Пункт 4, подсказка 4

Заметим, что в наборе с единичной суммой l-ое по величине число не больше 1/l, следовательно, карточка подойдет. А чему тогда будет равно a(1,k)?

Пункт 4, подсказка 5

a(1,k) = 1 + 1/2 + ... + 1/k. Давайте теперь рассмотрим произвольную пару натуральных чисел l < k и попробуем предъявить 2 набора, которые будут зависеть от k и l и мажорировать все наборы с единичной суммой.

Пункт 4, подсказка 6

Рассмотрим произвольный набор a₁ > a₂ > ... > aₖ с единичной суммой. Заметим, что для любого i aᵢ ≤ 1/i. Какой набор тогда будет мажорировать любой набор с единичной суммой, при условии, что все числа не превосходят 1/l?

Пункт 4, подсказка 7

Можно взять такой набор: в нем l раз встретится дробь 1/l, а также будут числа 1/(l + 1), 1/(l + 2), ... , 1/k. Осталось рассмотреть случай, когда a₁ > l. Попробуйте оценить сумму остальных aᵢ.

Пункт 4, подсказка 8

Это единичный набор, следовательно, a₂ + a₃ + ... + aₗ₊ᵢ < 1 - 1/l. Оцените aₗ₊ᵢ.

Пункт 4, подсказка 9

aₗ₊ᵢ ≤ (l - 1) / (l(l + i - 1)). Как, пользуясь этим соотношением, можно задать второй набор?

Пункт 4, подсказка 10

Второй набор будет следующего вида: (1; 1/2; ... ; 1/l; (l - 1) / l²; (l - 1) / (l(l + 1)); ... ; (l - 1) / (l(k - 1)). Попробуйте доказать, что разность между a(1,k) и наибольшей суммой одного из этих наборов может быть сколь угодно большой при правильном выборе l и k.

Пункт 4, подсказка 11

Посчитайте разницу между суммой с первой карточки и a(1,k).

Пункт 4, подсказка 12

Получим 1 + 1/2 + ... + 1/(l - 1) - (l - 1)/l. Заметьте, что эта сумма больше 1/2 + ... + 1/(l - 1).

Пункт 4, подсказка 13

При достаточно больших l эта сумма будет сколь угодно большой. Осталось посмотреть на вторую карточку.

Пункт 4, подсказка 14

У Вас должно получиться, что разность между a(1,k) и суммой чисел со второй карточки больше (1/l) ⋅ (1/(l+1) + 1/(l+2) + ... + 1/(k-1)) - 1. Осталось понять, ограниченно ли это число, и сделать соответствующие выводы.

Показать ответ и решение

1. Пример: наборы ( $1;14$ ) и ( $34;12$ ).

Оценка. Ясно, что должен быть набор, содержащий 1, чтобы мажорировать ( $1;0$ ), и набор, в котором оба числа больше $12$ , чтобы мажорировать $( ) 12;12$ . Если это одна и та же пара, то сумма уже $32$ . Если разные, то посмотрим на набор $( ) 34;14$ : чтобы набор $(1;x)$ мажорировал его, должно быть $x ≥ 14$ , а чтобы набор с парой чисел, больших $12$ мажорировал — это должен быть набор, как минимум $( ) 34;12$ . Легко видеть также, что указанный набор подходит.

_________________________________________________________________________________________________________________________________________________________________________________

2. Рассмотрим все возможные способы записать число $1+ 10− 100$ в виде суммы положительных рациональных дробей со знаменателем $10200$ (не обязательно несократимых). Очевидно, что это количество конечно, его и обозначим за $n$ — записав все соответствующие наборы на карточки, убедимся, что такой набор карточек подходит. Действительно, рассмотрим любой набор с единичной суммой. Заменим в нём каждое число на ближайшую сверху дробь со знаменателем $10200$ . При таком округлении сумма увеличится не более, чем на $10100⋅--1200 = 1∕10100 10$ , значит получится один из наших наборов или аналогичный набор с меньшей суммой. Произвольно увеличив числители некоторых дробей так, чтобы сумма стала равной $1+10−100$ , мы превратим набор в числа на одной из карточек, которая, таким образом, мажорирует исходный набор с единичной суммой.

_________________________________________________________________________________________________________________________________________________________________________________

3. Рассмотрим, например, следующую пару наборов:

( ) ( ) 2314,12,13,14 и 1,1334,1638, 11032 .

Сумма в каждом равна $324704-$ , это даже меньше,чем 1,71 , а $√3-= 1,73...$ . Проверим, что эта пара наборов мажорирует все нужные четвёрки. Ясно (*), что в упорядоченной тройке с суммой $x$ среднее число - не больше, чем $x2$ , а малое - не больше, чем $x3$ ; аналогичное верно для четвёрок. Действительно, если максимальное число в четвёрке больше $2314$ , то второе по величине - не больше,чем $1334$ , третье не больше $1638$ а самое маленькое не больше $11302$ , значит такая четверка мажорируется вторым набором. Аналогично, если максимальное число не больше, чем $21 34$ , то оно мажорируется первым набором.

_________________________________________________________________________________________________________________________________________________________________________________

4. Вычислим $a(1,k)$ . Как уже отмечалось, для всякого $l≤ k$ должна быть карточка, в которой $l$ -ое по величине число не меньше, чем $1 l$ . Если карточка всего одна, то сумма на этой карточке, таким образом, не меньше $1 1 1+ 2 + ...+ k$ . С другой стороны, карточка $( 1 1) 1,2,...,k$ , очевидно, подходит, т.к. в наборе с единичной суммой $l$ -ое по величине число не больше $1 -l$ , так что $1 1 a(1,k)=1 +2 +...+k$ . Теперь рассмотрим произвольную пару натуральных чисел $l<k$ , соотношение между которыми мы уточним позднее, и предъявим два набора, вдвоём мажорирующих все наборы с единичной суммой: а именно

1 1 1 --1- -1---1-- 1 (◟l,l,.◝◜..,l◞,l+ 1,l+2,l+ 3,...,k) lраз

( 1 1 1 l− 1 l− 1 l− 1 l− 1 ) 1,2,3,...,l,-l2-,l(l+1),l(l+2),...,l(k−-1)

Действительно, рассмотрим любой упорядоченный по убыванию набор ( $a1 ≥ a2 ≥ ...≥ ak$ ) с единичной суммой. Ясно, что $ai ≤1∕i$ при любом $i$ и поэтому первая карточка мажорирует любой набор с единичной суммой, в котором все числа не превосходят $1∕l$ .

Пусть, напротив, $a1 > 1l$ . Тогда для любого $i$ имеем

a2+ a3+ ...+al+i < 1− 1, откуда al+i ≤--l−-1--. l l(l+ i− 1)

Поэтому любой набор с $1 a1 > l$ мажорируется второй из наших карточек.

Осталось убедиться, что разность между $a(1,k)$ и максимумом из сумм в этих двух наборах может быть сделана (при подходящем выборе $l$ и $k$ ) сколь угодно большой. Действительно, сумма на первой карточке отличается от $a(1,k)$ на

1 1 l− 1 1 1 1+ 2 +...+l−-1 −--l-> 2 + ...+ l−-1

и эта величина при достаточно больших $l$ может быть сделана, как известно, сколь угодно большой. Теперь зафиксируем произвольное $l$ и посмотрим на вторую карточку: сумма чисел на ней меньше, чем $a(1,k)= 1+ 12 + ...+ 1k$ , на

( ) --1-+ -1--+⋅⋅⋅+ 1− l− 1 1 +--1-+ ...+ -1-- = l+ 1( l+2 k l l) l+ 1 k−( 1 ) = 1 -1--+ -1--+⋅⋅⋅+--1- + 1− l−21> 1 -1--+--1-+ ...+ -1-- − 1 l l+ 1 l+2 k − 1 k l l l+1 l+ 2 k− 1

Поскольку выражение в скобках при фиксированном $l$ и неограниченном $k$ может быть сделано сколь угодно большим, то можно выбрать $k$ так, что эта разность будет больше разности между $a(1,k)$ и первой суммой, которая одним лишь выбором $l$ может быть сделана сколь угодно большой для произвольного $k> l$ . Утверждение доказано, последовательность из условия не ограничена.

Ответ:

1. $5 4$

2. что и требовалось доказать

3. что и требовалось доказать

4. нет

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#108601

Две окружности, вписанные в угол с вершиной $R$ , пересекаются в точках $A$ и $B$ . Через $A$ проведена прямая, пересекающая меньшую окружность в точке $C$ , а большую — в точке $D$ . Оказалось, что $AB =AC = AD$ .

1. Пусть $C$ и $D$ совпали с точками касания окружностей и угла. Докажите, что угол $R$ прямой.

2. Пусть $C$ и $D$ совпали с точками касания окружностей и угла. Чему может быть равен угол $ADR$ ?

3. Докажите, что если $∠R$ прямой, то $C$ и $D$ совпадают с точками касания окружностей и угла.

4. Какие значения может принимать угол $RAO1$ , где $O1$ — центр меньшей окружности?

Источники: ЮМШ-2020, сюжет 2 (см. yumsh.ru)

Подсказки к задаче

Пункт 1, Подсказка 1

Посмотрите внимательно на рисунок. Мы что-то знаем про △BCD. Да, действительно, он прямоугольный! Далее попробуйте посчитать сумму ∠ACR + ∠CDR.

Пункт 1, Подсказка 2

Заметим, что ∠ACR, как и ∠RDC, являются углами между хордой и касательной. И правда! А значит ∠ACR + ∠RDC = (∠ABC + ∠ABD) / 2 = 180° / 2 = 90°

Пункт 2, Подсказка 1

Мы знаем что △DRA равнобедренный, поэтому давайте попробуем найти ∠DRA. Посмотрим внимательно на картинку. Ага! Да ведь она симметрична относительно биссектрисы угла! Значит ∠DRA = ∠CRB, кроме того мы что-то знаем про △ARB.

Пункт 3, Подсказка 1

На рисунке много окружностей, было бы неплохо сделать инверсию. Да, действительно, сделаем инверсию c центром в A и радиусом AB. После инверсии окружности перейдут в 2 перпендикулярные прямые, а перпендикулярные прямые перейдут в пару окружностей, вписанных в угол.

Пункт 3, Подсказка 2

Как же теперь доказать, что (⋅)C и D совпадают с точками касания окружностей и угла? Можно ввести систему координат (удобнее будет если она будет связана с прямым углом) и посчитать координаты всех точек, тем самым доказав, что точки совпадают.

Пункт 4, Подсказка 1

Да-да, снова необходимо сделать инверсию, а также не забыть замечательное свойство углов при инверсии!

Показать ответ и решение

$PIC$

Треугольник $BCD$ прямоугольный (медиана — половина гипотенузы). Значит, сумма дуг $AC$ и $AD$ соответствующих окружностей равна $2⋅90∘ = 180∘$ , а сумма соответствующих углов между хордой и касательной $CDR + DCR = 90∘$ , поэтому $∠R = 90∘$ .

_________________________________________________________________________________________________________________________________________________________________________________

$PIC$

Треугольник $RAB$ равносторонний $− RA = CD ∕2 =AB$ и $RA = RB$ по симметрии. Отсюда симметричные отрезки $RA,RB$ образуют со сторонами углы, равные $90∘−60∘-= 15∘ 2$ и этому же равен $∠ADR$ (т.к. $AD = AR$ ).

_________________________________________________________________________________________________________________________________________________________________________________

3. Выполним инверсию $i$ относительно окружности с центром в $A$ и радиусом $AB$ . Имеем $i(B )=B,i(C)= C,i(D)= D$ , и наши две окружности превращаются в прямые $BC,BD$ , образующие прямой угол, а стороны исходного угла — в пару окружностей, вписанных в этот угол, перпендикулярных друг другу (как и соответствующие прямые до инверсии) и пересекающихся в точках $A,S = i(R)$ .

$PIC$

Вычислим отношение их радиусов — это легко делается применением теоремы Пифагора к треугольнику $AO1O2$ со сторонами $r1,r2,√2(r2− r1)$ (здесь $O1,O2$ — центры новых окружностей, $r1 < r2$ - радиусы). Получается $rr21 = 2+ √3$ ; будем считать $r1 = 1,r2 = 2+ √3$ .

Введём связанную с нашим прямым углом систему координат, тогда центры имеют координаты $(1,1)$ и $(2+ √3,2+√3-)$ , а точки касания — $X1 = (1,0),X2 = (0,1),Y1 = (0,2+ √3),Y2 = (2+ √3,0)$ . Середина $X1Y1$ — это $( √-) 12,1+ 23$ , и, считая расстояния от неё до $O1$ и $O2$ , убеждаемся, что это точка пересечения наших окружностей,как и середина $X2Y2$ . Значит, эти середины — точки $A,R$ . Поскольку $A$ не лежит на биссектрисе угла, то прямая, из которой наш угол высекает отрезок с серединой $A$ , единственна, так что соответствующая пара точек $Xi,Yi$ совпадает с парой $C,D$ .

_________________________________________________________________________________________________________________________________________________________________________________

$PIC$

Исполним ту же самую инверсию, что и в предыдущем пункте, вновь получим прямой угол и вписанную в него пару окружностей. Прямая $AS$ пересекает стороны угла под 45 градусов, значит, то же делает эта же прямая $(i(AS)= AR =AS )$ с исходными окружностями. Поэтому и угол $RAO$ ( $O$ — центр меньшей окружности) равен $90∘− 45∘ = 45∘$ .

Ответ:

1. что и требовалось доказать

2. $15∘$

3. что и требовалось доказать

4. $∘ 45$

Ошибка.
Попробуйте повторить позже

Задача 3#108602

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

$p a− a$ делится на $p$ без остатка.

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

a1+b1,a2+b2,...,ap−1+ bp−1

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

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

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

3. Докажите, что искомая пара найдётся при $a= 4,b= 7$ .

4. Докажите, что искомая пара найдётся, если $a= 2,b= 3$ , а $p−1 -2-$ - простое.

Источники: ЮМШ-2020, сюжет 3 (см. yumsh.ru)

Подсказки к задаче

Подсказка 1

Для первых трёх пунктов достаточно использовать малую теорему Ферма с тем лишь дополнением, что во втором и третьем пункте нужно разобрать отдельно случаи с малыми значениями p, а вот в 4 пункте всё интереснее!

Подсказка 2

Перейдём к последнему пункту. Докажем методом "от противного". Будем рассматривать порядки 2 и 3 по модулю p. Чему они могут быть равны?

Подсказка 3

Действительно, варианты: 1, 2, q, 2q = p - 1. Неразобранный случай остался 2q. В нашем предположении в последовательности должны встретиться по разу все ненулевые остатки. Вот бы теперь какое-нибудь утверждение про остатки придумать. Пусть у нас есть два числа меньших q (q > 2), числа x и k. При этом x и остаток kx от деления на q имеют разную чётность. Можем ли мы тогда определить k относительно q? Какое можем получить отсюда следствие?

Подсказка 4

Действительно, k = q-1. Осталось подумать над следствием, и мы уже близки к финалу!

Подсказка 5

Для простого q, нечётного k такого, что 2q не делится на (k+1) найдется l, что остатки чисел l, kl по модулю 2q лежат строго между 0 и q. Во-первых, это не всем известный факт и по-хорошему требует доказательства. Во-вторых, применим это следствие, а дальше изучим сумму по k от 1 до (p - 1) чисел (2^k + 3^k)^(l+r) по модулю p.

Показать доказательство

1. По МТФ $4p−1+ 9p−1 ≡2$ , но в то же время и $p−1 p−-1 4 2 + 9 2 = 2p−1+ 3p−1 ≡ 2$ .

_________________________________________________________________________________________________________________________________________________________________________________

2. Если $p= 3$ , то всё ясно. Если $3(p−1)∕2 ≡ 1$ , то остальное как в предыдущем пункте. Иначе же $3(p−1)∕2 ≡ −1$ . Например, потому что из МТФ $3p− 1 ≡ 1$ , значит,

(3p−21− 1) (3 p−21-+1):p

Тогда

p−21+2 p−21 +2 1 1 4 + 3 ≡16− 9≡ 7= 4 + 3.

______________________________________________________________________________________________________________________________________________________

3. Случаи $p≤7$ разбираются руками. Дальше, аналогично предыдущим пунктам, если $7(p−1)∕2 ≡ 1$ , то всё ясно. Иначе $7(p−1)∕2 ≡− 1$ , а тогда для $k =1,...,p−1 2$

k k p−1+k p−1+k k p−1+k k 4 + 7 + 4 2 +7 2 ≡ 4 + 4 2 ≡2 ⋅4 .

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

p+1 2(4+ 42+ ...+4p−21) =2⋅ 4-2-− 4 ≡ 4⋅(4p−21− 2) ≡ 4⋅−1⁄≡ 0 4− 1 3 3

_________________________________________________________________________________________________________________________________________________________________________________

4. Предположим, что все остатки различны. Посмотрим на порядки 2 и 3 по модулю $p$ . (Порядок $a$ по модулю $p$ - минимальное натуральное $k$ такое, что $ak− 1$ (или числитель соответствующей несократимой дроби,если $a$ - дробь) кратно $p$ ; это $k$ мы будем обозначать $ordp(a)$ .) По МТФ они могут быть равны лишь $1,2,q,2q =p− 1$ . Первые два случая проигнорируем, а случаи, когда хотя бы один из порядков равен $q$ , идентичны разобранным в пунктах 1 и 3 . Пусть порядки $2q$ , в частности все остатки $2,22,...,2p−1$ , различны (иначе, если $2a$ и $2b$ дают одинаковые остатки, то $2a− 2b$ , а значит и $2a−b− 1$ , кратно $p$ , но $a− b< p− 1$ ) и найдётся такое $m$ , что $2m = 3$ . Отметим также, что в этом случае $2q =3q =−1$ , так что если при некотором $k$ имеем $2k +3k = 0$ , то и $( ) 2k±q +3±q = − 2k+ 3k = 0$ , так что нарушается условие различности остатков. Поэтому в нашей последовательности встречаются по разу все ненулевые остатки.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма 1. Пусть $q >2$ простое и $k <q$ таково, что для любого $x= 1,2,...,q − 1$ число $x$ и остаток $kx$ от деления на $q$ имеют разную чётность. Тогда $k= q− 1$ .

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Теперь изучим сумму $∑p−1(2k+ 3k)r+l k=1$ по модулю $p$ . С одной стороны, выражение в скобках пробегает все ненулевые остатки, а число $r+ l<q +q$ не кратно $p − 1= 2q = ord(2)$ , так что эту сумму можно посчитать как сумму геометрической прогрессии с неединичным знаменателем $r+l 2$ , и она равна нулю.

Посчитаем эту же сумму другим способом. Раскрыв все скобки по биному, перегруппировав слагаемые и переставив множители в показателях степеней, мы получим сумму геометрических прогрессий вида $i ∑ (i r+l−i)k Cr+l 23$ . Докажем, что ровно одна из этих прогрессий постоянна, а значит, ровно одно из указанных выражений ненулевое (тут надо отметить, что $r,l< q$ , так что $r +l< 2q = p− 1$ , поэтому появляющиеся биномиальные коэффициенты не кратны $p$ ). Это даст требуемое противоречие.

Действительно, при $i= r$ получаем, учитывая $m 2 = 3$ , что $rr+l−r r+ml 23 = 2 = 1$ , т.к. $r+ ml$ делится на $2q$ . С другой стороны, если $r+sr+l−r−s 2 3 =1$ , при некотором $s∈ [−r,l]$ то, деля, получаем $s−s 23 = 1$ то есть $s (2∕3) = 1$ . Получаем, что $ordp(2∕3)≤max(r,l)< q$ , значит $ordp(2∕3)$ равен 1 или 2 , что может быть лишь при $p= 5$ ; этот случай проверяется непосредственно.

Предыдущая подтема

Следующая подтема