Докажите, что для простых $%p>5$%$$\underbrace {11..1}_{p-1} \vdots p$$

P.S. Нужно решение без использования малой т. Ферма.

задан 17 Сен '18 18:14

10|600 символов нужно символов осталось
2

Достаточно доказать, что $%10^{p-1}-1$% делится на $%p$%. Это число из $%p-1$% девяток, и на 9 можно сократить в силу простейших свойств делимости (мы знаем, что 9 не делится на простое $%p > 5$%).

Рассмотрим граф, вершинами которого являются ненулевые остатки от деления на $%p$%, то есть числа $%r\in\{1,2,...,p-1\}$%. Для каждого такого $%r$% рассмотрим число $%10r$%. Оно, как и $%r$%, не делится на $%p$%, то есть даёт ненулевой остаток $%s$% от деления на $%p$%. В графе рисуем стрелочку от вершины $%r$% к вершине $%s$%.

Пример: пусть $%p=7$%. Тогда стрелочки пойдут так: $%1\to3\to2\to6\to4\to5\to1$%. Из каждой вершины выходит ровно одна стрелочка; здесь они образуют цикл. Но это не всегда так: при $%p=11$% у нас получатся отдельные циклы $%1\to10\to1$%, а также $%2\to9\to2$%, и прочие. Интересно пронаблюдать случай $%p=13$%: там будет два цикла длиной 6.

Теперь общее рассуждение: из любой вершины выходит ровно одна стрелочка. Идя по стрелкам, мы рано или поздно посетим вершину, в которой уже были. Значит, в графе есть циклы из стрелок. Рассмотрим самый короткий из них. Пусть он идёт из вершины $%r$% в себя, и состоит из $%k$% стрелок. Числа $%r$% и $%10^kr$% дают одинаковые остатки от деления на $%p$%. Значит, их разность $%(10^k-1)r$% делится на $%p$%. Ввиду того, что $%p$% простое, и $%1\le r\le p-1$% не делится на $%p$%, получаем, что $%10^k-1$% делится на $%p$%. Тогда для любой вершины $%s$%, пройдя из неё по $%k$% стрелочкам, мы придём обратно. Это значит, что все циклы у нас имеют одну и ту же длину $%k$% и при этом не пересекаются.

Общее число стрелок равно $%p-1=km$%, где $%m$% -- количество циклов. Отсюда следует, что $%10^{p-1}-1=(10^k)^m-1=(10^k-1)(10^{k(m-1)}+\cdots+10^k+1)$% делится на $%10^k-1$%, а потому и на $%p$%.

ссылка

отвечен 17 Сен '18 19:09

1

@falcao, все понял, благодарю!

(17 Сен '18 22:03) make78
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×811
×737
×111

задан
17 Сен '18 18:14

показан
282 раза

обновлен
17 Сен '18 22:03

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru