Оценочная теория чисел

Пункт 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 аналогично, просто по сути переобозначив переменные, закончив решение задачи!