Делимость и минимизация

[StaticZero]

Ну давайте я сделаю финишный рывок.

$$2s \geqslant 5^{s-1}\cdot 2\sigma$$

$$s \geqslant 5^{s-1}\sigma \geqslant 5^{s-1}$$

$$ 5s \geqslant 5^s$$

Если $s$ больше 2, то $5s < 5^s$.
(В самом деле, рассмотрим $f(s) = 5s$ и $g(s) = 5^s$, $s \in \mathbb R$. $\dfrac{df(s)}{ds} = 5, \dfrac{dg(s)}{ds} = 5^s \ln 5$. Найдем точку, где $f(s) = g(s)$, это, очевидно, $2$. Очевидно так же, что $f'(s) \leqslant g'(s)$ хотя бы для $s > 2$. Но по известным теоремам, в таком случае, $f(s) < g(s), s > 2).

Таким образом, $s \in \{1, 2\}$.
Вспоминаем, что $s$ - степень пятерки, на которую максимально делятся $(2^n + 1)$ и $(3^n + 1)$.
Ну тогда произведение делится на $5^{2s}$.
У нас фиксировано $s$, переберем их.
Для $s = 1$ разрешим уравнение

$n = 2\sigma = 2s$

$\sigma = 1$, подходит.

Для $s=2$ разрешаем

$n = 10\sigma = 2s$

$s = 5\sigma$
Таких $\sigma$ из целых не существует.
Ответ: $n = 2$.

[nnosipov]

StaticZero в сообщении #872963 писал(а):

Если $s$ больше 2, то $5s < 5^s$.
(В самом деле, рассмотрим $f(s) = 5s$ и $g(s) = 5^s$, $s \in \mathbb R$. $\dfrac{df(s)}{ds} = 5, \dfrac{dg(s)}{ds} = 5^s \ln 5$. Найдем точку, где $f(s) = g(s)$, это, очевидно, $2$. Очевидно так же, что $f'(s) \leqslant g'(s)$ хотя бы для $s > 2$. Но по известным теоремам, в таком случае, $f(s) < g(s), s > 2).

Таким образом, $s \in \{1, 2\}$.

Нууу, это уже несколько перебор, тем более, что на самом деле $f(2) \neq g(2)$. То, что неравенство $s \geqslant 5^{s-1}$ выполняется только при $s=1$, --- довольно очевидный мелкий факт (для формального доказательства производные применять, конечно, можно, но здесь это явное излишество; индукция по $s$ была бы более адекватным средством).

Ответ $n=2$ правильный, и мы действительно имеем финиш.

[StaticZero]

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

что на самом деле $f(2) \neq g(2)$

да, не заметил косяка

Спасибо огромное вам за помощь. Премного благодарен.

[Shadow]

Мне кажется, что такое доказательство по индукции не подходит для решения задачи. Вы доказали
$5^k \mid m \Rightarrow 5^{k+1} \mid 4^m+1$

Во первых, Вам нужно доказательство в обратную сторону. Во вторых, просто "делится" не достаточно, надо "$m$ делится на $5^k$ но не делится на $5^{k+1}$) для главного вывода: $4^m+1 \text{ и } 9^m+1$ делятся на одну и ту же степен 5. На самом деле необходимо доказать:
$5^k \parallel m \Leftrightarrow 5^{k+1} \parallel 4^m+1$. В обеих сторонах.
Не знаю пройдет ли здесь индукция. Но можно например рассмотреть бинoм Ньютона
$4^m+1=(5-1)^m+1$

$C_m^q\cdot 5^q=\dfrac{m(m-1)\cdots(m-q+1)}{q!}\cdot 5^q$

$\nu_5(q!)=\left\lfloor\dfrac q 5\right\rfloor+\left\lfloor\dfrac{q}{5^2}\right\rfloor+\cdots<\dfrac q 4$.

И при $q \ge 2,\quad q-\nu_5(q!) \ge 2$
А при $q=1\cdots$

StaticZero в сообщении #872801 писал(а):

Но тут тогда вопрос: а при каких $n$ величина $(2^n + 1)$ делится на $5^{\frac{n}{2}}$? У меня получается порочный круг.

Тоесть, когда $5^m \mid 4^m+1$? Ну, по крайней мере когда, делимое не меньше делителя.

[nnosipov]

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

На самом деле необходимо доказать:
$5^k \parallel m \Leftrightarrow 5^{k+1} \parallel 4^m+1$.

Это правильно, конечно. Всё это есть в LTE, которую я выше сформулировал, надеясь, что ТС обратит на неё внимание. Эта лемма является мощным инструментом в подобных задачах, поэтому лучше не мелочиться и доказать её всю целиком.

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

Но можно например рассмотреть бинoм Ньютона

На мой взгляд, выйдет сложнее, чем обычным способом. Формула Лежандра, конечно, интересна сама по себе, но в данном случае смотрится несколько чужеродной.

[StaticZero]

В итоге я узнал, что в задании опечатка. Там $(2^n + 1)(3^n + 2) \equiv 0 \pmod 5^n$
Ну а тут все тривиально решается, так как на $5$ делится только $(2^n + 1)$, для этого необходимо, чтобы $(2^n + 1) \geqslant 5^n$, а значит, подходит только $n=2$.

А LTE, наверное, хорошо бы доказать.

Здесь же, в доказательстве, мы просто предполагаем, что $(2^n+1)$ делится на какую-то максимальную степень $s$, мы знаем, какой нужен $n$. Этого разве недостаточно?

[nnosipov]

StaticZero в сообщении #873595 писал(а):

Там $(2^n + 1)(3^n + 2) \equiv 0 \pmod 5$

То есть, нужно найти все $n$, при которых $(2^n+1)(3^n+2)$ делится на $5^n$. Это мне кажется даже более интересной задачей, чем та, что мы обсуждали.

StaticZero в сообщении #873595 писал(а):

так как на $5$ делится только $(2^n + 1)$

Нет, число $3^n+2$ также может делиться на пять (причём даже на любую степень пятёрки).

-- Пн июн 09, 2014 18:15:41 --

StaticZero в сообщении #873595 писал(а):

Этого разве недостаточно?

Нужно аккуратно рассуждать. Всё-таки рекомендую потратить время и доказать LTE. Не спеша сочините доказательство и выложите здесь, а мы его почитаем и покритикуем.

[StaticZero]

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

Нет, число $3^n+2$ также может делиться на пять (причём даже на любую степень пятёрки).

Дважды идиот Советского Союза. Это очевидно, что делится. Только я написал почему-то, что не делится.

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

Не спеша сочините доказательство и выложите здесь, а мы его почитаем и покритикуем.

Я тогда растяну на недели-две сей процесс.

-- 09.06.2014, 15:38 --

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

[nnosipov]

StaticZero в сообщении #873603 писал(а):

он хотел сделать только один сомножитель делящимся где-нибудь на 5, чтобы задача была не такой ужасной.

Нет, эта задача в таком виде (с $3^n+2$) в самый раз. Узнаём всю правду про множитель $2^n+1$, а множитель $3^n+2$ просто слишком мал. Детали этого рассуждения --- за Вами.

[StaticZero]

Да, я тоже пришел к мысли только что.

$(2^n + 1) \equiv 0 \pmod 5$, если $n = 4k+2$. Но тогда $(3^n + 2) = (3^{4k+2} + 2) = 9^{2k+1} + 2 \not\equiv 0 \pmod 5 \ \ \forall k \in \mathbb N$. Значит, делится только $2^n + 1$.
Исследуем сравнение

$$2^n + 1 \equiv 0 \pmod {5^n}$$

$$2^n + 1 \geqslant 5^n$$

$$ n = 2$$

Все решение.

(Оффтоп)

Это больше похоже на типичную школьную задачку для "интеллектуалов" вроде меня.

[nnosipov]

StaticZero в сообщении #873608 писал(а):

Значит, делится только $2^n + 1$.

Вы правы. Ведь $n$ и там, и там одно и то же, на что я не обратил внимание. Но эту красоту легко испортить, заменив $3^n+2$ на, скажем, $3^n+6$. (Это так, конечно, к слову. Каким могло бы быть в принципе развитие событий.)

[StaticZero]

Так задача сводится к предыдущей, про $3^n + 1$. Только мы бы искали числа такие, что $3^n$ заканчивается на $9$, это те же самые числа, что мы искали и тогда. ($3^n + 1$).

[Shadow]

StaticZero в сообщении #873608 писал(а):

$(2^n + 1) \equiv 0 \pmod 5$, если $n = 4k+2$.

$(3^n + 2) \equiv 0 \pmod 5$, если $n = 4k+1$.

StaticZero в сообщении #873608 писал(а):

Значит, делится только $2^n + 1$.

Нет, он как раз не делится. Значит что делится только один из двух множителей. (за исключением случая $n=0$)

StaticZero в сообщении #873620 писал(а):

Так задача сводится к предыдущей, про $3^n + 1$

Зачем сводить элементарную задачу к более сложной?

[StaticZero]

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

StaticZero в сообщении #873608
писал(а):
$(2^n + 1) \equiv 0 \pmod 5$, если $n = 4k+2$. $(3^n + 2) \equiv 0 \pmod 5$, если $n = 4k+1$.

Совмещаем, получаем безусловно верное тождество $2 = 1$.

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

Нет, он как раз не делится. Значит что делится только один из двух множителей. (за исключением случая $n=0$)

Это и имелось ввиду. Если мы выберем, чтобы делилось $(2^n + 1)$, то $3^n + 2$ делиться не будет даже на 5, и наоборот.

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

Зачем сводить элементарную задачу к более сложной?

Это о похожести задач

$$(2^n + 1)(3^n + 1) \equiv 0 \pmod{5^n}$$

и

$$(2^n + 1)(3^n + 6) \equiv 0 \pmod{5^n}$$

[nnosipov]

StaticZero в сообщении #874025 писал(а):

Это о похожести задач

$$(2^n + 1)(3^n + 1) \equiv 0 \pmod{5^n}$$

и

$$(2^n + 1)(3^n + 6) \equiv 0 \pmod{5^n}$$

От этих двух задача о

$$(2^n + 1)(3^n + 2) \equiv 0 \pmod{5^n}$$

всё же отличается тем, что здесь можно обойтись без LTE.