Деление на 10000

[apriv]

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

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

Это Вам нужна единица. А мне нужно два любых одинаковых: как только два остатка $13^m$ и $13^n$ совпали, их разность тут же делится на 10000.

-- 14.07.2012, 17:49 --

Ну да, а их частное тогда, конечно же, сравнимо с 1 по модулю 10000, но меня это уже не слишком волнует. Кстати, это рассуждение с 1 к тому же использует тот нетривиальный факт, что 13 и 10000 взаимно просты; а рассуждение с принципом Дирихле работает всегда.

[thought]

Странный спор тут у вас. Принципом Дирихле можно доказать существование такой пары, причем тривиально. Пусть $\{r_n\}_{n \geq 1}$ - последовательность остатков при делении $13^n$ на 10000. Так как элементы данной последовательности принадлежат множеству $\{0,...,9999\}$, то обязательно найдутся два таких элемента с разными индексами, имеющие одинаковое значение (хотя понятно, что элементов с некоторым значением будет беск. много). Вот и все доказательство. А если нужны конкретные значения, то теорема Эйлера вверху.

[Shadow]

thought в сообщении #595243 писал(а):

А если нужны конкретные значения, то теорема Эйлера вверху.

thought в сообщении #595189 писал(а):

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

А если уж совсем совсем конкретные значения, то $(m+500k,m)$ есть общее решение

[thought]

Shadow, спасибо, теорема Эйлера дает общее решение вида (m+4000k,m), да и применялась она не для описания всех решений, а для поиска конкретных решений. Принцип Дирихле дает положительный ответ на вопрос, теорема Эйлера дает примеры конкретных значений, ну а Вы выписали все решения.

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

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

тот нетривиальный факт, что 13 и 10000 взаимно просты

Я бы не назвал сей факт нетривиальным. Он тривиален Правда, является достаточно случайным.

[apriv]

Профессор Снэйп в сообщении #595293 писал(а):

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

тот нетривиальный факт, что 13 и 10000 взаимно просты

Я бы не назвал сей факт нетривиальным. Он тривиален Правда, является достаточно случайным.

Ну, как бы, это еще проверять нужно, что они взаимно просты. А если бы были два каких-то произвольных числа? Пришлось бы еще алгорифм Эвклида вспоминать, а факт-то верен и без взаимной простоты; она тут ни при чем совершенно.

[thought]

Достаточно вспомнить теорему о каноническом разложении, свойствах нод и факт и правда станет тривиальным

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

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

Ну, как бы, это еще проверять нужно, что они взаимно просты.

$10000 = 2^4 \cdot 5^4$, $13$ - простое число