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

Теория чисел на ЮМШ

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

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

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

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

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

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

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

Задача 1#83387

Цель этого сюжета — доказательство следующего утверждения:

Пусть $p$ — нечётное простое число. Докажите, что существует ровно $(p− 3)∕2$ упорядоченных четвёрок $(a,b,c,d)$ натуральных чисел, для которых $ab+ cd =p$ и $max(c,d)<min(a,b).$

Если $r$ — остаток по модулю $p,$ то назовём четвёрку ( $a,b,c,d$ ), удовлетворяющую условиям выше, $r$ -четверкой, если $c ≡ra$ (mod $p).$

1. Докажите, что если $r$ -четвёрка существует, то $r∈{2,3,...,p− 2}.$

2. Докажите, что для данного $r$ существует не более одной $r$ -четвёрки.

3. Докажите, что если $r$ -четверка существует, то $(p − r)$ -четвёрки не существует.

4. Докажите, что для всякого $r∈{2,3,...,p− 2}$ существует либо $r$ -четвёрка, либо $(p − r)$ -четвёрка.

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

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

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

Перепишем требуемое так: доказать, что для r=0, r=1 и r=p-1 r-четвёрки точно нет. Каким путём хочется доказать это утверждение?

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

Конечно! Давайте пойдём от противного. Если 0-четвёрка существует, то что следует из c ≡ ra (mod p)? Но разве это не противоречит равенству из условия?) Окей... Пусть теперь 1-четвёрка существует. Попробуем аналогично случаю r=0 прийти к противоречию! Какое тогда сравнение по (mod p) можно написать?

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

Верно! Тогда p = ab + cd ≡ ab + rad = a(b+d) (mod p). Какая делимость отсюда следует? Как можно оценить a и b+d?

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

Да! Либо a, либо (b+d) делится на p. Значит либо a≥p, либо (b+d)≥p. Хмм... но по условию ab + cd = p... Осталось написать цепочки неравенств и прийти к противоречию! Абсолютно аналогично докажем и для r=p-1.

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

Опять пойдём от противного. Пусть для одного r существуют две четвёрки: (a,b,c,d) и (a`, b`, c`, d`). Воспользуемся равенством из условия и попробуем связать четвёрки между собой.

Пункт 2. Подсказка 2

Ага. Можно заметить, что ac' ≡ ara' ≡ ca' (mod p). Попробуем аналогично связать b,d и b`,d`.

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

Тогда ac`- a`c, bd`- b`d кратны р. Предположим, что эти разности одновременно не равны нулю. Попробуем тогда оценить bd`- b`d, пользуясь тем, что ac`- a`c > 0. Какое противоречие получаем?

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

Да! ac` > p > ab. Отсюда с` > b, c` > d. Не забываем, что bd`- b`d кратно р, но разве оно больше p?) С этим случаем покончено. А что, если всё-таки какая-то разность равна нулю (пусть bd`- b`d=0)? Что можно сказать про делители переменных, исходя из условия ab+cd = p = a`b`+ c`d`? Как связать это с bd`= b`d.

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

Заметим, что из ab + cd = p = a`b` + c`d` следует, что b и d, b` и d` взаимнопросты. Тогда из bd`= b`d следует, что b=b`, d=d`. Как теперь можно преобразовать равенство ab+cd = a`b` + c`d`? Что из него следует?

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

Конечо! (a-a`)b=(c-c`)d. Но b и d взаимнопросты. Значит (a-a`) делится на d, (c-c`) делится на b! Обозначим это так: (a-a`)=dx, c-c`)=bx. Осталось рассмотреть случай x>0 и x<0, пользуясь неравенствами между переменными и заключить, что четвёрки совпадают!

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

Пусть (a,b,c,d), (a`,b`,c`,d`) — две четвёрки, удовлетворяющие условиям с r и c r` = p − r соответственно. Давайте действовать, как в прошлом пункте. Какие тогда цепочки сравнений по mod p тогда можно написать? Какое противоречие с делимость на p получается?

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

Верно! Можно получить, что ac`+a`c, bd`+b`d кратны p. Аналогично прошлому пункту, пусть с`≥b, тогда с`>c,d. Оценим bd`+b`d>0. Какое противоречие с делимостью на p можно получить?

Пункт 3. Подсказка 3

Да, bd`+b`d = 0, но bd`+b`d >0 !? Окей, пусть c`< b. Попробуем оценить a`c+ac и b`d+bd`. Чему могут быть равны эти выражения (помним, что они краты p).

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

a`c+ac` < ab+ a`b` < 2p, аналогично b`d+bd`<2p. Тогда, т.к. они делятся на p и больше нуля, то они равны p! А что еще равно p по условию?)

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

Да! Запишем разность ab + cd и a`c+ac`. Получаем делимость на a. Такс... чего-то не хватает. Вспомним, что четвёрки упорядоченные. Что, если а — наибольшее из всех чисел? Выполняется ли полученная делимость?)

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

Окей...Давайте искать четверки так: на плоскости рассмотрим все векторы с целыми координатами (x,y), где y≡rx (mod p). Рассмотрим вектор u=(a,c), где сумма a+c минимальная. Что тогда нужно сделать, чтобы доказать существование r-четвёрки (или (p-r)-четвёрки)?

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

Давайте на прямой с уравнением xc − ya =p (пусть a>c) искать точку (d,−b) такую, что d> 0, d< a,d <b,c<b — тогда четвёрка (a,b,c,d) и будет искомой. С какими прямыми нам теперь нужно работать, чтобы найти иском точку?

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

Да! Рассмотрим прямую y=-x. Пусть точка (x₀,y₀)∈ℓ с целыми x₀,y₀ лежит выше прямой y+x= 0, а точка v₀=(x₀− a,y₀− c) — (нестрого) ниже. Какие условия теперь надо проверить?

Пункт 4. Подсказка 4

Конечно! Проверим нужные нам неравенства, которы мы писали выше! Проверьте эти условия, пользуясь выбором вектора (сумма координат минимальна).

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

Теперь выберем наибольшее целое неотрицательное m, при котором x₀−a−ma≥0. Тогда вектор v₀−mu = (x₀−a−ma, y₀−c−mc) — искомый. Какой случай осталось проверить, прежде чем разобраться со случаем с>a?

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

Осталось только исключить случай x−a−ma =0! Разберём теперь c>a аналогично, просто по сути переобозначив переменные, закончив решение задачи!

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

1. Требуется исключить варианты $r=0,1,p− 1.$ Если существует $r$ -четверка $(a,b,c,d)$ при $r= 0,$ то $c$ натуральное кратное $p,$ и тогда $ab+cd> p$ — противоречие.

Пусть существует $r$ -четверка $(a,b,c,d)$ при $r= 1.$ Тогда

p= ab+cd≡ ab+ rad= a(b+d) (mod p)

Получаем, что $.. a(b+ d).p.$ Тогда либо $a,$ либо $b+ d$ делится на $p.$ Тогда либо $a≥ p,$ либо $b+ d≥ p.$ В первом случаем получаем, что $ab+ cd≥p +cd> p.$ Во втором же $ab+cd≥ 2b+d ≥p+ 1.$ Получаем, что $1$ -четверки не существует.

Пусть существует $r$ -четверка $(a,b,c,d)$ при $r= p− 1.$ Тогда

p= ab+cd≡ ab+ rad= a(b− d) (mod p)

Получаем, что $.. a(b− d).p.$ Тогда либо $a,$ либо $b− d$ делится на $p.$ Тогда либо $a≥ p,$ либо $b+ d≥ p$ $(b− d⁄= 0,$ поскольку $b>d).$ В первом случаем получаем, что $ab+ cd ≥p+ cd> p.$ Во втором же $ab+ cd≥ b+d> b− d≥ p.$ Получаем, что $(p− 1)$ -четверки тоже не существует.

2. Пусть $(a,b,c,d),$ $(a′,b′,c′,d′)$ — две четверки, удовлетворяющие условиям с одним и тем же $r.$ Тогда $ac′ ≡ara′ ≡ca′ (mod p),$ аналогично $bd′ ≡− rdd′ ≡ b′d (mod p).$ Т.е. $ac′− a′c,$ $bd′− b′d$ кратны $p.$

Предположим, что эти разности одновременно не равны нулю. Пусть не умаляя общности $ac′− a′c> 0,$ тогда $ac′ >p >ab,$ т.е. $c′ > b$ и тем более $c′ > d.$ Отсюда получаем, что

|bd′− b′d|< max(bd′,b′d)< max(c′d′,b′c′)= b′c′ <a′b′ < p

откуда (т.к. $|b′d − b′d|$ кратно $p)$ получаем $bd′− b′d= 0$ — противоречие.

Пусть теперь одна из исходных разностей равна нулю (не умаляя общности $bd′− b′d).$ Отметим, что из равенств $ab+ cd =p =a′b′+ c′d′$ следует взаимная простота $b$ и $d,$ $b′$ и $d′.$ Поэтому из равенства $bd′ = b′d$ следует, что $b= b′$ и $d =d′,$ а из него — $(a− a′)b= (c′− c)d.$ В силу взаимной простоты $b$ и $d$ имеем $a− a′ =dx,$ $c′− c =bx.$ При $x> 0$ это противоречит условию $c′ < b′ = b,$ при $x< 0$ — условию $c< b$ . Значит, $x= 0,$ $a= a′,$ $c= c′$ — четверки полностью совпадают.

3. Пусть $(a,b,c,d)$ , $(a′,b′,c′,d′)$ — две четверки, удовлетворяющие условиям с $r$ и c $r′ = p− r$ соответственно. Тогда $ac′ ≡− ara′ ≡ −ca′ (mod p),$ аналогично $bd′ ≡ −rdd′ ≡− b′d (mod p).$ Т.е. $ac′+a′c,$ $bd′+ b′d$ кратны $p.$

Пусть $′ c≥ b,$ а значит, $′ c> c,d,$ тогда, аналогично прошлому пункту,

′ ′ ′′ ′′ ′′ ′ ′ bd + bd< cd + bc< cd + ba =p

— противоречие с делимостью на $p.$ Значит, $c′ < b$ и, аналогично $c< b′,$ $d′ < a,$ $d< a′.$ Тогда $a′c+ ac′ <ab+ a′b′ < 2p,$ поэтому из делимости $ac′+ a′c= p$ и аналогично $b′d+ bd′ = p.$

Предположим теперь, не умаляя общности, что $a$ — наибольшее из чисел. Вычитая из $ab+cd$ равное ему $ac′+ ca′,$ получаем $a(b− c′)=c(a′− d),$ откуда из взаимной простоты $a$ и $c$ получаем, что $a′− d$ делится на $a$ — противоречие с тем, что $a< a′,$ $a′− d> 0.$

4. Рассмотрим на плоскости множество всех векторов $(x,y)$ с целыми координатами $x,y$ такими, что $y ≡ rx (mod p)$ или $y ≡(p− r)x (mod p).$ Отметим, что это множество вместе с каждым вектором $(x,y)$ содержит также и $(±x,±y).$ Рассмотрим в нашем множестве вектор с минимальной суммой координат. В силу замечания выше можно считать, что вектор $u := (a,c),$ где $a,c> 0,$ $a⁄= c$ (на осях координат и на биссектрисах углов между ними такой вектор лежать не может, поскольку $2 ≤r ≤p− 1),$ если $c≡ (p− r)a (mod p),$ то переобозначим $r$ и $p− r.$ Предположим пока, что $a> c.$ Рассмотрим прямую $ℓ$ с уравнением $xc− ya =p.$ Будем искать точку $(d,− b)$ на этой прямой такую, что $d> 0,d< a,d <b,c<b$ — тогда четверка $(a,b,c,d)$ и будет искомой. Заметим, что если $(x,y)∈ℓ,$ то $(x− a,y − c)∈ℓ.$

Прямая $ℓ$ где-то пересекает прямую $y+ x= 0.$ Пусть точка $(x0,y0)∈ ℓ$ с целыми $x0,y0$ лежит выше прямой $y+ x= 0,$ а точка $v0 :=(x0− a,y0− c)$ — (нестрого) ниже.

Во-первых, проверим, что $x0− a> 0.$ В самом деле, в противном случае $x0 ≤ a.$ Из выбора вектора $u$ имеем

a +c≤ |x0 − a|+|y0− c|= a− x0+|y0+c|

Если $c≥y0$ , то

a − x0+ |y0− c|= a+ c− x0− y0 < a+ c

— противоречие. Если же $y0 > c,$ то $p= x0c− y0a< ac− ac= 0$ — снова противоречие.

Итак, $x0− a> 0.$ Поскольку $(x0− a)+ (y0− c)≤ 0,$ имеем $y0 − c< 0.$ Если $y0 ≥ 0,$ то $0< x0− a ≤c− y0 ≤ c$ и обе координаты вектора $v 0$ по модулю не больше, чем $c$ — это опять противоречит выбору $u.$ Значит, $y < 0 0$ и $c− y > c. 0$ Теперь выберем наибольшее целое неотрицательное $m,$ при котором $x0− a− ma≥ 0.$ Ясно, что это неотрицательное значение строго меньше, чем $a.$ Тогда вектор

v0− mu = (x0 − a− ma,y0− c− mc)

и есть искомый вектор. Действительно, все нужные неравенства уже установлены, осталось только исключить случай $x − a− ma =0, 0$ но в таком случае из уравнения прямой $ℓ$ получаем $xc− ya= p,$ $− (y − c− mc )a =p, 0$ что невозможно в силу того, что $a> c> 0,$ $− y + c+mc ≥ 1+c +mc ≥2. 0$

Наконец обратимся к случаю $c> a.$ В этом случае обозначим $′ a =c,$ $′ c = a$ и построим точно так же четверку $′ ′ ′ ′ (a,b,c,d)$ со всеми нужными свойствами, но такую, что, наоборот $′ ′ a ≡rc (mod p).$ В этом случае, очевидно, $′ ′ ′ ′ (b,a ,d,c)$ будет $p− r$ -четверкой, что нам подходит.

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

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

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

Задача 2#83912

$P$ — некий полином с целыми коэффициентами, $A$ и $M$ — целые числа. Построим последовательность $a n$ , где $a = A 1$ , и $a =P (a) n+1 n$ и пусть $rn$ — остаток от деления $an$ на $M$ .

1. Пусть $P(x)= x2+ x+ 1,A = 1,M = 32022$ . Докажите, что период последовательности $rn$ (то есть, такое наименьшее $t$ , что $rn+t = rn$ при достаточно больших $n$ ) равен 2.

2. Найдите длину предпериода той же последовательности (то есть такое наибольшее $n$ , что $an+t ⁄= an$ , где $t$ — период).

3. Назовем полином стабильным по модулю $M$ , если существует $B$ , такое что для любого $A$ найдется $k$ , для которого $rk = B$ . Докажите, что полином $3 2 f = x − x − 2$ нестабилен по модулю $M$ , если $M$ является квадратом нечётного числа.

4. Докажите, что многочлен $P (x)= x2− 3x +12$ стабилен для бесконечного числа натуральных $M$ .

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

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

Если мы докажем, что с какого-то момента a_(n+2) - a_n = a_(n+1) - a_(n-1) (mod 3^2022), то и требуемое тоже будет доказано. Попробуйте выразить a_(n+2) - a_n через a_(n+1) и a_(n-1).

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

Мы получаем, что если a_(n+1) - a_(n-1) делится на 3^k, то и a_(n+2) - an делится на 3^k. Теперь, если мы докажем, что a_(n+1) - a_(n-1) делится на 3^(k+1), то сможем сказать, что с какого-то момента k станет >= 2022. Попробуйте для этого доказать, что a_(n+1) и a_(n-1) имеют одинаковые остатки при делении на 3.

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

Для этого посмотрите на значение a_n по mod 3.

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

Как подсказывает нам прошлый пункт задачи, нужно рассматривать остатки от деления a_n на степени 3. Попробуйте найти таким способом зацикливание.

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

Отлично! Теперь мы знаем, что остатки от деления a_n на 9 и на 27 зацикливаются. Тогда, зная, что степень вхождения 3 в выражение a_(n+1) - a_(n-1) каждый раз растёт, попробуйте вывести рекуррентную формулу для этой степени вхождения.

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

Если v_n - степень вхождения 3 в a_(n+1) - a_(n-1), то v_2 = 1, v_3 = 2, v_(2k+1) = v_2k + 2 и v_(2k+2) = v_(2k+1). Теперь осталось лишь решить неравенство v_k < 2022.

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

Нам нужно определить такое B, чтобы для него нашлось A, такой, что ни один r_k не равен B. Сразу сделать это довольно трудно. Попробуйте для начала подставлять небольшие A и посмотреть на значения полинома.

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

Отлично! Мы знаем, что f(2) = 2. Очень удобно будет доказывать, что есть такое A, что не будет остатка 2, ведь M - квадрат нечётного числа. Осталось лишь подобрать такое A и доказать, что r_k никогда не равен 2. Попробуйте найти A так, чтобы в нём как слагаемое присутствовало q (M = q^2).

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

Можно взять A = 2 + k*q (k и q взаимно просты). Теперь попробуйте рассмотреть f(A) по mod M.

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

Доказать, что это верно для произвольного множество бесконечных чисел, не представляется возможным. Поэтому нужно определить, для каких чисел мы это будем делать. Предыдущие пункты задачи явно подсказывают, что M должна быть степенью какого-то числа. Попробуйте перебирать небольшие числа и посмотреть, является ли стабильным полином по этому модулю.

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

Так, теперь мы знаем, что для 7 многочлен стабилен. Тогда попробуем доказать, что это верно и для 7^k. Легче всего сделать это по индукции. База уже есть, осталось доказать переход. И победа!

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

1. Легко видеть, что остатки $an$ от деления на 3 чередуются с периодом 2 (1, 0, 1, 0, . . .) поэтому период остатков по модулю $M = 32022$ тем более не равен 1.
Покажем что он равен 2.
Заметим, что $an+2 − an =a2n+1− a2n−1+an+1− an−1 = (an+1− an−1)(an+1+ an−1 +1)$
Отсюда следует, что если $an+1 − an−1$ делится на $3k$ , то тем же свойством обладает и $an+2− an$ , а если вдобавок $an+1$ , $an−1$ дают остаток от 1 деления на 3, то $an+2 − an$ делится на $3k+1$ .
Учитывая, что такая ситуация имеет место при каждом четном $n$ , получаем, что соответствующее $k$ может неограниченно увеличиваться, в частности, $an+2− an$ делится на $32022$ при некотором $n= n0$ (а значит и при всех $n >n0$ ). Поэтому период $rn$ равен двум.

2. Выпишем остатки от деления $an$ на 9 и на 27: легко убедиться, что это 2-периодические последовательности $1,3,4,3,4,...$ и $1,3,13,21,13,21,...$ соответственно.
Поэтому число $(an+1+ an−1+ 1)$ не делится на 3 при нечетных $n$ , делится на 3, но не на 9 при $n= 2$ и делится на 9, но не на 27 при четных $n >2$ .
То есть если $v n$ — степень вхождения 3 в число $a − a n+1 n−1$ , то $v = 1 2$ , $v =2 3$ а дальше $v =v + 2 2k+1 2k$ и $v = v 2k+2 2k+1$ .
Отсюда легко видеть, что наибольшее $s$ такое, что $v <2022 s$ равно 2022, то есть $a − a 2023 2021$ — последняя среди разностей вида $an+2− an$ не кратная $M$ .

3. Пусть $M =Q2$ , тогда $Q$ - нечетное число.
Заметим, что $f(2)= 23− 22− 2= 2$ ,значит, достаточно показать, что существует число, проделывая операцию из условия над которым мы не получим 2.
Рассмотрим числа вида $t= 2+ kQ$ , где НОД $(k;Q)= 1$
$f(t)= (2+ kQ)3 − (2+ kQ )2 − 2= Q3k3+ 5Q2k2+8Qk +2$
Нетрудно заметить, что $f(t)≡ 8Qk + 2(mod M )$
То есть числа вида $t= 2+ kQ$ , где НОД $(k;Q)= 1$ переходят в себя, но число 2 не имеет такого вида, поэтому полином $f = x3− x2 − 2$ нестабилен по модулю $M$ , если $M$ является квадратом нечётного числа.

4. Индукцией по $k$ докажем, что для $M = 7k$ многочлен $x2− 3x+ 12$ стабилен.
Обозначим через $a → b$ , то что $P(a)≡b(modM )$
База $k =1$

0→ 5→ 1 → 31 → 3→ 5→ 12 → 3→ 5→ 13→ 5 → 1→ 34→ 2→ 3→ 5→ 15→ 1 → 36 → 5→ 1→ 3

Таким образом, имеем цикл длины 3 везде одинаковый.
Переход $k→ k+ 1$
Пусть по модулю $M = 7k$ многочлен стабилизируется так, что всегда встретится $r$
Тогда по модулю $M = 7k+1$ остаток $r$ будет $7km+ r= r1$
$P (r1)≡r2− 3r+ 12 +7kn(2r− 3)(Mod 7k+1)$ , что не зависит от $n$ , при $0≡ 2r− 3(Mod 7)$
$0 ≡2r− 3(Mod 7)⇔ 5 ≡r(Mod 7)$ , что бывает по базе индукции, поэтому многочлен стабилизируется и по модулю $7k+1$ .

Ответ:

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

2. 2021

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

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

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

Задача 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$ ; этот случай проверяется непосредственно.