Арифметическое многоединичие.

Previous Entry Поделиться Next Entry
17 марта, 2018
e_kaspersky
"Дорогие радиослушатели, пишет нам..." - кажется так начинался один из развесёлых анекдотов еще старых-недобрых советских времён. Так вот, не так давно один из наших радио-интернет-ЖЖ-слушателей где-то тут пожаловался, что у него истекает лицензия на KIS и что пора бы снова какие-нибудь мозговые головоломки позадавать - это он так надеется чисто ментальными упражнениями [золотой] годовой ключик заполучить, - похвально! Их есть у нас - и задачек, и ключиков. К тому же на авто-мото-тему буквально только что произошел очередной конкурс, пора и на тему арифметически-математического тоже посоревноваться.

Согласен я по всем направлениям с нашими радиослушателями, что-то мы давно не упражняли серое вещество головного мозга - как бы оно из-за этого не загустело и не забродило! Этого я допустить никак не могу, посему вот вам следующая задачка:

1. Доказать, что если состоящее только из единиц число (111...111) делится на 2017, то оно же делится и на 9.

И сразу следом ->

2. Найти (без программирования, математическими выкладками) минимальное такое число. То есть, число, которое состоит только из единиц и делится без остатка на 2017 и 9

Еще раз объясняю, решения на перлах-джавах-питонах рассматриваются только как дополнительная проверка математическим доказательствам. Решение должно быть таким, чтобы его можно было воспроизвести карандашом на листе бумаги А4.

Ага?

Самые точные, оригинальные и остроумные ответы будут отмечены ценными призами, благодарственными грамотами и словами восхищения! :) Ну, поехали!

Метки:
Previous Entry Поделиться Next Entry

Записи из этого журнала по тегу «chtogdekogda»

  • Ответы о мячах.

    Всем привет! То ли моя недавняя задачка о мячах была слишком сложной, то ли слишком простой, а может быть просто не было достойной мотивации типа…

  • Задача о мячах.

    В эфире регулярная рубрика "О физико-математическом" - лучшая зарядка для ума, чтобы извилины были гладкими и шелковистыми, а серое вещество самой…

  • Воскресное. Рассказы и истории.

    За неделю эфирного молчания накопилось много интересного. Пора потихоньку возвращать долги. Короткими историями, а потом уже будут длинные и много…


Давайте попробуем:

Указанное число из t единиц можно представить как (10^t - 1) / 9 и по условию оно сравнимо с нулем по модулю 2017. 2017 число простое, следовательно 10^t сравнимо с 1 по модулю 2017.

Малая теорема Ферма утверждает, что t=2016 будет нужным показателем степени. Более того, мультипликативный порядок ненулевого остатка будет делителем числа 2016 = 2^5 * 3^2 * 7. Степени образуют циклическую группу. Фактически же наша задача состоит в том, чтоб показать, что для числа 10 мультипликативный порядок L = 2016. Тогда со всей очевидностью следует решение задачи, поскольку любое t будет делиться на L, а значит и соответствующее число будет делиться на 9, поскольку его сумма цифр будет кратна 2016, т.е. тоже делиться на 9. Ну и минимальное число так же будет представляться записью из 2016 единиц.

Ну а поскольку 10 не является квадратичным вычетом, не является вычетом 3й или 7й степени (делители 2016), то его мультипликативный порядок не может быть делителем 2016 отличным от него самого.
(последнее утверждение проверялось численно, но стоит подумать как и в этом вопросе обойтись без компьютера)

В конце не нолик, а единичка.
А почему Вас t=16 заинтересовало?

> последнее утверждение проверялось численно, но стоит подумать как и в этом вопросе обойтись без компьютера

Именно так. У меня получилось только с помощью калькулятора, чисто карандаш+бумага нет.. Там вычислений немного, но утомляет.

?

Log in

No account? Create an account