делимость φ(n^(2k) + n^k + 1) на 6k

[maxal]

Докажите, что для всяких целых $n\geq 2$ и $k\geq 1$ значение функции Эйлера $\varphi(n^{2k}+n^k+1)$ делится на $6k$.

[vicvolf]

maxal в сообщении #1558659 писал(а):

Докажите, что для всяких целых $n\geq 2$ и $k\geq 1$ значение функции Эйлера $\varphi(n^{2k}+n^k+1)$ делится на $6k$.

Некоторые мысли. Многочлен преобразуется к виду: $n^{2k}+n^k+1=n^k(n^k+1)+1$, т.е является нечетным числом. Если оно простое, то $\varphi(n^{2k}+n^k+1)=n^k(n^k+1)$, где $n^k(n^k+1)$ при $n\geq 2$ и $k\geq 1$ кратен 6k. Если $n^{2k}+n^k+1$ не является простым числом, то он распадается на простые множители, один из которых равен $6k+1$ т.е. имеет вид $(6k+1)a$ (это надо доказать). В силу мультипликативности функции Эйлера в этом случае $\varphi((6k+1)a)=\varphi(6k+1)\varphi(a)=6k\varphi(a)$, т.е.тоже кратен 6k.

[nnosipov]

Думается, данная задача развивает такой известный сюжет: $\varphi(a^n-1)$ делится на $n$ для любых натуральных $a$ и $n$ ($a>1$).

[Dendr]

vicvolf в сообщении #1558885 писал(а):

Если $n^{2k}+n^k+1$ не является простым числом, то он распадается на простые множители, один из которых равен $6k+1$

Легко проверяется, что $m^2+m+1$ (где $m=n^k$, хотя на данном этапе даже не нужно) запишется либо как $6l+1$, либо $3(6l+1)$. Рандомно выбрав разные $m$, можно построить гипотезу, что эта сумма не может иметь простых делителей вида $6i-1$. Для первых чисел (5, 11, 17) это показывается непосредственно, хотя в общем виде пока не удалось доказать. Таким образом, если гипотеза верна, все простые делители $6l+1$ (в том числе, если число само простое) имеют вид $6j+1$, а значит, $\varphi(m^2+m+1)$ наверняка делится на 6.

Наоборот было бы проще ($6l-1$ обязано иметь простой делитель $6i-1$). Здесь же все наметки срываются. Ясно, что если делитель есть, то либо он по меньшей мере второй степени, либо их по меньшей мере два различных. Дальше как-то пытался рассматривать $m^2+m+1$ по модулю 36, но пользы вышло мало.

[nnosipov]

Dendr в сообщении #1558934 писал(а):

Рандомно выбрав разные $m$, можно построить гипотезу, что эта сумма не может иметь простых делителей вида $6i-1$.

То, что все простые делители числа вида $m^2+m+1$ имеют вид $6i+1$ --- это хорошо известный и нетрудно доказываемый факт.

[vicvolf]

vicvolf в сообщении #1558885 писал(а):

Если $n^{2k}+n^k+1$ не является простым числом, то он распадается на простые множители, один из которых равен $6k+1$ т.е. имеет вид $(6k+1)a$ (это надо доказать). В силу мультипликативности функции Эйлера в этом случае $\varphi((6k+1)a)=\varphi(6k+1)\varphi(a)=6k\varphi(a)$, т.е.тоже кратен 6k.

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

То, что все простые делители числа вида $m^2+m+1$ имеют вид $6i+1$ --- это хорошо известный и нетрудно доказываемый факт.

Достаточно доказать, что хотя один простой делитель имеет такой вид и задача решена.

[lel0lel]

$n^{3k}-1\equiv 0\bmod{n^{2k}+n^k+1}$. Пусть $d$ отличный от единицы делитель $3k$ , то $n^{3k/d}-1\not\equiv 0\bmod{n^{2k}+n^k+1}$.

[nnosipov]

vicvolf в сообщении #1558942 писал(а):

Достаточно доказать, что хотя один простой делитель имеет такой вид и задача решена.

Ну да, конечно. Вы напишите полное решение, а мы посмотрим.

[nnosipov]

lel0lel в сообщении #1558944 писал(а):

$n^{3k}-1\equiv 0\bmod{n^{2k}+n^k+1}$. Пусть $d$ отличный от единицы делитель $3k$ , то $n^{3k/d}-1\not\equiv 0\bmod{n^{2k}+n^k+1}$.

Это доказывает делимость на $3k$. При нечетном $k$ недостающая двойка бесплатно из-за четности значений функции Эйлера, а вот при четном $k$ нужно привлекать функцию Кармайкла.

[rightways]

Идея:

Пусть $k=2^sm$, тогда

$$n^{2k}+n^{k}+1=a^{2^{s+1}}+a^{2^s}+1$$

По моему нетрудно доказать что последнее выражение имеет по крайней мере $s+1$ различных простых делителей. (Можно вспомнить Зигмонди).

Используя факт $x^4+x^2+1=(x^2+x+1)(x^2-x+1)$

Тогда какраз то у функции Эйлера будет степень двойки на один выше как минимум

[vicvolf]

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

То, что все простые делители числа вида $m^2+m+1$ имеют вид $6i+1$ --- это хорошо известный и нетрудно доказываемый факт.

Возьмем $m=4$ и получим $m^2+m+1=21=3 \cdot 7$. Сравнение второй степени по любому простому модулю p всегда имеют решение. Если простое число $p>3$, то оно имеет вид либо $p=6k+1$, либо $p=6k-1$. Поэтому все простые числа вида $p=6k+1$ являются делителями многочлена $m^2+m+1$. Но простыми делителями данного многочлена могут быть и $p=3$ и простые вида $p=6k-1$.

[nnosipov]

vicvolf в сообщении #1559050 писал(а):

Возьмем $m=4$ и получим $m^2+m+1=21=3 \cdot 7$.

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

vicvolf в сообщении #1559050 писал(а):

Сравнение второй степени по любому простому модулю p всегда имеют решение. Если простое число $p>3$, то оно имеет вид либо $p=6k+1$, либо $p=6k-1$. Поэтому все простые числа вида $p=6k+1$ являются делителями многочлена $m^2+m+1$. Но простыми делителями данного многочлена могут быть и $p=3$ и простые вида $p=6k-1$.

Должен констатировать, что Вы совершенно не знаете основ: 1-е и 4-е предложения неверны, 2-е тривиально, а 3-е с таким уровнем знаний Вы не докажете (во всяком случае, придется заглянуть в учебник и кое-что предварительно узнать).

-- Пт июл 01, 2022 23:33:04 --

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

Используя факт $x^4+x^2+1=(x^2+x+1)(x^2-x+1)$

Да, именно так.

[vicvolf]

maxal в сообщении #1558659 писал(а):

Докажите, что для всяких целых $n\geq 2$ и $k\geq 1$ значение функции Эйлера $\varphi(n^{2k}+n^k+1)$ делится на $6k$.

Теорема 150 (стр. 130 Бухштаб 1966 г)

Пусть $f(x)=x^n+c_1x^{n-1}+...+c_n$ многочлен с целыми коэффициентами и свободным членом, который не делится на $p$, где $p$ - простое число, причем $p \geq n$. Тогда сравнение $f(x)$ с нулем по модулю $p$ имеет $n$ решений тогда и только тогда, когда все коэффициенты остатка от деления $x^{p-1}-1$ на $f(x)$ кратны $p$. ("добавлю от себя" или остаток от деления равен 0).

В нашем случае, $p=6k+1$, поэтому надо, чтобы многочлен $x^{p-1}-1=x^{6k}-1$ делился на $x^{2k}+x^{k}+1$ без остатка. А это выполняется, так как $x^{6k}-1=(x^{3k}+1)(x^{3k}-1)=(x^{3k}+1)(x^k-1)(x^{2k}+x^{k}+1)$.

Следовательно, многочлен $n^{2k}+n^{k}+1$ имеет простой делитель вида $p=6k+1$. Поэтому, как я раньше говорил, в силу мультипликативности функции Эйлера в этом случае $\varphi((6k+1)a)=\varphi(6k+1)\varphi(a)=6k\varphi(a)$, т.е. кратен 6k.

[maxal]

vicvolf, у нас здесь нет многочленов, так как $n$ хотя и произвольное, но фиксированное число. Аналогично, "вида $p=6k+1$" не имеет смысла, так как $k$ также фиксированное число.

[nnosipov]

vicvolf в сообщении #1559154 писал(а):

Следовательно, многочлен $n^{2k}+n^{k}+1$ имеет простой делитель вида $p=6k+1$.

Это верное утверждение, но оно не имеет отношения к задаче.

vicvolf в сообщении #1559154 писал(а):

в силу мультипликативности функции Эйлера в этом случае $\varphi((6k+1)a)=\varphi(6k+1)\varphi(a)=6k\varphi(a)$

Так можно было бы написать, если $6k+1$ и $a$ взаимно просты. Но ведь $a$ тоже может делиться на $6k+1$.