Не делится

[nnosipov]

(XXIII Кубок памяти Колмогорова) Докажите, что число $5^n-1$ не делится на $2^n+1$ ни при каком натуральном $n$.

P.S. Интересно сравнить с хорошо известной задачей про дробь

$$\frac{3^n-1}{2^n-1},$$

которая может быть целым числом только при $n=1$.

[gris]

на ходу: для первой половины чётных показателей очевидно. Подумал: а вдруг даже не сокращаются. Но для пятой степени есть общий делитель: одиннадцать
пока всё .

[nnosipov]

gris в сообщении #1435013 писал(а):

для чётных показателей очевидно

Да? В упор не вижу почему.

-- Пн янв 13, 2020 23:49:55 --

gris в сообщении #1435013 писал(а):

для первой половины чётных показателей очевидно

Это совсем другое дело Но что делать со второй половиной?

-- Пн янв 13, 2020 23:55:29 --

gris в сообщении #1435013 писал(а):

Но для пятой степени есть общий делитель: одиннадцать

Давайте сразу отбросим все нечетные показатели: для них очевидно не делится. Потому что ... Почему?

[gris]

из-за тройки.

[nnosipov]

Точно.

По поводу несократимости: дробь несократима примерно в два раза чаще, чем сократима. Это, естественно, численный эксперимент в разумных пределах (что-либо доказать здесь мне кажется делом очень сложным).

[nnosipov]

Попробую дать подсказку (возможно, это оживит тему --- на мой взгляд, задача вполне достойная). Так вот, здесь будут в деле числа Ферма $F_s=2^{2^s}+1$ и их простые делители, но рулит всем, как обычно в таких задачах, символ Якоби. А именно, нам потребуется равенство

$$\left(\frac{5}{F_s}\right)=-1$$

при $s \geqslant 2$.

Стартуем с уже доказанного выше: показатель $n$ можно считать кратным $4$.

[maxal]

Похоже на вариацию моей задачи: topic97212.html

[nnosipov]

Да, эти задачи (см. мою коллекцию, которая прилагается ниже) все более-менее похожи по методу решения. Но, как говорится, есть нюансы. В данной задаче известный сюжет закручен более изобретательно (во всяком случае, до меня не сразу дошло). Интересно было бы узнать, кто автор сего творения.

[Sonic86]

Вроде дошло:
$n=2^s m, 2\nmid m, s\geqslant 2$, $F_s := 2^{2^s}+1$, $p$ - любой делитель $F_s$
$2^n+1|5^m-1 \Rightarrow 5^{2^s m}\equiv 1\pmod {2^{2^s m}+1} \Rightarrow (5^m)^{2^s}\equiv 1\pmod {F_s} \Rightarrow $
$(5^m)^{2^s}\equiv 1\pmod p \Rightarrow 2^s\log(5^m)\equiv 0\pmod {p-1} \Rightarrow$
$2^s\log(5^m)\equiv 0\pmod {2^{s+1}} \Rightarrow 2\mid\log(5^m) \Rightarrow$
$5^m \equiv c^2 \pmod p \Rightarrow \left(\frac{5}{p}\right)=1 \Rightarrow \prod\limits_{p\mid F_s}\left(\frac{5}{p}\right)=\left(\frac{5}{F_s}\right)=1$.
Но символ Якоби $\left(\frac{5}{F_s}\right)=-1$ (просто вычисляем через закон взаимности для символа Якоби, знак четный, а $s\geqslant 2 \Rightarrow 2^{2^s}\equiv 1\pmod 5$), получаем противоречие.

Спасибо за подборку задач.
upd: $\mathrm{ord}$ везде заменен на $\log$

[nnosipov]

Sonic86 в сообщении #1435811 писал(а):

Спасибо за подборку задач.

Не за что. Рад, что обратили внимание.

Почитал Ваше решение. Вроде бы присутствуют (явно и неявно) все необходимые ингредиенты. Но я не понимаю следующее: 1) вот эту импликацию $(5^m)^{2^s}\equiv 1\pmod p \Rightarrow 2^s\mathrm{ord}(5^m)\equiv 0\pmod {p-1}$ и 2) вот эту $2\mid\mathrm{ord}(5^m) \Rightarrow 5^m \equiv c^2 \pmod p$ (здесь, как я понял, сказано следующее: если порядок элемента группы четен, то этот элемент есть квадрат другого элемента; но это утверждение в общем случае неверно --- например, $-1$, чей порядок равен двум, может быть и квадратичным невычетом). В общем, нужны подробности или чуть более аккуратные рассуждения. А так все довольно близко к тому, что получилось у меня.

[Sonic86]

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

1) вот эту импликацию $(5^m)^{2^s}\equiv 1\pmod p \Rightarrow 2^s\mathrm{ord}(5^m)\equiv 0\pmod {p-1}$

Это я просто логарифмировал и взаимно-простой множитель и выбросил взаимно-простой множитель показателя(? или как он называется?) элемента $5^m$.

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

2) вот эту $2\mid\mathrm{ord}(5^m) \Rightarrow 5^m \equiv c^2 \pmod p$ (здесь, как я понял, сказано следующее: если порядок элемента группы четен, то этот элемент есть квадрат другого элемента; но это утверждение в общем случае неверно --- например, $-1$, чей порядок равен двум, может быть и квадратичным невычетом).

Я спутал порядок и $\gcd(\text{порядок группы}, \log (5^m))$, оно же $=\frac{\text{порядок группы}}{\text{порядок элемента}}$. Как это называется? Я забыл
Заменил $\mathrm{ord}$ на $\log$. Теперь верно?

По-другому скажу на всякий случай:
Т.е. если $5^m$ - не квадрат, то $(5^m)^{2^s}$ не может быть $\equiv 1\pmod p$, потому что порядок группы $\mathbb{Z}_p^{\times}$ делится как минимум на $2^{s+1}$. А эта длинная цепочка - попытка аккуратной формализации, возможно излишняя.

[nnosipov]

Sonic86 в сообщении #1435850 писал(а):

оно же $=\frac{\text{порядок группы}}{\text{порядок элемента}}$. Как это называется?

Индекс подгруппы, порожденной элементом, в данной группе.

Sonic86 в сообщении #1435850 писал(а):

Теперь верно?

Пока не понял. Что у Вас обозначает $\log$? Это дискретный логарифм во всей группе $\mathbb{Z}_p^*$ (относительно какого-то фиксированного генератора)?

Вот эта фраза мне кажется более понятной:

Sonic86 в сообщении #1435850 писал(а):

Т.е. если $5^m$ - не квадрат, то $(5^m)^{2^s}$ не может быть $\equiv 1\pmod p$, потому что порядок группы $\mathbb{Z}_p^{\times}$ делится как минимум на $2^{s+1}$.

Upd. Да, здесь все OK. Хорошее рассуждение с логарифмами (если $\log{(5^m)}$ нечетен, то сразу противоречие, ибо как минимум одной двойки не хватит).

Для сравнения приведу свою версию объяснения. Пусть $n=2^st$, где $s \geqslant 2$, а $t$ нечётно. Если $5^n \equiv 1 \pmod{2^n+1}$, то

$$ 5^n \equiv 1 \pmod{F_s}, \eqno(*) $$

где $F_s=2^{2^s}+1$ --- число Ферма. Символ Якоби

$$ \left(\frac{5}{F_s}\right)=-1 $$

(вытекает из квадратичного закона взаимности и сравнения $F_s \equiv 2 \pmod{5}$ при $s \geqslant 2$), поэтому существует такой простой делитель $p$ числа $F_s$, для которого символ Лежандра

$$ \left(\frac{5}{p}\right)=-1. $$

Из сравнения $(*)$ следует сравнение

$$ 5^n \equiv 1 \pmod{p}. \eqno(**) $$

Кроме того, имеем $p-1=2^{s_1}t_1$, где $s_1 \geqslant s+2$ (известное свойство простых делителей числа Ферма $F_s$), а $t_1$ нечётно. Пусть $d=\text{ord}_p{(5)}=2^\alpha\beta$, где $\alpha \leqslant s_1$, а $\beta$ --- делитель $t_1$. По критерию Эйлера

$$ 5^{(p-1)/2} \equiv \left(\frac{5}{p}\right)=-1 \pmod{p}, $$

откуда $\alpha=s_1$. Значит, $\alpha \geqslant s+2$. Но тогда $n$ не делится на $d$, что противоречит $(**)$.

Замечание. Достаточно неравенства $s_1 \geqslant s+1$, которое доказать проще.