Уравнение в простых числах

[nnosipov]

Ktina в сообщении #706522 писал(а):

Данное в условии задачи уравнение равносильно уравнению

$$\frac{7^x-1}{7-1}=2^{y-1}$$

Кстати, глядя на эту запись, вспомнил такую задачу: если для простого числа $p$ и натуральных чисел $q>1$, $m$, $n$ имеет место равенство

$$ \frac{q^m-1}{q-1}=p^n, $$

то $m$ --- простое число.

Deggial: Тема отделена от темы Уравнение в натуральных числах, помогите разобраться

[Ktina]

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

Кстати, глядя на эту запись, вспомнил такую задачу: если для простого числа $p$ и натуральных чисел $q>1$, $m$, $n$ имеет место равенство

$$ \frac{q^m-1}{q-1}=p^n, $$

то $m$ --- простое число.

Тут уже одними модулями не обойтись

[nnosipov]

Да, здесь другие идеи, но рассуждения в целом стандартны.

[Ktina]

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

Да, здесь другие идеи, но рассуждения в целом стандартны.

Кстати, $m$ и $n$ тоже должны быть больше единички, иначе утверждение не верно.

[nnosipov]

Ktina в сообщении #706547 писал(а):

Кстати, $m$ и $n$ тоже должны быть больше единички, иначе утверждение не верно.

Не вижу, почему. Ведь $p$ --- простое, а значит, $p \geqslant 2$.

[Ktina]

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

Не вижу, почему. Ведь $p$ --- простое, а значит, $p \geqslant 2$.

Да, Вы правы.

[Aritaborian]

А теорема Ферма тут не поможет?

[Ktina]

Aritaborian в сообщении #706634 писал(а):

А теорема Ферма тут не поможет?

Я тоже думала через МТФ решать, но не нашла, как именно.

[Sonic86]

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

если для простого числа $p$ и натуральных чисел $q>1$, $m$, $n$ имеет место равенство

$$ \frac{q^m-1}{q-1}=p^n, $$

то $m$ --- простое число.

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

Да, здесь другие идеи, но рассуждения в целом стандартны.

Интересно, каковы они здесь? Неужели это реально решить простыми соображениями?!

(неправильное решение)

Это избыточно сложное и ошибочное решение.

Я устал решать , поэтому воспользуюсь танчиками:
$\frac{q^m-1}{q-1}=\prod\limits_{d\mid m, d\neq 1}\Phi_d(q)=p^n$
$\Phi_d(q)>q-1$. Для использования $\Phi_d(q)>1$ необходимо $q>2$, потому случай $q=2$ сначала разберем отдельно:

1) Пусть $q=2$. Получаем $2^m-1=p^n\Leftrightarrow 2^m=p^n+1$, $p$ нечетное. Если $2\mid n$, то $4\nmid p^n+1$, значит $2\nmid n$, значит $p^n+1=(p+1)(p^{n-1}+...+1)$. В правой скобке число слагаемых нечетно (в силу $2\nmid n$), значит $p^{n-1}+...+1\equiv 1\pmod 2$ значит $p+1=2^m$, а $p^{n-1}+...+1=1$, что невозможно при $n>1$. Значит $n=1$, значит $p$ - простые Мерсенна, их показатель прост.

2) Пусть $q>2$. Тогда $\Phi_d(q)>1$, значит $(\forall d)\Phi_d(q)\equiv 0\pmod p$. А теперь танчик.: Для любых $a,b$ существуют $f_a, f_b$: $f_a(x)\Phi_a(x)+f_b(x)\Phi_b(x)=R(\Phi_a, \Phi_b)$, где $R$ - результант. Сам результант круговых многочленов известен (см. Прасолова Многочлены):

$$R(\Phi_a, \Phi_b)= \begin{cases} 0 \text{ при } a=b\\ p^{\varphi(b)} \text{ при } a=bp^k\\ 1 \text{ в других случаях} \end{cases}$$

(здесь в формуле $p$ - произвольное простое, никакого отношения к исходному уравнению не имеющее. Дальше оно не используется, а используется $p$ из уравнения).
Поскольку $(\forall d)\Phi_d(q)\equiv 0\pmod p$, то $(\forall a,b)R(\Phi_a,\Phi_b)\equiv 0\pmod p$. Теперь, если $n$ имеет хотя бы $2$ различных простых делителя, то их результант равен $1$, получаем противоречие $1\equiv 0\pmod p$. Значит $n=p^r$. Тогда уравнение принимает вид $\Phi_p(q)\Phi_{p^2}(q)...\Phi_{p^r}(q)=p^n$. Каждый множитель слева является степенью $p$. Кроме того, $\Phi_{p^k}(q)=\Phi_p(q^{p^{k-1}})$, а поскольку $\Phi_p(x)$ - возрастающая функция, то $\Phi_p(q)<\Phi_{p^2}(q)<...<\Phi_{p^r}(q)$, а значит все множители являются различными степенями простого $p$: $\Phi_{p^k}(q)=p^{a_k}, a_1<a_2<...<a_r$. Если $r>1$, то в произведении слева присутствует член $\Phi_{p^2}(q)=\Phi_p(q^p)$. Разность $\Phi_{p^2}(q)-\Phi_p(q)=q^{p-1}Q(p)=p^{a_2}-p^{a_1}\neq 0$ в силу $a_1<a_2$. Отсюда наконец получаем $p^{a_1}\mid q^{p-1}$, т.е. $q=p$, что явно невозможно. (Здесь как раз ошибка: $p^{a_2}-p^{a_1}$ - это не степень простого, значит не факт, что именно $q$ делится на $p$)
Т.обр, $m$ не может имет различные простые делители, а если $m=p^r$, то $r>1$ невозможно, значит $m$ - простое.

[nnosipov]

(Оффтоп)

Sonic86, я сейчас как раз обдумывал, как круговыми многочленами попользоваться; думал, может, легче выйдет Элементарное решение у меня есть, завтра напишу. Да и Вашу стену текста надо обдумать.

[Shadow]

Пусть $m=ab, \gcd(a,b)=1$

$\dfrac{q^{ab}-1}{q-1}=\dfrac{q^a-1}{q-1} \times \dfrac{q^{ab}-1}{q^a-1}=p^n$
Оба множителя должны быть степении простого p. Аналогично и $\dfrac{q^b-1}{q-1}$ тоже степень p. Разделив одно на другое получим (пусть $a>b$) $q^a-1 \vdots q^b-1$, причем частное тоже степень p.
$q^a-1=q^{a-b}(q^b-1)+q^{a-b}-1\cdots$
Т.е можно приложить алгоритм Евклида. Не делится.

Осталось рассмотреть случай когда m - степень простого числа (достаточно квадрат)...
Должно былть просто, а вот...

[nnosipov]

Shadow в сообщении #706728 писал(а):

Должно былть просто, а вот...

У меня вроде бы всё получилось. Надеюсь, не наврал.

[Sonic86]

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

Да и Вашу стену текста надо обдумать.

Там ошибка, можно не читать.

[Ktina]

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

(Оффтоп)

Элементарное решение у меня есть, завтра напишу.

(Оффтоп)

С нетерпением буду ждать завтрашнего дня. Я над этой задачей целый день думала, но безрезультатно.
Правда, мне тут уже кое-кто подсказал. Но писать не буду, так как не хочу выдавать чужое решение за своё. Если он захочет, сам напишет.

[nnosipov]

Цитата:

Если для простого числа $p$ и натуральных чисел $q>1$, $m$, $n$ имеет место равенство

$$ \frac{q^m-1}{q-1}=p^n, $$

то $m$ --- простое число.

Будем рассуждать от противного. Пусть $m=m_1p_1$, где $p_1$ --- произвольный простой делитель числа $m$, а $m_1>1$. Тогда

$$ p^n=(q^{m_1-1}+q^{m_1-2}+\ldots+q+1)(q^{m_1(p_1-1)}+q^{m_1(p_1-2)}+ \ldots+q^{m_1}+1)=AB. $$

Отсюда следует, что $A \equiv B \equiv 0 \pmod{p}$. Из сравнения $A \equiv 0 \pmod{p}$ выводим $q^{m_1} \equiv 1 \pmod{p}$, так что $B \equiv p_1 \pmod{p}$. Таким образом, $p_1 \equiv 0 \pmod{p}$, т.е. $p_1=p$. Итак, если $m$ --- составное число, то $m=p^k$, где $k \geqslant 2$. Имеем

$$ A=\frac{q^{p^{k-1}}-1}{q-1}, \quad B=q^{p^{k-1}(p-1)}+q^{p^{k-1}(p-2)}+\ldots+q^{p^{k-1}}+1. $$

Если $A=p^s$, то $B=p^t$, где $t>s$ (поскольку $B>A$ и $AB=p^n$). Имеем $q^{p^{k-1}}-1=(q-1)A \equiv 0 \pmod{p^s}$ и, как следствие, $B \equiv p \pmod{p^s}$. Поэтому $s=1$, т.е. $A=p$, что невозможно.