Задачка на делимость

[rightways]

Докажите, что любой простой делитель числа $7n^2(n+1)-1$ ($n\in N$) имеет вид $p=7k±1$.

[rightways]

кто решил?

[worm2]

Я, наверное, сразу скажу, что не смогу решить.
Но $7k\pm 1$ нужно заменить на $14k\pm 1$.

[nnosipov]

worm2 в сообщении #1018377 писал(а):

Но $7k\pm 1$ нужно заменить на $14k\pm 1$.

На самом деле не нужно, это помешает правильному взгляду на этот факт. Не хочу лишать удовольствия решающих (спасибо ТС за такой красивый пример, где он их только берёт ), поэтому дам подсказку: полезно решить уравнение $7x^3+7x^2-1=0$ в обычных вещественных числах; если корни будут найдены в правильном виде, это намекнёт, в какую сторону копать дальше.

Кстати, утверждение можно усилить: при простом $p$ сравнение $7x^3+7x^2-1 \equiv 0 \pmod{p}$ разрешимо тогда и только тогда, когда $p \equiv \pm 1 \pmod{7}$.

[Sonic86]

(Оффтоп)

rightways в сообщении #1018353 писал(а):

кто решил?

Я с большой вероятностью не смогу. У меня была аналогичная задача topic31013.html (1-е 4 поста можно не читать), но у меня там оказалось все сильно проще. Здесь почему-то эта техника не работает, либо недостаточна.

Я свел задачу к рассмотрению многочлена $x^3-7x-7$. Его значения тоже делятся только на $p=7\pm 1$ или на 7, но формула Кардано дает плохие корни.
Я был бы рад какой-нибудь подсказке.

[nnosipov]

Sonic86, здесь ровно то же самое, так что Вы фактически решили эту задачу ещё в 2010 году Многочлен $7x^3+7x^2-1$ также имеет корни в круговом поле (догадайтесь, в каком), только не надо их находить с помощью формулы Кардано. А дальше стандартная техника, связанная с конечными полями и их квадратичными расширениями. (Можно также вспомнить, как круговые многочлены разлагаются над конечным полем.)

[Коровьев]

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

Я был бы рад какой-нибудь подсказке.

$$ x^3 - 7x - 7 = \left( {x - \left( {\xi _2 - \xi _1 } \right)} \right)\left( {x - \left( {\xi _3 - \xi _2 } \right)} \right)\left( {x - \left( {\xi _1 - \xi _3 } \right)} \right) $

$\xi _1 =e^{2\pi i/7}+e^{-2\pi i/7};$

$\xi _2 =e^{4\pi i/7}+e^{-4\pi i/7};$

$\xi _3 =e^{6\pi i/7}+e^{-6\pi i/7};$


Знал по случаю, проверил PARI

[nnosipov]

Всё это ненужные частности. Можно взять любой нормированный неприводимый кубический многочлен $f(x)$ с целыми коэффициентами, имеющий корень в поле $\mathbb{Q}(\zeta+\zeta^{-1})$, где $\zeta^7=1$. Сравнение $f(x) \equiv 0 \pmod{p}$ имеет решения тогда и только тогда, когда $p \equiv \pm 1 \pmod{7}$ или $p=7$.

[Sonic86]

Коровьев в сообщении #1018932 писал(а):

$$ x^3 - 7x - 7 = \left( {x - \left( {\xi _2 - \xi _1 } \right)} \right)\left( {x - \left( {\xi _3 - \xi _2 } \right)} \right)\left( {x - \left( {\xi _1 - \xi _3 } \right)} \right) $$

Знал по случаю

Ну везет. А как найти, если не знал?

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

Можно взять любой нормированный неприводимый кубический многочлен $f(x)$ с целыми коэффициентами, имеющий корень в поле $\mathbb{Q}(\zeta+\zeta^{-1})$, где $\zeta^7=1$.

Вот до поля я догадался. Я только не понимаю, как определить, что указанный многочлен имеет там корень. Я, правда, пока мало думал. Я пока взял в лоб $x=au^2+bu+c, u=\zeta+\zeta^{-1}$, пытался подставить, получается система из 3-х алгебраических уравнений с 3-я неизвестными над $\mathbb{Q}$. М.б. она, конечно, легкая, но я ее не выписал - многобуковок.

[nnosipov]

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

Я только не понимаю, как определить, что указанный многочлен имеет там корень. Я, правда, пока мало думал.

Ну, в компьютерной алгебре есть такие алгоритмы. Не только корни в алгебраических полях можно находить, но и даже факторизовать над ними. Так что просто берём Maple, и он всё делает.

-- Вс май 24, 2015 13:49:43 --

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

Я пока взял в лоб $x=au^2+bu+c, u=\zeta+\zeta^{-1}$, пытался подставить, получается система из 3-х алгебраических уравнений с 3-я неизвестными над $\mathbb{Q}$.

Да, так можно делать. Потом Грёбнером её, а найти рациональные корни многочлена от одной переменной труда не составит. Здесь нет теории чисел, здесь именно алгебра.

[Коровьев]

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

А как найти, если не знал?

Для небольших простых $P$ можно и "в ручную".
Возьму данный пример.

$x^3 - 7x - 7 = 0$

$$\[ x = \sqrt[3]{{\frac{7}{2} + \sqrt {\left( {\frac{7}{2}} \right)^2 - \left( {\frac{7}{3}} \right)^3 } }} + \sqrt[3]{{\frac{7}{2} - \sqrt {\left( {\frac{7}{2}} \right)^2 - \left( {\frac{7}{3}} \right)^3 } }} = \frac{1}{3}\left( {\sqrt[3]{{3 \cdot 7\left( {5 + \varepsilon } \right)}} + \sqrt[3]{{3 \cdot 7\left( {5 + \varepsilon ^2 } \right)}}} \right) \]$

$$\[ \left\{ \begin{array}{l} 3 = - \left( {1 + 2\varepsilon } \right)^2 = - \left( {1 + 2\varepsilon ^2 } \right)^2 \\ \left( {5 + \varepsilon } \right) = \left( {2 + 3\varepsilon ^2 } \right)\left( {1 + 2\varepsilon } \right) \\ \left( {5 + \varepsilon ^2 } \right) = \left( {2 + 3\varepsilon } \right)\left( {1 + 2\varepsilon ^2 } \right) \\ \end{array} \right. \]$

И теперь самое важное соотношение

$$\[ \left\{ \begin{array}{l} \left( {\xi _1 + \varepsilon \xi _2 + \varepsilon ^2 \xi _3 } \right)^3 = 7\left( {2 + 3\varepsilon } \right) \\ \left( {\xi _1 + \varepsilon ^2 \xi _2 + \varepsilon \xi _3 } \right)^3 = 7\left( {2 + 3\varepsilon ^2 } \right) \\ \end{array} \right. \]$

В теме Представление простого P=3n+1 формой P=A^2-AB+B^2 получена формула для любого P. При P=7 получаем это соотношение.

$$\[ x_1 = \sqrt[3]{{3 \cdot 7\left( {5 + \varepsilon } \right)}} +\sqrt[3]{{3 \cdot 7\left( {5 + \varepsilon ^2 } \right)}} = - \left( {\xi _1 + \varepsilon ^2 \xi _2 + \varepsilon \xi _3 } \right)\left( {1 + 2\varepsilon } \right) - \left( {\xi _1 + \varepsilon \xi _2 + \varepsilon ^2 \xi _3 } \right)\left( {1 + 2\varepsilon ^2 } \right) = \xi _3 - \xi _2 \]$


Правка.
$\[ \begin{array}{l} x_1 = \frac{1}{3}\sqrt[3]{{3 \cdot 7\left( {5 + \varepsilon } \right)}} + \frac{1}{3}\sqrt[3]{{3 \cdot 7\left( {5 + \varepsilon ^2 } \right)}} = \\ - \frac{1}{3}\left( {\xi _1 + \varepsilon ^2 \xi _2 + \varepsilon \xi _3 } \right)\left( {1 + 2\varepsilon } \right) - \frac{1}{3}\left( {\xi _1 + \varepsilon \xi _2 + \varepsilon ^2 \xi _3 } \right)\left( {1 + 2\varepsilon ^2 } \right) = \xi _3 - \xi _2 \\ \end{array} \] $