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

[StaticZero]

Есть задача, которая ставит в тупик, и другая, где я метод решения подобных не понял, видимо.
1. Найти все $n \in \mathbb N$ такие, что $(2^n + 1)(3^n + 1)$ делится на $5^n$.
Попытка решения в следующем. Я выясняю, что возможные $n$ имеют вид $n = 4k+2, k \in \mathbb N \cup \{0\}$ и только такие, ибо только тогда есть делимость левой части хотя бы на $5$.
Переход к нечетным основаниям:
$(2^{4k+2} + 1)(3^{4k+2} + 1) = (4^{2k+1} +1)(9^{2k+1}+1)
затем
$(4^{2k+1} +1)(9^{2k+1}+1) = (4+1)(9+1)(4^{2k} - 4^{2k-1} + ... + 1)(9^{2k} - 9^{2k-1} + ... + 1) = 50(4^{2k} - 4^{2k-1} + ... + 1)(9^{2k} - 9^{2k-1} + ... + 1) $
Легко видеть, что, по крайней мере, на $25$ число делится бесспорно. Дальше что делать, пока не могу понять. Есть подозрение, что скобки могут разделиться на 5 не более одного раза каждая.

2. Даны $a, b, c > 0$ такие, что $a+b+c = 27abc$. Найдите минимальное значение $(a+b)(b+c)(a+c)$.
Здесь я не могу понять, чего от меня хотят.
Из неравенства Коши получим
$(a+b)(a+c)(b+c) \geqslant 8\sqrt{ab\cdot bc \cdot ac} = 8abc$
В то же время,
$\frac{2(a+b+c)}{3} \geqslant \sqrt[3]{(a+b)(a+c)(b+c)}$
$\frac{8(a+b+c)^3}{27} \geqslant (a+b)(a+c)(b+c)$
$8\cdot 729(abc)^3 \geqslant (a+b)(a+c)(b+c)$

Равенства достигаются при $a=b=c=t$, найдём $t$:
$3t = 27t^3$
$t_1 = 0, t_2 = \frac{1}{3}, t_3 = -\frac{1}{3}$
Так как $t>0$, то $t = \frac{1}{3}$.
Тогда
$8\cdot 729(abc)^3 = (a+b)(a+c)(b+c) = 8abc$
и $\min = \frac{8}{27}$

Мне сказали, что "равенство не гарантирует минимум". О чем речь?

[nnosipov]

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

1. Найти все $n \in \mathbb N$ такие, что $(2^n + 1)(3^n + 1)$ делится на $5^n$.

Попробуйте сначала ответить на такой частный вопрос: на какую максимальную степень пятёрки делится число $2^n+1$ в зависимости от $n$?

Вы правильно заметили, что достаточно рассматривать только те $n$, которые имеют вид $n=2m$, где $m$ нечётно. Предположите, что $m=5^st$, где $t$ не делится на $5$, и выясните, на какую степень пятёрки будет тогда делиться $2^n+1$ (в ответе будет участвовать $s$).

-- Пт июн 06, 2014 20:38:57 --

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

Есть подозрение, что скобки могут разделиться на 5 не более одного раза каждая.

А Вы поэкспериментируйте с конкретными $n$ при помощи компьютера и попробуйте заметить закономерность.

-- Пт июн 06, 2014 20:51:37 --

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

Мне сказали, что "равенство не гарантирует минимум". О чем речь?

Вы не привели доказательство того, что равенство $a=b=c$ гарантирует минимум выражению $(a+b)(b+c)(c+a)$.

[B@R5uk]

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

Вы не привели доказательство того, что равенство $a=b=c$ гарантирует минимум выражению $(a+b)(b+c)(c+a)$.

В связи с этим возникает интересный вопрос: привести пример симметричных относительно перестановок величин $a$, $b$, $c$ минимизируемой функции и уравнения связи, которые, между тем, дают экстремум, не удовлетворяющий равенству $a=b=c$.

[StaticZero]

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

Попробуйте сначала ответить на такой частный вопрос: на какую максимальную степень пятёрки делится число $2^n+1$ в зависимости от $n$?

Взял в руки комп. алгебру, ввожу
$(2^n + 1) \mod 5^m, m \in \mathbb N$
Получил следующее:
$(2^n + 1) \mod 5^m = 0 \Leftrightarrow n = 2 \cdot 5^{m-1}(2i + 1), i \in \mathbb N_0, m \in \mathbb N$
$(3^n + 1) \mod 5^m = 0 \Leftrightarrow n = 2 \cdot 5^{m-1}(2i + 1), i \in \mathbb N_0, m \in \mathbb N$
То есть критерии делимости на $5^m$ совпадают.

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

Вы не привели доказательство того, что равенство $a=b=c$ гарантирует минимум выражению $(a+b)(b+c)(c+a)$

Я тогда вообще не понимаю, как проверить минимум. Я посмотрел, что, если
$f(a, b, c) = (a+b)(b+c)(c+a)$
то
$A \geqslant f(a, b, c) \geqslant B$
и $A = B$ тогда, когда $a = b = c$.
Если этого недостаточно, то, значит, я не понял ничего в методе приведения к равенству.

[nnosipov]

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

Получил следующее:
$(2^n + 1) \mod 5^m = 0 \Leftrightarrow n = 2 \cdot 5^{m-1}(2i + 1), i \in \mathbb N_0, m \in \mathbb N$
$(3^n + 1) \mod 5^m = 0 \Leftrightarrow n = 2 \cdot 5^{m-1}(2i + 1), i \in \mathbb N_0, m \in \mathbb N$

Правильно. Нужно только добавить, что в обоих случаях $2i+1$ не должно делиться на $5$. Теперь Вам осталось: а) доказать эти утверждения; б) понять, как с их помощью решить саму задачу.

-- Сб июн 07, 2014 00:06:48 --

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

Если этого недостаточно, то, значит, я не понял ничего в методе приведения к равенству.

Вы не в ту сторону пошли. Из полученного неравенства $A \geqslant f(a,b,c) \geqslant B$ следует неравенство $A \geqslant B$. А чему равносильно это последнее неравенство?

[StaticZero]

Тогда $i \in \mathbb N_0 \diagdown \{2, 7, 12, ... | 2 + 5t, t \in \mathbb N\}$.
Ладно, пока отправляюсь думать над 1 задачей.

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

А чему равносильно это последнее неравенство?

Имеем
$\frac{8}{27}(a+b+c)^3 \geqslant 8abc$
$\frac{(a+b+c)^3}{27} \geqslant abc$
$(a+b+c)^3 \geqslant (a+b+c)$
$(a+b+c)((a+b+c)^2 - 1) \geqslant 0$
$(a+b+c) = x$
$x^2 - 1 \geqslant 0$
$x \in [1; \infty)$
$a+b+c \geqslant 1$
Не знаю, правда, то ли вы хотели от меня услышать или нет. Может быть, я вас неправильно понял.

Давайте раскручу идею дальше:
$a = b = c = t$
Нашли $t = \frac{1}{3}$
$\Rightarrow (a+b+c) = 1 = \{\min(a+b+c) \ |\ a = b = c, \ a+b+c = 27abc\}$

-- 06.06.2014, 21:24 --

Этого уже хватает?

[nnosipov]

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

Не знаю, правда, то ли вы хотели от меня услышать или нет.

По-моему, у Вас было написано (см. первый пост) $A=8 \cdot 729(abc)^3$, $B=8(abc)$. Решив неравенство $A \geqslant B$, мы получим $abc \geqslant 1/27$.

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

Этого уже хватает?

В общем, да.

[StaticZero]

Значит, еще раз: мы ищем $a, b, c$ такие, что $a = b = c, abc = 27$. Мы найдем минимальное значение произведения, подгоним циферки под него и подставим в функцию. Так же, вроде? Да, и спасибо за помощь. Теперь есть пути решения.

-- 06.06.2014, 22:22 --

Я ничего не могу сделать в первой. Я даже не понимаю, почему эта формула верна.

[nnosipov]

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

$(2^n + 1) \mod 5^m = 0 \Leftrightarrow n = 2 \cdot 5^{m-1}(2i + 1)$

Докажите это утверждение индукцией по $m$.

[StaticZero]

Да в том-то и дело, что я не вижу связи между делимостью числа на $5^m$ и $5^{m+1}$. Надо бы знать частное от деления на $5^{m}$, чтобы сказать о делимости на $5^{m+1}$.

[nnosipov]

Ну, давайте напишем равенство $2^{2 \cdot 5^ml}+1=4^{5^ml}+1=(4^{5^{m-1}l}+1)(\ldots)=(2^{2 \cdot 5^{m-1}l}+1)(\ldots)$. Докажите, что вторая скобка (выпишите её подробно) делится на $5$.

[StaticZero]

Разродился таким доказательством.

Докажем, что
$(2^n + 1) \equiv 0 \pmod {5^{m}}$, если $n = 2\sigma\cdot 5^{m-1}$, где $m, n \in \mathbb N$, $\sigma$ нечетно.

Используем индукцию по $m$:

Пусть $m=1$.
Известно, что на $5$ делятся все числа вида

$$(2^{4k+2} + 1), k\in N_0$$

В самом деле, так как $2^{4k+2} = 4^{2k+1}$, а $4$ в нечётной степени имеет кол-во единиц, равное $4$, то

$$2^{4k+2} = a_s\cdot 10^s+...+a_1\cdot 10 + 4 = 10\cdot(a_s\cdot 10^{s-1} + ... + a_1) + 4 = 5b + 4, b\in \mathbb N$$

Отсюда следует

$$2^{4k+2} + 1 = 5b + 4 + 1 = 5(b+1) \equiv 0 \pmod 5$$

что и требовалось. Легко видеть, что $4k + 2 = 2\cdot(2k + 1)\cdot 5^0$. Итак, база подтверждена.

Пусть для всякого $q = m$ выполнено

$$(2^{2\sigma\cdot 5^{m-1}} + 1) \equiv 0 \pmod {5^{m}}$$

Перейдем к нечетным степеням и обозначим

$$4^{\sigma\cdot 5^{m-1}} = x$$

По предположению,

$$x + 1 \equiv 0 \pmod {5^m}$$

Тогда для $q = m+1$ получаем

$$x^5 + 1 \equiv 0 \pmod{5^{m+1}}$$

$$(x+1)(x^4 - x^3 + x^2 - x + 1) \equiv 0 \pmod{5^{m+1}}$$

Учтем, что $x$ - это $4$ в нечётной степени. Следовательно, нечётные степени $x$ заканчиваются на $4$, а чётные - на $6$. Тогда распишем степени $x$:
$x^4 = 5b_1 + 1$
$x^3 = 5b_2 + 4$
$x^2 = 5b_3 + 1$
$x = 5b_4 + 4$
$1 = 1$

Отсюда

$$(x^4 - x^3 + x^2 - x + 1) = 5(b_1 - b_2 + b_3 - b_4) + 1 - 4 + 1 - 4 + 1 = 5(b_1 - b_2 + b_3 - b_4 - 1)$$

Следовательно,

$$(x^5 + 1) = (x+1)(x^4 - x^3 + x^2 - x + 1) \equiv 0 \pmod{5^{m+1}}$$

что и требовалось доказать.

Для $3^n + 1$ аналогично.
Теперь поймем, что $(2^n + 1)$ и $(3^n + 1)$ максимально делятся на одни и те же степени пятерки, допустим, $s$. Тогда их произведение максимально делится на $5^{2s}$. Отсюда неравенство $2s \geqslant n$.
Нам нужно, чтобы всё произведение делилось на $5^n$.
Но тут тогда вопрос: а при каких $n$ величина $(2^n + 1)$ делится на $5^{\frac{n}{2}}$? У меня получается порочный круг.

-- 07.06.2014, 17:31 --

Или мне просто достаточно сказать, что $n$ такие, что

$$n = 2\cdot \sigma \cdot 5^{\frac{n}{2}}, \sigma \in \{1, 3, 7, 9, ... | 2q + 1, q \ne 4p, p \in \mathbb N\}$$

[nnosipov]

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

Или мне просто достаточно сказать, что $n$ такие, что

$$n = 2\cdot \sigma \cdot 5^{\frac{n}{2}}, \sigma \in \{1, 3, 7, 9, ... | 2q + 1, q \ne 4p, p \in \mathbb N\}$$

Да, только поаккуратнее нужно выразиться. Лучше отталкиваться от неравенства $2s \geqslant n$ и равенства $n=2 \cdot 5^{s-1}\sigma$. При больших $n$ эти соотношения будут противоречить друг другу.

В целом, задачу Вы решили. Рассуждения, которые здесь использовались, можно обобщить следующим образом (Lifting The Exponent Lemma).

Пусть $a$, $b$ --- такие неравные целые числа, что $a \equiv b \not\equiv 0 \pmod{p}$, где $p$ --- нечётное простое число. Тогда для любого $n=1,\,2,\,\dots$ справедливо равенство

$$ \nu_p(a^n-b^n)=\nu_p(a-b)+\nu_p(n). $$

(Здесь $\nu_p(m)$ обозначает показатель, с которым $p$ входит в каноническое разложение числа $m$.)

[StaticZero]

Я только не понимаю одного, что $n$ стоит и слева, и справа. Могу ли я явно его получить?

[nnosipov]

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

Могу ли я явно его получить?

Можно получить оценку для $n$ сверху. А затем непосредственно перебрать те $n$, которые удовлетворяют этой оценке.