2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

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



Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Делимость и минимизация
Сообщение06.06.2014, 16:08 
Заслуженный участник
Аватара пользователя


22/06/12
2129
/dev/zero
Есть задача, которая ставит в тупик, и другая, где я метод решения подобных не понял, видимо.
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}$

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

 Профиль  
                  
 
 Re: Делимость и минимизация
Сообщение06.06.2014, 16:36 
Заслуженный участник


20/12/10
8858
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)$.

 Профиль  
                  
 
 Re: Делимость и минимизация
Сообщение06.06.2014, 17:14 
Аватара пользователя


26/05/12
1534
приходит весна?
nnosipov в сообщении #872504 писал(а):
Вы не привели доказательство того, что равенство $a=b=c$ гарантирует минимум выражению $(a+b)(b+c)(c+a)$.
В связи с этим возникает интересный вопрос: привести пример симметричных относительно перестановок величин $a$, $b$, $c$ минимизируемой функции и уравнения связи, которые, между тем, дают экстремум, не удовлетворяющий равенству $a=b=c$.

 Профиль  
                  
 
 Re: Делимость и минимизация
Сообщение06.06.2014, 19:43 
Заслуженный участник
Аватара пользователя


22/06/12
2129
/dev/zero
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$.
Если этого недостаточно, то, значит, я не понял ничего в методе приведения к равенству.

 Профиль  
                  
 
 Re: Делимость и минимизация
Сообщение06.06.2014, 19:55 
Заслуженный участник


20/12/10
8858
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$. А чему равносильно это последнее неравенство?

 Профиль  
                  
 
 Re: Делимость и минимизация
Сообщение06.06.2014, 20:18 
Заслуженный участник
Аватара пользователя


22/06/12
2129
/dev/zero
Тогда $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 --

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

 Профиль  
                  
 
 Re: Делимость и минимизация
Сообщение06.06.2014, 20:31 
Заслуженный участник


20/12/10
8858
StaticZero в сообщении #872587 писал(а):
Не знаю, правда, то ли вы хотели от меня услышать или нет.
По-моему, у Вас было написано (см. первый пост) $A=8 \cdot 729(abc)^3$, $B=8(abc)$. Решив неравенство $A \geqslant B$, мы получим $abc \geqslant 1/27$.
StaticZero в сообщении #872587 писал(а):
Этого уже хватает?
В общем, да.

 Профиль  
                  
 
 Re: Делимость и минимизация
Сообщение06.06.2014, 20:34 
Заслуженный участник
Аватара пользователя


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

-- 06.06.2014, 22:22 --

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

 Профиль  
                  
 
 Re: Делимость и минимизация
Сообщение07.06.2014, 12:35 
Заслуженный участник


20/12/10
8858
StaticZero в сообщении #872568 писал(а):
$(2^n + 1) \mod 5^m = 0 \Leftrightarrow n = 2 \cdot 5^{m-1}(2i + 1)$
Докажите это утверждение индукцией по $m$.

 Профиль  
                  
 
 Re: Делимость и минимизация
Сообщение07.06.2014, 12:54 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Делимость и минимизация
Сообщение07.06.2014, 13:39 
Заслуженный участник


20/12/10
8858
Ну, давайте напишем равенство $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$.

 Профиль  
                  
 
 Re: Делимость и минимизация
Сообщение07.06.2014, 16:15 
Заслуженный участник
Аватара пользователя


22/06/12
2129
/dev/zero
Разродился таким доказательством.

Докажем, что
$(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\}$$

 Профиль  
                  
 
 Re: Делимость и минимизация
Сообщение07.06.2014, 18:29 
Заслуженный участник


20/12/10
8858
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$.)

 Профиль  
                  
 
 Re: Делимость и минимизация
Сообщение07.06.2014, 19:55 
Заслуженный участник
Аватара пользователя


22/06/12
2129
/dev/zero
Я только не понимаю одного, что $n$ стоит и слева, и справа. Могу ли я явно его получить?

 Профиль  
                  
 
 Re: Делимость и минимизация
Сообщение07.06.2014, 20:11 
Заслуженный участник


20/12/10
8858
StaticZero в сообщении #872874 писал(а):
Могу ли я явно его получить?
Можно получить оценку для $n$ сверху. А затем непосредственно перебрать те $n$, которые удовлетворяют этой оценке.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 32 ]  На страницу 1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group