Loading [MathJax]/jax/output/SVG/jax.js

X математическая олимпиада «Шелковый путь», 2011 год


Докажите, что существует бесконечно много простых чисел, представимых в виде m2+mn+n2 для некоторых целых чисел m,n.
посмотреть в олимпиаде

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

пред. Правка 4   6
8 года 7 месяца назад #

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

Пусть (a,n)=1 тогда существуют натуральные числа x,yn такие, что a2x2y2(modn) .

Док-во:

Надо рассмотреть все числа вида axy где x,y{0,1,...,[n]} тогда получим больше n чисел , (точнее ровно ([n]+1)2) значит два числа дают одинаковый остаток при дел. на n т.e. ax1y1ax2y2(modn) или a2(x1x2)2(y1y2)2(modn).

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

Док:

Пусть x примитивный корень p , тогда в место a положим a=2xp13+1.

Лемма 3 : Любое простое число вида 3k+1 представимо в виде 3a2+b2.

Док-во:

По лемме 2 имеем: a23(modp)

и по лемме 1: a2x23x2y2(modp) где x2,y2<p. Значит 3x2+y2=pk где k<4 дальше легко...

Лемма 4:

Числа вида 3a2+b2 представимы в виде m2+mn+n2.

Док:

3a2+b2=(ab)2+(ab)(a+b)+(a+b)2.

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

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

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

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

Est' ssylka na vawe rewenie?

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

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

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

пред. Правка 3   -2
5 года 10 месяца назад #

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

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

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