2014 dxdy logo

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

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


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


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

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

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

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

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



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


22/06/12
2129
/dev/zero
Ну давайте я сделаю финишный рывок.
$$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$.

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


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

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


22/06/12
2129
/dev/zero
nnosipov в сообщении #873030 писал(а):
что на самом деле $f(2) \neq g(2)$


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

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

 Профиль  
                  
 
 Re: Делимость и минимизация
Сообщение09.06.2014, 11:16 


26/08/11
2057
Мне кажется, что такое доказательство по индукции не подходит для решения задачи. Вы доказали
$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$? Ну, по крайней мере когда, делимое не меньше делителя.

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


20/12/10
8858
Shadow в сообщении #873566 писал(а):
На самом деле необходимо доказать:
$5^k \parallel m \Leftrightarrow 5^{k+1} \parallel 4^m+1$.
Это правильно, конечно. Всё это есть в LTE, которую я выше сформулировал, надеясь, что ТС обратит на неё внимание. Эта лемма является мощным инструментом в подобных задачах, поэтому лучше не мелочиться и доказать её всю целиком.
Shadow в сообщении #873566 писал(а):
Но можно например рассмотреть бинoм Ньютона
На мой взгляд, выйдет сложнее, чем обычным способом. Формула Лежандра, конечно, интересна сама по себе, но в данном случае смотрится несколько чужеродной.

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


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

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


20/12/10
8858
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. Не спеша сочините доказательство и выложите здесь, а мы его почитаем и покритикуем.

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


22/06/12
2129
/dev/zero
nnosipov в сообщении #873598 писал(а):
Нет, число $3^n+2$ также может делиться на пять (причём даже на любую степень пятёрки).

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

nnosipov в сообщении #873598 писал(а):
Не спеша сочините доказательство и выложите здесь, а мы его почитаем и покритикуем.



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

-- 09.06.2014, 15:38 --

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

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


20/12/10
8858
StaticZero в сообщении #873603 писал(а):
он хотел сделать только один сомножитель делящимся где-нибудь на 5, чтобы задача была не такой ужасной.
Нет, эта задача в таком виде (с $3^n+2$) в самый раз. Узнаём всю правду про множитель $2^n+1$, а множитель $3^n+2$ просто слишком мал. Детали этого рассуждения --- за Вами.

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


22/06/12
2129
/dev/zero
Да, я тоже пришел к мысли только что.

$(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$$ Все решение.

(Оффтоп)

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

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


20/12/10
8858
StaticZero в сообщении #873608 писал(а):
Значит, делится только $2^n + 1$.
Вы правы. Ведь $n$ и там, и там одно и то же, на что я не обратил внимание. Но эту красоту легко испортить, заменив $3^n+2$ на, скажем, $3^n+6$. (Это так, конечно, к слову. Каким могло бы быть в принципе развитие событий.)

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


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

 Профиль  
                  
 
 Re: Делимость и минимизация
Сообщение09.06.2014, 16:14 


26/08/11
2057
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$
Зачем сводить элементарную задачу к более сложной?

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


22/06/12
2129
/dev/zero
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}$$

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


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

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

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



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

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


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

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