Тройка и треугольные числа

[Dave]

a) Треугольным называется число, представимое в виде $\frac {n(n+1)} 2$ для некоторого целого $n$. Пусть $a$ и $b$ - треугольные числа. Докажите, что любой простой делитель $p \ne 3$, входящий в разложение числа

$$6a+2b+1$$

на простые множители в нечётной степени, даёт остаток $1$ при делении на $3$.
б) Пусть $n$ - любое натуральное число. Докажите, что любой простой делитель $p \ne 3$ числа

$$n^2+n+1$$

даёт остаток $1$ при делении на $3$, а $3$ не может входить в разложение этого числа в степени большей, чем $1$.

[temp03]

б) так это просто теорема $a^{n-1}+a^{n-2}+...+a^2+a+1=\prod\limits_{i=1}^m{(2k_in+1)}$, если $a\neq pn+1$, где $2k_in+1$ - некоторые простые числа.

[nnosipov]

А в чём прикол? Если есть продолжение, давайте сразу.

[Dave]

temp03 в сообщении #579091 писал(а):

б) так это просто теорема $a^{n-1}+a^{n-2}+...+a^2+a+1=\prod\limits_{i=1}^m{(2k_in+1)}$, если $a\neq pn+1$, где $2k_in+1$ - некоторые простые числа.

Что за теорема? $3^5+3^4+3^3+3^2+1=364=2^2 \cdot 7 \cdot 13$.
И что она даст, если $a=pn+1$ ?

[nnosipov]

Пусть $p$ --- нечётное простое число. Тогда все простые делители кругового многочлена

$$ \Phi_p(x)=\frac{x^p-1}{x-1}=x^{p-1}+\ldots+x+1 $$

суть $p$ и все простые числа $q \equiv 1 \pmod{2p}$. Кроме того, $\Phi_p(x) \not\equiv 0 \pmod{p^2}$ при любом целом $x$. Этот факт хорошо известен и сам по себе вряд ли может быть олимпиадной задачей, его надо чем-то дополнять. Вот пример такой олимпиадной задачи: Найдите все пары $(x,y)$ целых чисел, удовлетворяющих равенству

$$ \frac{x^7-1}{x-1}=y^5-y^4-2y^2+1. $$

[temp03]

Dave в сообщении #579220 писал(а):

Что за теорема? $3^5+3^4+3^3+3^2+1=364=2^2 \cdot 7 \cdot 13$.
И что она даст, если $a=pn+1$ ?

я забыл дописать, что $n$ (показатель степени) - должно быть простое, а у вас $n=6$. Тогда многочлен $3^5+3^4+3^3+3^2+3+1$ раскладывается как $\dfrac{3^2-1}{3-1}\cdot(3^4+3^2+1)=(3+1)(3^4+3^2+1)$. Поэтому делится на $4\neq2kn+1$. Если же $n$ - простое, то многочлен неприводимый.

[Dave]

nnosipov в сообщении #579260 писал(а):

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

Вот я и дополнил. Первой частью задачи, которую пока никто не решил.

[nnosipov]

Dave в сообщении #579458 писал(а):

Первой частью задачи, которую пока никто не решил.

Да все обленились Может, что-нибудь повеселее придумаем про бинарные квадратичные формы? Мне понравился вот такой сюжет:
Сколько решений в натуральных числах при данном натуральном $n$ имеет уравнение $3x^2+5y^2=2^n$?
Можно ли это как-то обобщить?

[Sonic86]

(Оффтоп)

Может я обленился, но у меня ни одна из задач не получается а как решать 1-ю задачу? - там же квадратичная форма неоднородная

nnosipov в сообщении #579475 писал(а):

Сколько решений в натуральных числах при данном натуральном $n$ имеет уравнение $3x^2+5y^2=2^n$?

нашел пока такое: если $n$ четно, то решений нет, а если нечетно, то решений $\frac{n-1}{2}$. Серию решений выписать не получилось - может руки кривые, а может $\mathbb{Z}[\sqrt{-15}]$ - кольцо с числом классов =2.

[nnosipov]

Sonic86 в сообщении #579741 писал(а):

Может я обленился, но у меня ни одна из задач не получается а как решать 1-ю задачу? - там же квадратичная форма неоднородная

А выделить полные квадраты и перейти к другим переменным?

Sonic86 в сообщении #579741 писал(а):

если $n$ четно, то решений нет, а если нечетно, то решений $\frac{n-1}{2}$. Серию решений выписать не получилось - может руки кривые, а может $\mathbb{Z}[\sqrt{-15}]$ - кольцо с числом классов =2.

Ответ правильный. Можно ли сами решения как-то выписать --- вопрос интересный. Да и пересчитать их совсем уж просто у меня не получилось --- только индукцией.

[Dave]

nnosipov в сообщении #579475 писал(а):

Сколько решений в натуральных числах при данном натуральном $n$ имеет уравнение $3x^2+5y^2=2^n$?

Хитрость заключается в том, что решать нужно не в натуральных, а в целых числах. Про $(x,y) \leftrightarrow (2x,2y)$ и ежу понятно. Что же касается ровно одного (если считать натуральные решения) нового решения, появляющегося с каждым увеличением $n$ на $2$, то вот оно волшебное преобразование, дающее, начиная с пары $(1,1)$, новое решение на каждом шаге и доказывающее, что других новых решений нет:

$$(x,y) \leftrightarrow \left(\frac {x+5y} 2, \frac {y-3x} 2\right).$$

Пара будет получаться всегда целой и нечётной, т.к. всегда $x+y \equiv 2 \pmod 4$ (это св-во и нечётность доказываются по индукции параллельно). Обратное преобразование

$$(a,b) \rightarrow \left(\frac {a-5b} 8,\frac {3a+b} 8\right)$$

из каждого нечётного решения при $n \geqslant 5$ будет давать целочисленное и опять нечётное решение для $n-2$, нужно только правильно расставить знаки у $a$ и $b$. К примеру, мы должны брать не пару $(3,1)$, а пару $(3,-1)$. Существование нужной расстановки знаков показывается анализом по модулю $32$ исходного уравнения.

nnosipov в сообщении #579748 писал(а):

Можно ли сами решения как-то выписать --- вопрос интересный.

А почему же нельзя? Как-нибудь через степени комплексных чисел. Или через синусы-косинусы.

[nnosipov]

Мне было удобней работать с уравнением $X^2+15Y^2=3 \cdot 2^n$. Нужный шаг вниз придумался сам собой: равенство нужно сократить на $4$, а для этого достаточно поделить $X+Y\sqrt{-15}$ на $(1+\sqrt{-15})/2$, ведь квадрат модуля последнего числа как раз равен $4$.