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

[vicvolf]

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

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

В главе "Сравнение с неизвестной величиной" Бухштаб пишет, что $x$ - принимает только целые значения и рассматриваются только многочлены с целыми коэффициентами. Указанное мною решение также справедливо для целых значений $x$. Называть ли эту последовательность многочленом или по-другому это дело вкуса. Важно другое. Функция Эйлера является арифметической функций, т.е. функция натурального аргумента. По определению $\varphi(1)=1$. Остальные натуральные значения аргумента можно представить в виде $m=ap$, где $a$ - натуральное число ( в частности равное 1), $p$ - простое число. Поэтому в силу мультипликативности функции Эйлера справедливо:$\varphi(ap)=\varphi(a)(p-1)$.
Для того, чтобы $\varphi(a)(p-1)$ делилось на $6k$ должно $p=6k+1$. Значит, если доказать, что при любом значении $m=n^{2k}+n^k+1$ оно делится на $p=6k+1$, то $\varphi(n^{2k}+n^k+1)$ будет делиться на $6k$. Доказательство этого факта с помощью данной теоремы я и привел. Наверно возможны и другие доказательства. Было бы интересно посмотреть.

-- 04.07.2022, 13:43 --

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

Но ведь $a$ тоже может делиться на $6k+1$.

Может, но это будет уже дополнительный множитель, так как я доказал, что последовательность $n^{2k}+n^k+1$ делится для любого $n$ на $p=6k+1$.

[maxal]

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

Может, но это будет уже дополнительный множитель, так как я доказал, что последовательность $n^{2k}+n^k+1$ делится для любого $n$ на $p=6k+1$.

Например, для $n=3$ и $k=1$ этой делимости нет: $3^2+3+1=13$ не делится на $6\cdot 1+1=7$.

-- Mon Jul 04, 2022 11:13:16 --

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

Указанное мною решение также справедливо для целых значений $x$.

Вы не понимаете, что в этой задает нет переменных. Если бы я спрашивал найти значение $n$, которое чему-то там удовлетворяет, то да $n^{2k}+n^k+1$ можно было рассматривать как многочлен от $n$. Но в данной задаче у вас нет свободы варьировать $n$ или $k$. Они произвольные, но фиксированные.

[nnosipov]

vicvolf
У Вас неверно просто все, начиная от понимания самого смысла задачи и кончая мелкими деталями.

[vicvolf]

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

Вы не понимаете, что в этой задает нет переменных. Если бы я спрашивал найти значение $n$, которое чему-то там удовлетворяет, то да $n^{2k}+n^k+1$ можно было рассматривать как многочлен от $n$. Но в данной задаче у вас нет свободы варьировать $n$ или $k$. Они произвольные, но фиксированные.

Спасибо, я все понял. Я доказал другое утверждение:

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

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

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

Это верное утверждение.

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

vicvolf
У Вас неверно просто все, начиная от понимания самого смысла задачи и кончая мелкими деталями.

У Вас есть правильное доказательство? Было бы интересно ознакомиться.

[maxal]

Мое решением состоит из двух ингредиентов:

* если $k=3^t\cdot m$, где $3\nmid m$, то

$$\Phi_3(n^k) = \prod_{d\mid m} \Phi_{d\cdot 3^{t+1}}(n)$$

* $\Phi_{3^{t+1}m}(n)$ делится на примитивный простой делитель $q\mid n^{3^{t+1}m}-1$, который имеет вид $q=3^{t+1}m\cdot \ell + 1$ для некоторого $\ell$. Поэтому $\varphi(\Phi_3(n^k))$ делится на $q-1$.

Остается заметить, что
Если $m=1$, то $6k=3^{t+1}\cdot m\cdot 2$ делит $q-1$.
Если $m>1$, то $\Phi_{3^{t+1}}(n)$ делится на какое-то нечетное простое $r\ne q$, и соответственно $3k=3^{t+1}\cdot m$ делит $q-1$ и $2$ делит $r-1$.

[xagiwo]

Эх, вчера вечером только начал записывать решение...

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

$\Phi_{3^{t+1}m}(n)$ делится на примитивный простой делитель $q\mid n^{3^{t+1}m}-1$, который имеет вид $q=3^{t+1}m\cdot \ell + 1$ для некоторого $\ell$

А это как доказываете? Я вот верю, что все простые делители $\Phi_{3^{t+1}m}(n)$ имеют либо вид как $q$, либо делят $3m$. Причём даже могу поверить, что тройки там нет. Но почему $\Phi_{3^{t+1}m}(n)$ не может быть составлено из делителей $m$?
Моё недоделанное решение сводило всё к случаю, когда $m$ — степень простого $p$, и тогда $\Phi_{3^{t+1}m}(n)$ либо достаточно большая для наших целей степень числа $p$, либо имеет делитель нужного вида.

[maxal]

xagiwo в сообщении #1559603 писал(а):

А это как доказываете? Я вот верю, что все простые делители $\Phi_{3^{t+1}m}(n)$ имеют либо вид как $q$, либо делят $3m$. Причём даже могу поверить, что тройки там нет. Но почему $\Phi_{3^{t+1}m}(n)$ не может быть составлено из делителей $m$?

Из разложений $x^s-1$ в произведение круговых многочленов следует, что всякий примитивный простой делитель $n^s-1$ обязан делить $\Phi_s(n)$. Более детальное утверждение есть в Википедии.
Ну а существование примитивных простых делителей нам гарантирует теорема Зигмонди.

[maxal]

Кстати, у случая простого $n$ возможно есть комбинаторная интерпретация - см. A058241.

[nnosipov]

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

У Вас есть правильное доказательство?

Да, разумеется.

Пусть $d$ --- порядок числа $a$ по модулю $a^{2n}+a^n+1$. Имеем

$$ a^{3n} \equiv 1 \pmod{a^{2n}+a^n+1}, $$

откуда следует, что $3n=dk$ для некоторого натурального $k$. Если $k>1$, то

$$ a^{3n/k} \equiv 1 \pmod{a^{2n}+a^n+1}, $$

что невозможно, так как

$$ a^{3n/k}-1 \leqslant a^{3n/2}-1<a^{2n}+a^n+1. $$

Значит, $k=1$ и $d=3n$. Как следствие, $\lambda(a^{2n}+a^n+1)$ и $\varphi(a^{2n}+a^n+1)$ делятся на $3n$. При нечетном $n$ отсюда следует делимость $\varphi(a^{2n}+a^n+1)$ на $6n$. Пусть $n=2^sm$, где $s \geqslant 1$ и $m$ нечетно. Рассмотрим каноническое разложение

$$ a^{2n}+a^n+1=\prod_{i=1}^tp_i^{\alpha_i}, \eqno(*) $$

в котором все $p_i$ нечетны. Формула

$$ \lambda(a^{2n}+a^n+1)=\mathrm{lcm}{(p_1^{\alpha_1-1}(p_1-1),\dots,p_t^{\alpha_t-1}(p_t-1))} $$

позволяет заключить, что $p_i-1$ делится на $2^s$ при некотором $i$. Тогда из формулы

$$ \varphi(a^{2n}+a^n+1)=\prod_{i=1}^tp_i^{\alpha_i-1}(p_i-1) $$

вытекает делимость $\varphi(a^{2n}+a^n+1)$ на $2^{s+1}$ (а значит, и на $6n$), как только $t>1$. Осталось отметить, что в $(*)$ случай $t=1$ исключен, ибо имеет место разложение

$$ a^{2n}+a^n+1=b^4+b^2+1=(b^2+b+1)(b^2-b+1), $$

где $b=a^{2^{s-1}m}$, при этом $\gcd{(b^2+b+1,b^2-b+1)}=1$.

[Lia]

vicvolf
Ваше последнее сообщение не привносило ничего нового в обсуждение и представляло собой нарезку из цитат темы. Удалено.

[vicvolf]

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

Из разложений $x^s-1$ в произведение круговых многочленов следует, что всякий примитивный простой делитель $n^s-1$ обязан делить $\Phi_s(n)$.

Значит обобщая $\varphi (n^{(p-1)k}+n^{(p-2)k}+...+n^k+1)$ делится на $2pk$, где $p>2$ - простое число, $n \geq 2$, $k \geq 1$ - натуральные числа?