19-я Международная Жаутыковская олимпиада по математике, 2023 год

Егер натурал санды $ax^2+bxy+cy^2$ түрінде келтіруге болса, бұл жерде $a$, $b$, $c$, $x$, $y$ — бүтін сандар және $b^2-4ac=-20$, сол санды жақсы сан деп айтамыз. Екі жақсы санның көбейтіндісі де жақсы сан болатынын дәлелдеңіз. ( А. Голованов )

Комментарий/решение

Назовем простое число $p$ хорошим, если $-5$ является квадратичным вычетом $mod$ $p$ и плохим в противном случае.

Утверждение. Натуральное число $t$ является хорошим тогда и только тогда, когда все плохие простые числа делят его в четной степени.

Пускай число $t$ является числом указанного вида. Пусть $t=ax^2$, где $a$ - часть числа $t$ свободная от квадратов (то есть мы выделили максимальную четную степень для каждого простого делителя). Тогда, по предположению, для всех $p|a$, сравнение $x^2 \equiv -5\text{ }(mod\text{ }p)$ разрешимо, тогда, по китайской теореме об остатках, разрешимо и сравнение $x^2 \equiv -5\text{ }(mod\text{ }a)$, пусть $r$ - решение этого сравнения, тогда пусть $r^2+5=ac$. Тогда $t = ax^2 + 2rxy + cy^2$ - требуемое представление для $y=0$, откуда $t$ и вправду хорошее.

Пусть теперь наоборот, $t$ - хорошее. Заметим сразу, что если $p|m^2+5n^2$ и $p$ - плохое, то $p|m,n$. Если нет, что $(\frac{m}{n})^2 \equiv -5\text{ }(mod\text{ }p)$, откуда оно хорошее. Допустим, что $2 \nmid v_p(t)$ для какого то плохого $p$.Теперь $p|ta = (ax+\frac{by}{2})^2+5y^2$ и $p|tc = (cy+\frac{bx}{2})^2+5x^2$, откуда $p|x,y$, тогда заменим $x$ и $y$ на $\frac{x}{p}$ и $\frac{y}{p}$, тогда $v_p(t)$ уменьшиться на 2, но $t$ останется хорошим и степень вхождения также будет нечетной. Рано или поздно это приведет к противоречию.

Остается заметить, что в такой формулировке произведение двух чисел очевидно остается хорошим

Добрый день! Классное решение! Сколько у вас баллов на М.Ж.О?

Кажется 28

Фанаты опять накручивают лайки

https://izho.kz/wp-content/uploads/2023/02/Day_2_sol_2023.pdf

Утверждение: если $n$ имеет вид $ax^2+bxy+cy^2$ для некоторых таких $a,b,c$, то либо $n=x^2+5y^2$, либо $n=2x ^2+2xy+3y^2$ (для разных $x,y$).

Доказательство претензии: Очевидно, что мы можем w.log.g. предположим, что $a \ge c>0$ и $b \ge 0$. Более того, подставив $x x+y$, мы можем w.l.o.g. предположим, что $b \le a$. Следовательно, $20=4ac-b^2 \ge 3a^2$ и, следовательно, $a \le 2$ и быстрый анализ показывает, что единственными возможностями являются $(a,b,c)=(1,0,5)$ и $(a,b,c)=(2,2,3)$.

Возвращаясь к основной проблеме, теперь достаточно доказать, что произведения чисел вида $x^2+5y^2$ или $2x^2+2xy+3y^2$ снова имеют этот вид. Но это следует непосредственно из следующих трех тождеств:

\[(a^2+5b^2)(c^2+5d^2)=(ac+5bd)^2+5(ad-bc)^2.\]\[(a^2+5b^2 )(2c^2+2cd+3d^2)=2(ac-bc-3bd)^2+2(ac-bc-3bd)(2bc+bd+ad)+3(2bc+bd+ad)^2 .\]\[(2a^2+2ab+3b^2)(2c^2+2cd+3d^2)=(2ac+bc+ad-2bd)^2+5(bc+ad+bd)^2 .\](Обратите внимание, что хотя это может выглядеть как черная магия, эти тождества можно легко получить из факторизаций $a^2+5b^2=(a+\sqrt{-5}b)(a-\sqrt{-5 }b)$ и т. д. точно так же, как обычные тождества для сумм двух квадратов получаются факторизацией в $\mathbb{Z}[i]$.)

"доказательство претензии")))))

Мне кажется достаточно оставлять ссылку на aops, а не переводить через гугл-переводчик и вставлять сюда, потому что гугл иногда коряво переводит