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

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

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

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

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

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

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

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

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

Задача 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. Пусть существует $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> 1$ . Во втором же $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> 1$ . Во втором же $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′+b′d< c′d′+b′c′ < c′d′+b′a′ = 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$ . Отметим, что это множество вместе с каждым вектором $(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$ и обе координаты вектора $v0$ по модулю не больше, чем $c$ — это опять противоречит выбору $u$ . Значит, $y0 < 0$ и $c− y0 > c$ . Теперь выберем наибольшее целое неотрицательное $m$ , при котором $x0− a− ma≥ 0$ . Ясно, что это неотрицательное значение строго меньше, чем $a$ . Тогда вектор $v0− mu =(x0− a− ma, y0− c− mc)$ и есть искомый вектор. Действительно, все нужные неравенства уже установлены, осталось только исключить случай $x0 − a− ma =0$ , но в таком случае из уравнения прямой $ℓ$ получаем $xc− ya= p$ , $− (y0− c− mc)a =p$ , что невозможно в силу того, что $a> c> 0$ , $− y0+c +mc ≥1 +c+ mc≥ 2$ .

Наконец обратимся к случаю $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. Легко видеть, что остатки $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-$ - простое.

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

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