11-ші «Жібек жолы» математикалық олимпиадасы, 2011 жыл

Кейбір бүтін $m,n$ сандары арқылы $m^2 + mn + n^2$ түрінде өрнектеуге болатын ақырсыз көп жай сандар табылатынын дәлелдеңдер.

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

Лемма 1 (Очень полезная!):

Пусть $(a,n)=1$ тогда существуют натуральные числа $x,y\le \sqrt{n}$ такие, что $a^2\cdot x^2\equiv y^2 \pmod n$ .

Док-во:

Надо рассмотреть все числа вида $ax-y$ где $x,y\in \{0,1,...,[\sqrt{n}]\}$ тогда получим больше $n$ чисел , (точнее ровно $([\sqrt{n}]+1)^2$) значит два числа дают одинаковый остаток при дел. на $n$ т.e. $ax_1-y_1\equiv ax_2-y_2 \pmod n$ или $a^2(x_1-x_2)^2 \equiv (y_1-y_2)^2 \pmod n$.

Лемма 2: Если простое имеет вид $p=3k+1$ тогда существует натуральное число $a$ такое, что $p|a^2+3$

Док:

Пусть $x-$ примитивный корень $p$ , тогда в место $a$ положим $a=2x^{\frac{p-1}{3}}+1$.

Лемма 3 : Любое простое число вида $3k+1$ представимо в виде $3a^2+b^2$.

Док-во:

По лемме 2 имеем: $a^2\equiv -3 \pmod p$

и по лемме 1: $a^2x^2\equiv -3x^2 \equiv y^2 \pmod p$ где $x^2,y^2<p$. Значит $3x^2+y^2=pk$ где $k<4$ дальше легко...

Лемма 4:

Числа вида $3a^2+b^2$ представимы в виде $m^2+mn+n^2$.

Док:

$3a^2+b^2=(a-b)^2+(a-b)(a+b)+(a+b)^2$.

Итак по теореме Дирихле простых чисел вида $3k+1$ бесконечно много.

На самом деле, любое простое число 6k+1 представимо в таком виде. Это не трудно понять, если заметить что такое простое число является составным в кольце $Z[w]$, где $w$ - корень третьей степени из 1.

Est' ssylka na vawe rewenie?

Докажем, что если p - составное, то оно представимо в таком виде. В кольце p можно записать как произведение числа на сопряженное к нему. p=aa' (дальше нетрудно показать,что a и a' взаимно просты). $p=N(p)=N(aa')=x^2+xy+y^2$ для каких то целых $x,y$ по определению нормы в кольце $Z[w]$. С этой частью разобрались.

Теперь, собственно, докажем что p обязательно составное. Если это не так: В силу того,что -3 квадратичный вычет по модулю $6k+1$(легкое применение символа Лежандра, а именно, закона квадратичной взаимности), то существуют m,n целые такие что: $(2m-n)^2+3n^2$ делится на p. p-нечетное, значит $m^2+mn+n^2=(m+nw)(m+nw)'$ делится на p. Но m и n взаимно просты с p и p простое в кольце. Противоречие. Ч.Т.Д.

Что такое примитивный корень?

Можете подробнее доказать Лемму1