X математическая олимпиада «Шелковый путь», 2011 год
Комментарий/решение:
Лемма 1 (Очень полезная!):
Пусть (a,n)=1 тогда существуют натуральные числа x,y≤√n такие, что a2⋅x2≡y2(modn) .
Док-во:
Надо рассмотреть все числа вида ax−y где x,y∈{0,1,...,[√n]} тогда получим больше n чисел , (точнее ровно ([√n]+1)2) значит два числа дают одинаковый остаток при дел. на n т.e. ax1−y1≡ax2−y2(modn) или a2(x1−x2)2≡(y1−y2)2(modn).
Лемма 2: Если простое имеет вид p=3k+1 тогда существует натуральное число a такое, что p|a2+3
Док:
Пусть x− примитивный корень p , тогда в место a положим a=2xp−13+1.
Лемма 3 : Любое простое число вида 3k+1 представимо в виде 3a2+b2.
Док-во:
По лемме 2 имеем: a2≡−3(modp)
и по лемме 1: a2x2≡−3x2≡y2(modp) где x2,y2<p. Значит 3x2+y2=pk где k<4 дальше легко...
Лемма 4:
Числа вида 3a2+b2 представимы в виде m2+mn+n2.
Док:
3a2+b2=(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′)=x2+xy+y2 для каких то целых x,y по определению нормы в кольце Z[w]. С этой частью разобрались.
Теперь, собственно, докажем что p обязательно составное. Если это не так: В силу того,что -3 квадратичный вычет по модулю 6k+1(легкое применение символа Лежандра, а именно, закона квадратичной взаимности), то существуют m,n целые такие что: (2m−n)2+3n2 делится на p. p-нечетное, значит m2+mn+n2=(m+nw)(m+nw)′ делится на p. Но m и n взаимно просты с p и p простое в кольце. Противоречие. Ч.Т.Д.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.