Простые делители минимального квадрата 9/9

1. Условия и обозначения

Рассмотрим магический квадрат 3×3, все девять клеток которого являются положительными попарно различными квадратами целых чисел:

\mathcal M(e^2,x,y)= \begin{pmatrix} a^2&b^2&c^2\\ d^2&e^2&f^2\\ g^2&h^2&j^2 \end{pmatrix}.

Квадрат называется минимальным, если корни его клеток взаимно просты в совокупности:

\gcd(a,b,c,d,e,f,g,h,j)=1.

Это равносильно невозможности разделить все клетки на один и тот же квадрат целого числа, больший единицы. Далее факторизуются именно корни клеток; показатели простых в самих клетках вдвое больше.

Общая форма магического квадрата 3×3 →

2. Два набора тождеств

Каждая пара клеток, противоположных относительно центра, имеет сумму 2e²:

a^2+j^2=b^2+h^2=c^2+g^2=d^2+f^2=2e^2.

Кроме того, каждый угол является средним членом арифметической прогрессии, концы которой находятся в двух боковых клетках:

\begin{aligned} f^2+h^2&=2a^2,& d^2+h^2&=2c^2,\\ b^2+f^2&=2g^2,& b^2+d^2&=2j^2. \end{aligned}

Доказательство

В форме m(e²,x,y) отклонения четырёх противоположных пар от центра равны x, y−x, y и x+y. Сложение элементов каждой пары уничтожает отклонение и даёт 2e². Для первой угловой прогрессии получаем

(e^2+x+y)+(e^2+x-y)=2(e^2+x)=2a^2.

Остальные три равенства получаются тем же раскрытием или поворотом квадрата.

3. Простые 4k+3 и сумма двух квадратов

Лемма

Пусть q — простое число, q≡3 (mod 4). Если q делит u²+v², то q делит и u, и v.

Доказательство

Если v не делится на q, то класс uv⁻¹ был бы квадратным корнем из −1 по модулю q. Но по критерию Эйлера

u^2\equiv-v^2\pmod q \quad\Longrightarrow\quad (uv^{-1})^2\equiv-1\pmod q, \qquad q\nmid v.

\left(\frac{-1}{q}\right)=(-1)^{(q-1)/2}=-1,

поэтому такого корня нет. Значит, q делит v, после чего из q∣u² следует q∣u.

Форма через показатели

Если u и v не равны нулю одновременно, то

v_q(u^2+v^2)=2\min\{v_q(u),v_q(v)\}.

Действительно, после вынесения общей степени q оставшаяся сумма двух квадратов не делится на q по доказанной лемме.

4. Единственное примитивное разложение одной простой степени

Почему в ℤ[i] есть единственность факторизации

Для z=u+iv положим N(z)=u²+v². Если α,β∈ℤ[i] и β≠0, округлим действительную и мнимую части α/β до ближайших целых чисел и получим γ∈ℤ[i]. Тогда для остатка ρ=α−γβ выполняется

N(\rho)=N(\beta)\left|\frac{\alpha}{\beta}-\gamma\right|^2 \le\frac12N(\beta)<N(\beta).

Следовательно, норма является евклидовой функцией. Евклидов алгоритм даёт наибольший общий делитель и тождество Безу. Поэтому каждый неприводимый элемент прост: если π∣αβ и π∤α, то gcd(π,α)=1, а умножение тождества Безу на β даёт π∣β. Разложение на неприводимые существует по убыванию положительной нормы, а простота неприводимых последовательно сокращает одинаковые множители в двух разложениях. Тем самым ℤ[i] является кольцом с единственностью факторизации.

Геометрия деленияБлижайшее гауссово целое

Точка α/β всегда попадает в один из таких квадратов.|α/β − γ|² = s² + t² ≤ 1/2

Расщепление простого p≡1 (mod 4)

По критерию Эйлера существует t, для которого t²≡−1 (mod p). Поэтому p делит (t+i)(t−i), но не делит ни один множитель в ℤ[i]: делимость на рациональное p потребовала бы делимости на p обеих координат, включая координату ±1. Значит, p не является простым элементом ℤ[i] и раскладывается нетривиально. Нормы двух нетривиальных множителей перемножаются в p², поэтому каждая равна p. Выбирая один из них как π, получаем

p=\pi\bar\pi,\qquad N(\pi)=p.

Два представления N=u²+v² считаются одинаковыми, если они отличаются перестановкой u,v или знаками. Представление называется p-примитивным, если p не делит одновременно u и v.

Гауссова лемма

Если p≡1 (mod 4) — простое и α≥1, то число 2p²ᵅ имеет ровно одно p-примитивное представление суммой двух квадратов с точностью до указанной эквивалентности.

Доказательство

В кольце гауссовых целых выберем простое π, для которого p=ππ̄. Из единственности факторизации любой элемент z=u+iv нормы 2p²ᵅ с точностью до умножения на единицу имеет вид

z\sim(1+i)\pi^r\bar\pi^{\,2\alpha-r}, \qquad 0\le r\le2\alpha.

Условие p∣u и p∣v равносильно делимости z на p=ππ̄. Оно выполняется ровно при 1≤r≤2α−1. Остаются r=0 и r=2α; соответствующие элементы сопряжены и задают одно представление после перестановки и изменения знаков.

Интерактивный инструмент

Гауссова факторизация

Переставляйте сопряжённые множители и наблюдайте, какое представление суммой двух квадратов они задают.

n1…20 000

325 =5²4k+1134k+1

Разложение в сумму двух квадратов существуетВсе простые 4k+3 входят в чётных степенях.

Все варианты

325 = 1² + 18²325 = 6² + 17²325 = 10² + 15²

Левый столбец	⇄	Правый столбец
1 + 2i		1 − 2i
1 + 2i		1 − 2i
2 + 3i		2 − 3i
-18 − i	×	-18 + i

Произведения столбцовz = -18 − i, z̄ = -18 + i

Норма выбранного произведения325 = 1² + 18²

5. Факторизация центрального корня

Структура квадратаПять представлений числа 2e²

a²

b²

c²

d²

e²

f²

g²

h²

j²

a² + j² = b² + h² = c² + g² = d² + f² = 2e²

e² + e² = 2e²

Одинаковый цвет связывает клетки, противоположные относительно центра.

Теорема

Центральный корень e минимального квадрата 9/9 имеет вид

e=\prod_{i=1}^{r}p_i^{\alpha_i}, \qquad r\ge2,\quad p_i\equiv1\pmod4,\quad \alpha_i\ge1,

где p₁,…,pᵣ — попарно различные простые числа.

Исключение простых 4k+3

Пусть простое q≡3 (mod 4) делит e. Каждая из четырёх противоположных пар удовлетворяет u²+v²=2e², поэтому предыдущая лемма заставляет q делить оба её корня. Тогда q делит все девять корней, что противоречит минимальности.

Исключение числа 2

Если e чётно, то 2e² делится на 8. Сумма двух квадратов может делиться на 8 только тогда, когда оба корня чётны. Четыре равенства для противоположных пар снова сделали бы все корни чётными. Следовательно, e нечётно.

Итак, каждый простой делитель e имеет вид 4k+1.

Не менее двух различных делителей

Случай e=1 невозможен: число 2 имеет только представление 1²+1², тогда как четыре пары различных нецентральных клеток должны давать четыре различных представления 2e².

Предположим теперь, что у e имеется только один различный простой делитель. Тогда e=pᵅ для некоторого p≡1 (mod 4). Четыре пары противоположных нецентральных клеток дают четыре различных представления 2p²ᵅ. По гауссовой лемме не более одной пары является p-примитивной. Поэтому по модулю p ненулевой может остаться не более чем одна пара противоположных клеток.

Магическая константа равна 3e² и потому равна нулю по модулю p. Возьмём строку или столбец, содержащие одну клетку оставшейся пары, но не содержащие противоположную. Две другие клетки этой линии равны нулю, поэтому её сумма заставляет равняться нулю и третью клетку. Значит, p делит также корни последней пары, а затем все девять корней. Получено противоречие с минимальностью.

6. Число представлений числа 2e²

Пусть e имеет доказанную факторизацию. Число неупорядоченных положительных представлений 2e²=u²+v² с точностью до знаков равно

R(2e^2)=\frac{1+\prod_{i=1}^{r}(2\alpha_i+1)}{2}.

Доказательство

В гауссовой факторизации для каждой пары πᵢ,π̄ᵢ можно независимо выбрать показатель πᵢ от 0 до 2αᵢ; это даёт ∏(2αᵢ+1) вариантов до умножения на единицы. В обычном подсчёте упорядоченных представлений получается 4∏(2αᵢ+1) решений со знаками. Единственное диагональное представление — e²+e². Оно имеет четыре, а каждое недиагональное неупорядоченное представление — восемь упорядоченных знаковых вариантов, откуда следует формула.

Сам квадрат использует пять различных представлений: четыре пары противоположных клеток и центральную пару e²+e².

7. Простые делители нецентральных корней

Теорема

Пусть q≡3 (mod 4) — простой делитель любого из восьми нецентральных корней минимального квадрата 9/9. Тогда

q\equiv7\pmod8.

Из теоремы о центре следует q∤e.

Угловая клетка

По симметрии достаточно рассмотреть q∣a. Из f²+h²=2a² и леммы о простых 4k+3 следует q∣f и q∣h. В координатах m(e²,x,y) разности f²−a²=y и h²−a²=−y, поэтому y≡0 (mod q). Из a²=e²+x≡0 получаем x≡−e². Следовательно,

b^2=e^2-x+y\equiv2e^2\pmod q.

Поскольку q не делит e, число 2 является ненулевым квадратом по модулю q.

Боковая клетка

По симметрии положим q∣b. Используем две угловые прогрессии

b^2+d^2=2j^2,\qquad b^2+f^2=2g^2.

Если хотя бы один из j,g не делится на q, соответствующее равенство сразу показывает, что 2 — квадрат по модулю q. Если q делит и j, и g, то он делит также d и f. Равенства j²=e²−x≡0 и g²=e²+y≡0 дают x≡e² и y≡−e², после чего f²=e²+x+y≡e². Это противоречит одновременно q∣f и q∤e. Следовательно, 2 снова является квадратом по модулю q.

Завершение

Дополнительный закон для символа Лежандра имеет вид

\left(\frac2q\right)=(-1)^{(q^2-1)/8}.

При q≡3 (mod 4) возможны классы 3 и 7 по модулю 8. Число 2 является квадратом только во втором из них, поэтому q≡7 (mod 8).

8. Итоговая факторизационная граница

В центральном корне встречаются только простые 1 или 5 по модулю 8, причём различных простых не менее двух. В любом нецентральном корне простой делитель 3 по модулю 4 может иметь только класс 7 по модулю 8; классы 3 по модулю 8 исключены.

Вместе с ограничениями по модулю 24 все девять корней нечётны и не делятся на 3. Эти условия необходимы, но сами по себе не достаточны для существования квадрата 9/9.

Вычеты и квадратичные вычеты →