19-я Международная Жаутыковская олимпиада по математике, 2023 год
Комментарий/решение:
Назовем простое число p хорошим, если −5 является квадратичным вычетом mod p и плохим в противном случае.
Утверждение. Натуральное число t является хорошим тогда и только тогда, когда все плохие простые числа делят его в четной степени.
Пускай число t является числом указанного вида. Пусть t=ax2, где a - часть числа t свободная от квадратов (то есть мы выделили максимальную четную степень для каждого простого делителя). Тогда, по предположению, для всех p|a, сравнение x2≡−5 (mod p) разрешимо, тогда, по китайской теореме об остатках, разрешимо и сравнение x2≡−5 (mod a), пусть r - решение этого сравнения, тогда пусть r2+5=ac. Тогда t=ax2+2rxy+cy2 - требуемое представление для y=0, откуда t и вправду хорошее.
Пусть теперь наоборот, t - хорошее. Заметим сразу, что если p|m2+5n2 и p - плохое, то p|m,n. Если нет, что (mn)2≡−5 (mod p), откуда оно хорошее. Допустим, что 2∤ для какого то плохого 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 останется хорошим и степень вхождения также будет нечетной. Рано или поздно это приведет к противоречию.
Остается заметить, что в такой формулировке произведение двух чисел очевидно остается хорошим
Добрый день! Классное решение! Сколько у вас баллов на М.Ж.О?
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].)
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.