C11 Тождества Софи Жермен и продвинутая факторизация

Идея метода: некоторые многочлены, которые не разлагаются над $\mathbb{Z}$ «стандартными» формулами (разность квадратов, кубов и т.п.), всё же факторизуются, если использовать нетривиальное тождество — добавить и вычесть вспомогательный член так, чтобы получились неполные квадраты или группируемые множители.

Самый знаменитый пример — тождество Софи Жермен:$$a^4 + 4b^4 = (a^2 + 2b^2 - 2ab)(a^2 + 2b^2 + 2ab).$$ Слева стоит сумма, которая «похожа» на неразложимую. Справа — два множителя. Как это получается? Добавим и вычтем $4a^2b^2$: $a^4 + 4a^2b^2 + 4b^4 - 4a^2b^2 = (a^2+2b^2)^2 - (2ab)^2$. Это уже разность квадратов.

Такой подход называют продвинутой факторизацией: ищем подходящую алгебраическую «достройку» до полного квадрата, куба, или применяем нетривиальное группирование. В олимпиадных задачах по теории чисел это позволяет доказать, что выражение составное (имеет нетривиальный делитель), не находя делитель явно. Метод требует знания нескольких «заготовленных» тождеств и умения увидеть, под какое из них маскируется задача.

• Тождество Софи Жермен: $a^4 + 4b^4 = (a^2 + 2b^2 - 2ab)(a^2 + 2b^2 + 2ab)$. Условие: оба множителя $> 1$ при $a, b \geq 1$, $a$ нечётно или $b \geq 1$. Когда использовать: выражение имеет вид $n^4 + 4m^4$ или $n^4 + 4$ (при $m=1$); задачи ТЧ на составность.

• Тождество $a^4 + a^2 + 1$: $a^4 + a^2 + 1 = (a^2 + a + 1)(a^2 - a + 1)$. Условие: $a \geq 1$; оба множителя $> 1$ при $a \geq 2$. Когда использовать: задачи вида «докажите, что $n^4 + n^2 + 1$ составное при $n \geq 2$»; телескопические произведения.

• Разность $n$-х степеней: $a^n - b^n = (a-b)(a^{n-1} + a^{n-2}b + \ldots + b^{n-1})$. Условие: $n \in \mathbb{N}$, $a \neq b$. Когда использовать: делимость $a^n - 1$ на $a - 1$, нахождение НОД.

• Сумма нечётных степеней: $a^n + b^n = (a+b)(a^{n-1} - a^{n-2}b + \ldots + b^{n-1})$ при нечётном $n$. Условие: $n$ нечётное. Когда использовать: доказать делимость $a^n + b^n$ на $a+b$.

• Тождество для $a^4 + b^4$: $a^4 + b^4 = (a^2 + b^2)^2 - 2a^2b^2$; само по себе не факторизуется над $\mathbb{Z}$, но через $a^4+4b^4$ с подстановкой $b \leftarrow \frac{b}{\sqrt[4]{4}}$ — полезная промежуточная форма.

• Тождество $a^6 - b^6$: $a^6 - b^6 = (a^2-b^2)(a^4+a^2b^2+b^4) = (a-b)(a+b)(a^2+ab+b^2)(a^2-ab+b^2)$. Когда использовать: задачи на кратные факторизации степеней 6.

• «Достройка» до полного квадрата. Добавить и вычесть $4a^2b^2$, чтобы получить $(a^2+2b^2)^2-(2ab)^2$, затем применить разность квадратов.

• Группировка с перегруппировкой. Разбить сумму на две части так, чтобы в каждой был общий множитель: $a^4+a^3b - a b^3 - b^4 = a^3(a+b) - b^3(a+b) = (a+b)(a^3-b^3)$.

• Замена переменной для приведения к знакомому виду. Если выражение содержит $n^4+4$, подставить $a=n, b=1$ в тождество Жермен.

• Использование корней единицы (теоретически). $a^n - b^n$ делится на $a - \omega b$ для каждого $n$-го корня из единицы $\omega$. Даёт полную факторизацию над $\mathbb{C}$, что помогает найти разложение над $\mathbb{Z}$.

• Телескопирование через тождество. $a^4+a^2+1 = \frac{a^6-1}{a^2-1}$ при $a \neq 1$, что даёт телескопические произведения вида $\prod_{k=1}^n (k^4+k^2+1)$.

• Проверка значений. При подозрении на нетривиальный делитель подставить конкретные малые значения и угадать структуру множителей.

Поверхностные признаки (что буквально написано):
- «Докажите, что $n^4 + 4k^4$ составное» или «не является простым»
- «Докажите, что $f(n)$ делится на $g(n)$» при степени $\geq 4$ - «Найдите все простые числа вида $n^4 + 4$»
- «Докажите, что выражение не является простым для $n > 1$»

Структурные признаки (форма выражения, объекты):
- Степень 4 или 6 в сумме; выражение вида $\square^4 + 4\square^4$ - Выражение «похоже» на полный квадрат, но не является им
- Задача про $n^4 + n^2 + 1$, $n^4 + 4$, $n^6 \pm$ - В задаче нет запроса «найти корни», а только «разложить» или «доказать составность»

Цель задачи (что от тебя хотят):
- Доказать, что число составное (предъявить нетривиальный делитель)
- Разложить многочлен в произведение
- Вычислить телескопическое произведение или сумму

Задача 1. Докажите, что число $n^4 + 4$ составное для любого целого $n > 1$.

Источник: классика олимпиадной теории чисел, тренировочная

Как думать (рассуждение ученика):
1. Что я вижу? Выражение $n^4 + 4$ для $n > 1$. Нужно доказать составность, то есть найти нетривиальный делитель. Перебрать? При $n=2$: $16+4=20=4\cdot5$. При $n=3$: $81+4=85=5\cdot17$. При $n=4$: $256+4=260=4\cdot65$. Явного закона не видно, но чувствуется, что всегда делится на что-то нетривиальное.
2. Какой метод? Выражение вида $n^4 + 4\cdot 1^4$ — это точно тождество Жермен с $a=n, b=1$.
3. Первый ход: Применить тождество $a^4 + 4b^4 = (a^2+2b^2-2ab)(a^2+2b^2+2ab)$ при $a=n, b=1$.
4. Проверить, что оба множителя $> 1$ при $n > 1$.

Решение:

По тождеству Софи Жермен:$$n^4 + 4 = n^4 + 4 \cdot 1^4 = (n^2 + 2 - 2n)(n^2 + 2 + 2n) = (n^2 - 2n + 2)(n^2 + 2n + 2).$$

Остаётся убедиться, что оба множителя больше $1$ при $n > 1$:
- $n^2 + 2n + 2 = (n+1)^2 + 1 \geq (2+1)^2 + 1 = 10 > 1$. ✓
- $n^2 - 2n + 2 = (n-1)^2 + 1 \geq (2-1)^2 + 1 = 2 > 1$. ✓

Следовательно, при $n > 1$ число $n^4 + 4$ является произведением двух чисел, каждое из которых больше $1$, то есть является составным.

Ответ: $n^4 + 4 = (n^2-2n+2)(n^2+2n+2)$ — составное при всех $n > 1$.

Что в этой задаче было главным: распознать, что $n^4 + 4 = n^4 + 4 \cdot 1^4$ — это ровно форма тождества Жермен. После этого всё решается в две строки.

Задача 2. Докажите, что $n^4 + n^2 + 1$ составное при всех целых $n \geq 2$, и вычислите произведение $\displaystyle P = \prod_{k=2}^{10} (k^4 + k^2 + 1)$.

Источник: тренировочная (части встречаются на олимпиадах уровня муниципального этапа ВсОШ)

Как думать (рассуждение ученика):
1. Что я вижу? $n^4+n^2+1$ — степень 4, три слагаемых. Это похоже на «почти» квадрат $(n^2+1)^2 - n^2$? Проверим: $(n^2+1)^2 = n^4+2n^2+1$, но у нас $n^4+n^2+1$ — на $n^2$ меньше. Значит $(n^2+1)^2 - n^2 - n^2 + n^2$... подождём. Попробуем иначе.
2. Вспомним тождество. $a^4+a^2+1 = (a^2+a+1)(a^2-a+1)$. Проверим: $(a^2+a+1)(a^2-a+1) = ((a^2+1)+a)((a^2+1)-a) = (a^2+1)^2-a^2 = a^4+2a^2+1-a^2 = a^4+a^2+1$. ✓
3. Составность: при $n \geq 2$: $n^2+n+1 \geq 7 > 1$ и $n^2-n+1 \geq 3 > 1$. Оба множителя нетривиальны.
4. Телескоп: $n^4+n^2+1 = (n^2+n+1)(n^2-n+1)$. Заметим, что $n^2+n+1 = (n+1)^2-(n+1)+1$, то есть $n^2+n+1 = f(n+1)$, где $f(k) = k^2-k+1$. Значит$$\prod_{k=2}^{10}(k^4+k^2+1) = \prod_{k=2}^{10}(k^2+k+1)\cdot\prod_{k=2}^{10}(k^2-k+1).$$ Здесь $k^2+k+1 = (k+1)^2-(k+1)+1$ — это $f(k+1)$, а $k^2-k+1 = f(k)$. Поэтому:$$\prod_{k=2}^{10}f(k+1) \cdot \prod_{k=2}^{10}f(k) = \frac{\prod_{k=2}^{11}f(k)}{f(2)} \cdot \prod_{k=2}^{10}f(k) = \frac{f(3)f(4)\cdots f(11)\cdot f(2)f(3)\cdots f(10)}{f(2)}.$$ Телескоп сворачивается:$$P = \frac{\left(\prod_{k=2}^{10} f(k)\right) \cdot \prod_{k=3}^{11} f(k)}{f(2)} = \prod_{k=2}^{10} f(k) \cdot \frac{\prod_{k=3}^{11}f(k)}{f(2)}.$$ Пересчитаем напрямую: $\prod_{k=2}^{10}(k^4+k^2+1) = \prod_{k=2}^{10}f(k+1)\cdot f(k)$. При $k$ от 2 до 10 значения $f(k) = k^2-k+1$:$f(2)=3,\ f(3)=7,\ f(4)=13,\ f(5)=21,\ f(6)=31,\ f(7)=43,\ f(8)=57,\ f(9)=73,\ f(10)=91,\ f(11)=111.$ Тогда:$$P = \prod_{k=2}^{10} f(k) \cdot \prod_{k=3}^{11} f(k) = \frac{f(2)\cdots f(10) \cdot f(3)\cdots f(11)}{1}.$$ Телескоп: произведение $(k^2+k+1)(k^2-k+1)$ при $k=2..10$ — это $f(3)\cdot f(2) \cdot f(4)\cdot f(3) \cdots f(11)\cdot f(10) = f(2) \cdot f(11) \cdot f(3)^2 \cdot f(4)^2 \cdots f(10)^2$. Удобнее: произведение двух соседних «частичных» дал нам $P = f(2)\cdot f(11)\cdot\left(\prod_{k=3}^{10}f(k)\right)^2$. Но проще всего перемножить напрямую.

Решение (составность):

$n^4+n^2+1 = (n^2+n+1)(n^2-n+1)$. При $n \geq 2$: $n^2-n+1 = n(n-1)+1 \geq 3$ и $n^2+n+1 \geq 7$. Оба множителя больше 1, поэтому число составное.

Ответ (составность): доказано.

Что в этой задаче было главным: знать тождество $a^4+a^2+1=(a^2+a+1)(a^2-a+1)$ и уметь применять его к телескопическим произведениям, замечая рекуррентную связь $k^2+k+1 = (k+1)^2-(k+1)+1$.

• Ошибка: Не проверить, что оба множителя больше 1. → Почему неверно: если один из них равен 1, разложение тривиально и не доказывает составность. → Как избежать: после применения тождества всегда явно оценить каждый множитель снизу.

• Ошибка: Перепутать тождество Жермен с обычной суммой четвёртых степеней $a^4+b^4$ (которое не разлагается над $\mathbb{Z}$). → Почему неверно: $a^4+b^4$ и $a^4+4b^4$ — разные выражения; коэффициент 4 принципиален. → Как избежать: запомнить: разлагается $a^4+4b^4$, а не $a^4+b^4$.

• Ошибка: Применять тождество $a^n+b^n=(a+b)(\ldots)$ при чётном $n$. → Почему неверно: для чётного $n$ эта формула не работает. Работает только при нечётном $n$. → Как избежать: помнить условие: сумма нечётных степеней делится на $a+b$; для чётных — только разность.

• Ошибка: При телескопе в произведении $(k^2+k+1)(k^2-k+1)$ забыть выровнять аргументы. → Почему неверно: $k^2+k+1$ — это $f(k+1)$, а $k^2-k+1$ — это $f(k)$; смещение на 1 критично для сокращений. → Как избежать: выписать несколько членов вручную и проследить, что сокращается.

• Ошибка: Использовать тождество $a^4+a^2+1$ как факторизацию над полем, не проверив целочисленность. → Почему неверно: над $\mathbb{Z}$ нужно убедиться, что коэффициенты целые — в данном случае это очевидно, но в других тождествах может быть не так. → Как избежать: перед применением проверить тождество умножением.