X математическая олимпиада «Шелковый путь», 2011 год
Комментарий/решение:
Лемма 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.
Докажем, что если 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 простое в кольце. Противоречие. Ч.Т.Д.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.