Деление на 10000

[DjD USB]

Докажите что существуют такие натуральные m и n такие что $13^m - 13^n$ делится на 10000.

[thought]

Например, при всех m=n.

[мат-ламер]

Может поможет то, что $13=10+3$ и степени биномом раскрыть.

[Sonic86]

$13^m\equiv 13^n\pmod{10^5}\Leftrightarrow 13^{n-m}\equiv 1\pmod{10^5}$ - фактически ищем $n-m$ по какому-то модулю.

[DjD USB]

DjD USB в сообщении #595177 писал(а):

Докажите что существуют такие натуральные m и n такие что $13^m - 13^n$ делится на 10000.

Я извеняюсь. m и n различны

-- Сб июл 14, 2012 13:48:38 --

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

$13^m\equiv 13^n\pmod{10^5}\Leftrightarrow 13^{n-m}\equiv 1\pmod{10^5}$ - фактически ищем $n-m$ по какому-то модулю.

Не $10^5$ а $10^4$

[thought]

Продолжая идею Sonic86, остается применить теорему Эйлера: если (a,m)=1, то

$$ a^{\phi(m)} \equiv 1 (\mod m) $$

$\phi(1000) = 4000$, поэтому

$$ 13^{4000} \equiv 1 (\mod 10000) $$

n=m+4000. Поэтому все пары вида (m+4000, m) подходят.

[apriv]

DjD USB в сообщении #595177 писал(а):

Докажите что существуют такие натуральные m и n такие что $13^m - 13^n$ делится на 10000.

Это называется «принцип Дирихле»: вряд ли $13^m$ дает разные остатки при делении на 10000 при всех натуральных $m$.

[Профессор Снэйп]

apriv в сообщении #595193 писал(а):

Это называется «принцип Дирихле»: вряд ли $13^m$ дает разные остатки при делении на 10000 при всех натуральных $m$.

Браво! Жаль, что сам не додумался

[ewert]

apriv в сообщении #595193 писал(а):

Это называется «принцип Дирихле»: вряд ли $13^m$ дает разные остатки при делении на 10000 при всех натуральных $m$.

И как из принципа Дирихле следует, что оно даёт все мыслимые остатки (что, кстати, неверно) -- или что среди множества остатков непременно есть единица?...

[Профессор Снэйп]

ewert в сообщении #595221 писал(а):

И как из принципа Дирихле следует...

Э-э-э... А принцип Дирихле как формулируется?

-- Сб июл 14, 2012 18:57:07 --

ewert в сообщении #595221 писал(а):

или что среди множества остатков непременно есть единица?

При чём здесь единица?

[apriv]

ewert в сообщении #595221 писал(а):

apriv в сообщении #595193 писал(а):

Это называется «принцип Дирихле»: вряд ли $13^m$ дает разные остатки при делении на 10000 при всех натуральных $m$.

И как из принципа Дирихле следует, что оно даёт все мыслимые остатки (что, кстати, неверно) -- или что среди множества остатков непременно есть единица?...

Я не говорил, что оно дает все мыслимые остатки. Я не говорил, что среди множества остатков непременно есть единица. Для доказательства нужного утверждения хватает только того, что они не могут быть попарно различны.

[Профессор Снэйп]

У нас есть клетки - остатки от деления на $10000$. Их, как нетрудно догадаться, ровно $10000$. И есть счётное число зайцев - натуральных чисел. Зайца $n$ мы помещаем в клетку, равную остатку от деления $13^n$ на $10000$. Остаётся лишь рассмотреть двух различных зайцев $m$ и $n$, сидящих в одной и той же клетке

[ewert]

apriv в сообщении #595225 писал(а):

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

Как тут уже было многократно замечено (да и просто очевидно), доказываемое утверждение в точности равносильно следующему: при некоторых $m$ число $13^m-1$ делится на $10000$. Или, что в точности то же самое: что среди остатков от деления чисел $13^m$ на $10000$ непременно присутствует единица. Не более и не менее. И где же тут Дирихле и вообще попарная различность?... Речь идёт конкретно о единице и только о ней.

[apriv]

ewert в сообщении #595230 писал(а):

Как тут уже было многократно замечено (да и просто очевидно), доказываемое утверждение в точности равносильно следующему: при некоторых $m$ число $13^m-1$ делится на $10000$. Или, что в точности то же самое: что среди остатков от деления чисел $13^m$ на $10000$ непременно присутствует единица. Не более и не менее. И где же тут Дирихле и вообще попарная различность?... Речь идёт конкретно о единице и только о ней.

Я, с Вашего позволения, буду доказывать не то, что Вы предлагаете, а то, что изначально сформулировано. А уж из того, что какие-то два остатка совпадут, конечно, следует и то, что среди них встретится единица.

[ewert]

apriv в сообщении #595235 писал(а):

А уж из того, что какие-то два остатка совпадут, конечно, следует и то, что среди них встретится единица.

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