Processing math: 47%

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


Назовём натуральное число хорошим, если оно представляется в виде ax2+bxy+cy2, где a, b, c, x, y -- целые числа и b24ac=20. Докажите, что произведение двух хороших чисел — тоже хорошее число. ( А. Голованов )
посмотреть в олимпиаде

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

  13
2 года 2 месяца назад #

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

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

Пускай число t является числом указанного вида. Пусть t=ax2, где a - часть числа t свободная от квадратов (то есть мы выделили максимальную четную степень для каждого простого делителя). Тогда, по предположению, для всех p|a, сравнение x25 (mod p) разрешимо, тогда, по китайской теореме об остатках, разрешимо и сравнение x25 (mod a), пусть r - решение этого сравнения, тогда пусть r2+5=ac. Тогда t=ax2+2rxy+cy2 - требуемое представление для y=0, откуда t и вправду хорошее.

Пусть теперь наоборот, t - хорошее. Заметим сразу, что если p|m2+5n2 и p - плохое, то p|m,n. Если нет, что (mn)25 (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 останется хорошим и степень вхождения также будет нечетной. Рано или поздно это приведет к противоречию.

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

  0
2 года 2 месяца назад #

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

  0
2 года 2 месяца назад #

Кажется 28

  5
2 года 2 месяца назад #

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

  10
1 года 5 месяца назад #

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

  5
1 года 4 месяца назад #

Утверждение: если 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].)

  2
1 года 2 месяца назад #

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

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