3^n+4^n

[zykov]

Есть задача, которую давно не получается решить.
"Доказать, что если $3^n+4^n$ делится на $n$ (где $n>1$), то это $n$ делится на 7".

Элементарными методами ничего не выходит. Возможно нужны какие-то продвинутые методы из теории чисел.
Возможно теорема Зигмонди как-то поможет.
Может тут кто хорошо разбирается в теории чисел и видит как это решается?

Элементарными методами легко получить, что $n$ должно быть нечётное и что если $n$ простое, то это должно быть $7$ (т.е. либо это 7, либо составное).
Ещё легко видно, что если $n$ нечётно, то $3^n+4^n$ делится на 7, это правда не гарантирует, что множитель 7 будет внутри $n$.

Вычислительный эксперимент показал, что например подходят $n=7^k$.
Ещё подходят $n=7^k \cdot 379^m$ (где $k \geq 1$ и $m \geq 0$).
Почему именно $379$?
Есть гипотеза, это потому что $3^7+4^7=7^2 \cdot 379$.
Или в общем виде, что если $n$ - подходит, то из простых делителей $3^n+7^n$ можно составить другие подходящие $n$.
Например $3^{49}+4^{49}=7^3 \cdot 379 \cdot 74163546829 \cdot 32871239562379$ и тогда по гипотезе можно ещё составить подходящие $n$ с этими двумя множителями.

Впрочем может это и не нужно, если доказать делимость подходящего $n$ на $7$ гораздо проще, чем найти все подходящие $n$.

PS: Наверно это обобщается на произвольное простое $p$ вместо 7, так что $a+b=p$ и нужно доказать делимость $n$ на $p$, если $a^n+b^n$ делится на $n$.
Например, для $1^n+2^n$ эта гипотеза с составлением $n$ из простых делителей вроде как работает.

[Gagarin1968]

zykov в сообщении #1546330 писал(а):

Элементарными методами ничего не выходит

А если попробовать биномиальное разложение $3^n+(7-3)^n$? Ведь если $n$ нечётное, то члены с $3^n$ сокращаются. Это ничего не даёт?
Я не проверял, просто как идея.

[zykov]

Даёт вот это:

zykov в сообщении #1546330 писал(а):

что если $n$ простое, то это должно быть $7$

[lel0lel]

Рассмотреть для начала случай $n=pq$, где $p, q$ различные нечетные простые отличные от $3$ и от $7$. Тогда $(3/4)^{pq}\equiv -1\bmod{pq}$, следовательно $p\mid {\frac{q-1}{2^k}}$, где $k$ показатель степени двойки в факторизации числа $q-1$. Аналогично $q\mid{\frac{p-1}{2^m}}$. Одновременно оба условия выполнены быть не могут, так как одно из чисел больше другого.

[nnosipov]

zykov в сообщении #1546330 писал(а):

Элементарными методами ничего не выходит.

Есть элементарное решение. Вообще, это довольно известный сюжет из олимпиадной теории чисел (см., например, Сендеров В., Спивак А. Задача 4493 // Математика в школе. 2000. № 3. С. 74). В решении используется принцип крайнего: нужно рассмотреть наименьший простой делитель числа $n$.

[zykov]

"принцип крайнего" - это тоже что "Proof by infinite descent"?

[nnosipov]

Да нет, это скорее типа https://www.mccme.ru/free-books/prasolo ... m/gl20.htm Кстати, относительно недавно здесь уже обсуждалась подобная задача (а именно, задача 4 с 40-й IMO). Вот здесь: topic147387.html

[zykov]

То, что $n$ не делится на 2, 3, 5 - легко показать.
Сумма степеней не делится ни на 2, ни на 3.
Сумма степеней делится на 5 только при $n=4k-2$, где $k\geq 1$. Т.е. может делится только для чётного $n$. Но подходящие $n$ нечётные.

Что дальше - не ясно. Уже пробовал представить $n=q\cdot m$, где $q$ простое.
Тогда по модулю $q$ будет $(3^q)^m+(4^q)^m \equiv 0$.
По малой теореме Ферма $3^q \equiv 3$ и $4^q \equiv 4$ по модулю $q$.
Значит $3^m+4^m \equiv 0$ по модулю $q$ (а надо бы по модулю $m$). И что дальше?

[lel0lel]

zykov в сообщении #1546435 писал(а):

что дальше?

поделить на $4^m$, это можно, так как $(q,2)=1.$ И подумать чему может быть равно $(q-1,m)$

[zykov]

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

чему может быть равно $(q-1,m)$

Никаких идей. Тут есть какая-то теорема?

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

следовательно $p\mid {\frac{q-1}{2^k}}$, где $k$ показатель степени двойки в факторизации числа $q-1$. Аналогично $q\mid{\frac{p-1}{2^m}}$. Одновременно оба условия выполнены быть не могут, так как одно из чисел больше другого.

Тоже не понял, откуда это.
Например, если $p=2^{k_1}+1$ и $q=2^{k_2}+1$, то оба делятся на 1 без проблем.

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

где $p, q$ различные нечетные простые отличные от $3$ и от $7$

Где использовалось, что они отличны от $3$ и $7$?

[lel0lel]

zykov в сообщении #1546450 писал(а):

Никаких идей. Тут есть какая-то теорема?

Следствие МТФ: если $a^n\equiv 1\pmod p$ и $a\not\equiv 1\pmod p$, то $(n, p-1)>1$.

zykov в сообщении #1546450 писал(а):

Например, если $p=2^{k_1}+1$ и $q=2^{k_2}+1$, то оба делятся на 1 без проблем

$a\mid b$ читается "a делит b".

zykov в сообщении #1546450 писал(а):

Где использовалось, что они отличны от $3$ и $7$?

если бы была тройка, то решений очевидно нет, потому и городить нечего. А если бы была семёрка, то сравнение $(3/4)^m\equiv -1\pmod 7$ было бы верным при любом нечётном $m$, поэтому одного условия не появилось бы, и всё бы сработало, поэтому семёрку исключили, чтобы рассмотреть случай, который ведёт к противоречию.

В общем, в этой задаче важно знать приведённое в начале следствие МТФ, тогда и решится всё легко. И да, нужно рассматривать по минимальному простому модулю.

[zykov]

lel0lel
Спасибо!
Теперь всё понятно.
Получается, что $m$ делится на делитель $q-1$, который меньше $q$. Значит минимальный делитель $n$ должен быть 7.

[nnosipov]

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

В общем, в этой задаче важно знать приведённое в начале следствие МТФ

Я бы не привязывал все это к МТФ, хотя она здесь и нужна. Есть более фундаментальное соображение: если $x^a=1$ и $x^b=1$, то $x^d=1$, где $d=\gcd{(a,b)}$.

[zykov]

Тут важно не то что $x^d \equiv 1$, а то что $\gcd{(a,b)} > 1$.
Т.е. более фундаментальное соображение тут то, что если $P_q(x)$ - порядок числа $x$ по модулю $q$ (наименьшая степень числа $x$ эквивалентная 1 по модулю $q$), то любая другая степень этого числа эквивалентная 1 будет кратна этому порядку.
Из МТФ мы тут получаем только то, что степень $q-1$ даёт 1. А далее получаем, что оба $m$ и $q-1$ делятся на порядок числа, который больше 1. А порядок $3/4$ больше 1 для всех простых модулей кроме 2 и 7. (Для модуля 2 можно было бы взять $4/3$ вместо $3/4$.)

Интересно, что это доказательство обобщается на произвольный случай $a^n+b^n$, где $a+b=p$ равно простому числу.
$a$ и $b$ взаимно простые, т.е. для любого простого модуля $q$ можно выбрать либо $a$, либо $b$, такой что это число не делится на $q$.

[lel0lel]

zykov в сообщении #1546509 писал(а):

порядок $3/4$ больше 1 для всех простых модулей кроме 2 и 7.

Вообще по модулю два про порядок говорить не нужно, а по модулю семь порядок равен $2$.