Делимость на примориал

[Ktina]

Для каждого примориала $P$ найти все натуральные $n$ такие, что $P|n^n+1$

[mihiv]

Годятся числа: $n=kP-1,k=1,2,\dots$,есть ли еще решения,не знаю.

[Ktina]

mihiv в сообщении #551884 писал(а):

Годятся числа: $n=kP-1,k=1,2,\dots$,есть ли еще решения,не знаю.

Да, незадача вышла. Я нашла решение только для первых четырёх примориалов: 2, 6, 30 и 210. Там действительно годятся только числа вида $kP-1$.

[temp03]

mihiv в сообщении #551884 писал(а):

Годятся числа: $n=kP-1,k=1,2,\dots$,есть ли еще решения,не знаю.

Нету. Достаточно взять какой-нибудь маленький праймориал, например $5\#$ или $7\#$ и убедиться что из всех $n^n+1$ на него делятся только если $P\ |\ n+1$. Фишка в том, что праймориал состоит из последовательных простых чисел, включая простые Софи Жермен, поэтому $\left(\dfrac{n^n+1}{n+1},P\right)=1$
-- Ср мар 28, 2012 13:44:10 --

По-моему, тут даже можно обобщить до $a^n+b^n$ делится на $k\#$ только если $a+b\div k\#$

[mihiv]

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

праймориал состоит из последовательных простых чисел, включая простые Софи Жермен, поэтому $\left(\dfrac{n^n+1}{n+1},P\right)=1$

Не могли бы Вы пояснить этот момент?

[temp03]

Возьмём $7\#=210$. Тогда есть несколько вариантов:
1) если $\left(\dfrac{a^n+b^n}{a+b},210\right)=7$, то $n\leq7$. Если $n=7$, то $a+b\div7$. Но тогда $a+b\div210$.
2) если $\left(\dfrac{a^n+b^n}{a+b},210\right)<7$. Пусть $n=3$, то $\dfrac{a^n+b^n}{a+b}$ может делиться на $7$ и при этом $7\not|\ a+b$. Контрпример $\dfrac{19^3+11^3}{19+11}\div7$, однако $7\not|\ 19+11$.

Так что в случае $a^n+b^n$ предположение

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

По-моему, тут даже можно обобщить до $a^n+b^n$ делится на $k\#$ только если $a+b\div k\#$

неверное.

mihiv, там надо смотреть случай 2) для $n^n+1$. Т.е. $n<\dfrac p2$. Но праймориал растёт быстрее чем $\left(\dfrac p2\right)^{\frac{p}{\ln p}}$. В общем это очень долгая история. И труднодоказуемая.

[mihiv]

У меня получилось доказать вот что:пусть уже доказано,что $1).p_m\# |n^n+1$ только для чисел вида $n=kp_m\# -1,k=1,2,\dots $ и 2).на отрезке $[\frac {p_m+1}2,p_{m+1}]$ есть по крайней мере одно простое число $q$,такое,что $2q+1$ также простое,тогда $p_{m+1}\# |n^n+1$ только для чисел вида $n=kp_{m+1}\# -1$.

Для каждого конкретного примориала условие 2). легко проверяется(оно скорее всего выполняется для всех $p_{m+1}$),поэтому,начав с $p_2\# $,можно последовательно переходить к следующим примориалам.

[temp03]

Наверное.

(Оффтоп)

ужасно болит голова. Сначала я ответил на ваше сообщение, потом исправил. Оказалось что исправил неверно, а было верно, так правил, правил, пока не вышел час правки. В общем, я уже не помню почему я и как написал тогда.

[mihiv]

mihiv в сообщении #553861 писал(а):

получилось доказать

Не получается,нашел ошибку.

[temp03]

mihiv, в общем идея такая: праймориал $7\#$ содержит все простые от $2$ до $7$. Поэтому если $\dfrac{n^n+1}{n+1}$ делится на какое-то простое $7|\ 7\#$, а $n+1$ не делится, то $n\div p_i$ такое, что $7=2kp_i+1$ (это $3$).
Но тогда чтобы $n^n+1\div 7\#$ необходимо, чтобы $n+1\div p_i$, но это невозможно, т.к. $n\div p_i$. Противоречие.
Т.е. таких $n$ не существует.