Математическое и загадочное

[E.K.]

Да, да, ошибся с количесвом единиц.

Но если "не придираться к запятым" - ответьте мне почему простые p>5 являются делителями чисел из 'p-1' единиц?

[E.K.]

Что интересно. Простое 'p>5' является делителем числа из 'p-1' единиц, но иногда не только! Например, 37 делит 111, а 13 делит 111111. Я немного потыкал и получился вот такой список простых чисел и количества единиц в числах типа 111...111, которые они делят.

 

7 : 6 (то есть 7 делит 111111).

11 : выколотый случай, оно само себя умеет делить Но если посмотреть на все делимые, то это:

11 : 10, 8, 6, 4, 2.

13 : 12, 6.

17 : 16 (и всё, больше нет).

19 : 18.

23 : 22.

29 : 28.

31 : 30, 15.

37 : 36, 33, 30, 27, 24, 21, 18, 15, 12, 9, 6, 3 (111 делится на 37).

41 : 40, 35, 30, 25, 20, 15, 10, 5.

43 : 42, 21.

 

Кто-нибудь видит закономерность?

 

Да, проверять на делимость следует только делители числа 'p-1'. Например,13 может делить "12 и делители 12-ти" единиц, то есть числа из 6, 4, 3 и 2 единиц. Остальные проверять не надо. Доказательство:

 

Если число 111...111 делится на простое ‘p’, это число минимальное и состоит из ‘n’ единиц, то и все числа типа {n}{n}…{n} будут делиться на ‘p’. При этом все прочие числа, где количество единиц не кратно ‘n’, на ‘p’ не делятся.

 

Пусть число с ‘m’ единиц делится на ‘p’.  То есть, {m единиц} = a*p

Поскольку ‘n’ минимальное такое, что {n единиц} = b*p, то из 'm единиц' вычитаем ‘n единиц’.

Получаем, что число вида: 111...111000...000 есть p*(b-a)

p – простое, то есть все двойки и пятёрки есть делители ‘b-a’ (поскольку у нас p>5).

Сокращаем двойки и пятёрки:  111...111 делится на p, где количество единиц = ‘m-n’.

Если 'm-n' > 'n' повторяем процедуру 'i' раз до тех пор, пока 'm_i-n' не окажется:

- равно 'n', то есть 'm' кратно 'n', либо же:

- 'm_i

Приехали.

[E.K.]

Я вроде бы решил.

А вы?

[E.K.]

Ну, ладно. Начинаю подсказывать.

 

 

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

Q2. Найти минимальное такое число, т.е. состоящее из единиц и делящееся на 2017 и 9.

 

Ну, поехали. Неспеша, потихоньку, пункт за пунктом ===>

 

Как всем давно известно, 2017 число простое. А чем хороши простые числа? С ними работать проще! Не верите? Сейчас убедитесь лично сами ->

 

Давайте рассмотрим последовательность 'П1' чисел, состоящих из единиц: 1, 11, 111, ...

 

Параграф 1. Во-первых, такое число (которое делится на 2017) существует. То есть, для простых ‘p>5’ в последовательности П1 рано или поздно найдётся число, которое делится на ‘p’ без остатка. Если это не так, то берём два числа с одинаковыми остатками от деления на 'p', то есть два числа {x,y} ≡ a (mod p). Такие есть, поскольку чисел в П1 бесконечно, а остатков всего 'p'. Вычитаем одно из другого, получаем число типа 111...111000...000. Поскольку p>5, то 'p' взаимопросто с 10=2*5, то можно делить на 100...000. Получаем что 111...111 ≡ 0 (mod p), то есть делится на 'p' без остатка. Приехали.

 

Я доступно излагаю эту среднюю арифметику?

 

// простая тройка вылетает в дальнейших рассуждениях, посему 'p>5'.

 

Итак, вывод номер-один. Числа 111...111 рано или поздно умеют делиться на 2017.

 

[продолжения следуют]

[Skarbovoy]

Число состоящее с единиц делится на 2017 если в тем 2016 * n единиц, n ∈ N, получено "экспериментально".

Почему оно делится на 9 - понятно, а с призноком делимости на 2017 затрудняюсь.

Сумма чисел в этом числе делится на 9 (2016, 2016 * 2 = 4032, 2016 * 3 = 6048, 2016 * 4 = 8064...), а значит и само число делится на 9.

[E.K.]

Число состоящее с единиц делится на 2017 если в тем 2016 * n единиц, n ∈ N, получено "экспериментально".

Почему оно делится на 9 - понятно, а с призноком делимости на 2017 затрудняюсь.

Сумма чисел в этом числе делится на 9 (2016, 2016 * 2 = 4032, 2016 * 3 = 6048, 2016 * 4 = 8064...), а значит и само число делится на 9.

Посыл неверный, поскольку он ведёт к обострению степеней верхних чисел. А нам нужно найти нижние грани арифметических оптимизаций. Так что, увы, ваше это - не работает.

[E.K.]

Продолжаю подсказывать дальше -->

 

Параграф 2. Аналогично доказывается, что если ‘m’ минимальное, которое делится на ‘p’ без остатка, то делятся без остатка все и только числа вида {m}{m}…{m}... Если существует какое-то 'n', меньшее 'm', такое что {m}...{m}{n} делится без остатка, то вычитаем из него {m}...{m} и получаем, что {n} делится на 'p' без остатка. То есть, 'm' не минимальное. Противоречие.

 

// Дальше уже сами или как?

[E.K.]

Параграф 3. Рассмотрим последовательность 'ПО' остатков от деления 111...111 на простое 'p':  1, 11, 111, 1111 (для p>1111) и так далее. Последовательность остатков от деления будут совпадать в каждой m-итеррации последовательности П1:

 

             1, 11, 111, ... m

             {m}1, {m}11, {m}111, … {m}{m}

 

То есть, можно рассматривать только остатки 1, 11, 111, ..., m - дальше они будут повторяться по циклу.

 

Последовательность остатков следует правилу:

 

Если 111...111 ≡ a (mod p) , то в последовательности П1 следующий 111...1111 ≡ 10*a + 1 (mod p)

То есть, каждый следующий член последовательности 'ПО' вычисляется из предыдущего по формуле 10*a + 1 (mod p)

 

Посмотрим, например, на остатки для 'p=7', это будет:  {0, 1, 4, 6, 5, 2, 0, ...}. Сразу видно, что в последовательности отсутствует '3' и что если бы '3' там была, то это был бы замкнутый на '3' цикл, поскольку следующий в последовательности будет:

 

             10*n + 1 = 30 + 1 = 2 + 1 = 3 (mod 7)

 

То есть, остаток '3' является вырожденным случаем для 'p=7'.

 

// Бонус трек. Последоватальности остатков 'П1' для некоторых других простых чисел:

 

Вернее, исследование как ведёт себя 10*a+1 на остатках по простым числам. Что интересно, всегда есть "выколотый" (пустой) цикл, состоящий из одного значения (это было доказано выше). А также иногда (но не всегда) цикл короче 'p-1' и все числа от 0 до 'p-1' (без "выколотого") разбиваются на меньшие циклы, но все они одинаковой длины! Это тема для дальнейших рассуждений...

 

11:        0, 1, 0  

             2, 10, 2

             3, 9, 3

             4, 8, 4

             5, 7, 5

             6, 6  

13:        0, 1, 11, 7, 6, 9, 0 

             3, 5, 12, 4, 2, 8, 3

             10, 10

17:        0, 1, 11, 9, 6, 10, 16, 8, 13, 12, 2, 4, 7, 3, 14, 5, 0

             15, 15

19:        0, 1, 11, 16, 9, 15, 18, 10, 6, 4, 3, 12, 7, 14, 8, 5, 13, 17, 0

             2, 2

23:        0, 1, 11, 19, 7, 2, 21, 4, 18, 20, 17, 10, 9, 22, 14, 3, 8, 12, 6, 15, 13, 16, 0

             5, 5

29:        0, 1, 11, 24, 9, 4, 12, 5, 22, 18, 7, 13, 15, 6, 3, 2, 21, 8, 23, 28, 20, 27, 10, 14, 25, 19, 17, 26, 0

             16, 16

31:        0, 1, 11, 18, 26, 13, 7, 9, 29, 12, 28, 2, 21, 25, 3, 0 

             4, 10, 8, 19, 5, 20, 15, 27, 23, 14, 17, 16, 6, 30, 22, 4

             24, 24

37:        0, 1, 11, 0 

             2, 21, 26, 2

             3, 31, 15, 3

             4, 4

             5, 14, 30, 5

             6, 24, 19, 6

             7, 34, 8, 7

             9, 17, 23, 9

             10, 27, 12, 10

             13, 20, 16, 13

             18, 33, 35, 18

             22, 36, 28, 22

             25, 29, 32, 25

41:        0, 1, 11, 29, 4, 0

             2, 21, 6, 20, 37, 2

             3, 31, 24, 36, 33, 3

             5, 10, 19, 27, 25, 5

             7, 30, 14, 18, 17, 7

             8, 40, 32, 34, 13, 8

             9, 9

             12, 39, 22, 16, 38, 12

             15, 28, 35, 23, 26, 15

43:        0, 1, 11, 25, 36, 17, 42, 34, 40, 14, 12, 35, 7, 28, 23, 16, 32, 20, 29, 33, 30, 0

             2, 21, 39, 4, 41, 24, 26, 3, 31, 10, 15, 22, 6, 18, 9, 5, 8, 38, 37, 27, 13, 2

             19, 19

 

Есть куда размышлять дальше, ой как есть куда...

[E.K.]

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

 

Что интересно, эту задачку мне прислали ровно два месяца назад - 18 января 2018 года. Но сначала просто тупо времени не было, потом время было рывками, подумать длительно не получалось. И вот - срослось по времени, желанию, да и в основы арифметики надо в интернетах подглядывать... И решение произошло.

 

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

[oit]

 

 

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

нам лучше что-нибудь попроще))

[E.K.]

нам лучше что-нибудь попроще))

Так куда же проще? Чистая арифметика, ни одного запредельного термина типа "интеграл", "логарифм", "неевклидовые пространства", "теорема Эйлера", "постоянная Ферма", "функция Лобачевского", "критерий Зейцмана"... ну и так далее.

 

Ладно, переходим к Параграфу четыре.

 

Параграф 4. Среди всех чисел {0,1,2,…p-1} есть одно и только одно число 'a', которое даёт "пустой" цикл. То есть 'a' не может быть остатком от деления на ‘p’ и более того, если есть число 111...111, которое даёт этот остаток ‘a’, то и следующее за ним даёт этот же остаток:

 

             111…111 ≡ a (mod p)

             111…1111 ≡ a (mod p)

 

             10a + 1 ≡ a (mod p)

             9a ≡ p-1 (mod p)

 

Поскольку ‘p’ простое и не равно 3, то у этого “9a ≡ p-1 (mod p)” есть единственное решение. Вот и всё. Очень просто. (подробности вот здесь).

 

// Замечание 4.1. Я же предупреждал, что с простыми числами работать очень просто!

// Замечание 4.2. Здесь рассуждения окончательны выходят за p={2,3,5}. Вот почему изначально 'p>5'.

 

Как следствие, такого остатка не существует. Иначе за ним будут сплошные {a,a,a, ...}, что противоречит цикличности 'ПО'.

 

То есть, возможных остатков деления последовательности 'П1' на 'p' всего 'p-1' = {0,1,...,p-1 / без 'a'}

 

// Замечание 4.3. Кстати, этот "Параграф 4" вроде как в дальнейших рассуждениях никак не применяется.. Но пусть будет, просто для арифметической красоты явления деления последовательности 111...111 на простое число 2017.

 

Замечание 4.4. Для p=2017 пустой цикл = 224. Это очень просто ->

 

10a + 1 ≡ a (mod 2017)

9a ≡ -1 = 2016 = 9*224 (mod 2017)

 

Как же легко работать с простыми числами!

 

a ≡ 224 (mod 2017)

 

Проверяем...

 

 

2241 = 2017 + 224.

 

Всё, приехали.

 

[ещё пара параграфов - "и золотой ключик у нас в руках!"]

[E.K.]

Да, я уверенно наблюдаю, что данная задачка вывела почти всех за пределы вывиха головного мозга, что мне как-то странно. Оная вопроса как-бы не является Великой Теоремой Ферма.. Ну, да и ладно. Не получилось - так пусть так и останется. Проблема в другом.. У меня как-бы более простых задачек не получается пока.

 

Посему, я продолжаю старую песню. Прошу обратить внимание на последующие изложения всей этой истории -->

 

Именно сейчас и здесь мы медленно подползаем к самому заглавному моменту решения этой нетривиальной задачки.

 

 

А давайте вычтем одно из другого!

 

- и на этом дальнейшее решение становится простым и обыденным. И всё на этом.

[E.K.]

Параграф 5. Рассмотрим разницы (дельты) между соседними значениями в последовательности остатков от деления, например:

 

1, 11, 111, 1111, 11111, ... - изначальная последовательность 'П1'.

0, 1, 4, 6, 5, 2, 0, ... - последовательность остатков от деления на 'p=7'.

1, 3, 2, 6, 4, 5, 1, ... - дельты между соседними в последовательности остатков (по модулю 7).

 

Очевидно, дельты тоже цикличны. Как и порождающая их сущность остатков.

 

То есть, цикл остатков 'ПО' однозначно определяет цикл дельт.

 

Теперь самое важное! => Значения в цикле дельт все различны.

 

То есть, не только остатки от деления 111...111 на простое 'p' все различны, но еще и разницы дельт в цикле тоже все разные, они в цикле никогда не повторяются.

 

Доказательство: (мы же здесь не блумберги какие-то, у нас же есть аргументы и факты железнее некуда) ==>

 

Если это не так, то есть две пары чисел, дельты между которыми равны внутри цикла. Это означает, что две пары чисел с количеством единиц меньше 'p' дают одинаковые дельты (разницы остатков) по модулю 'p'. Символами "на бумаге" это будет примерно вот так:

 

             111...111111...111000...000 ≡ a (mod p)  

             111...111000...000000...000 ≡ a (mod p)

 

Вычитаем:

 

             111...111*10^k ≡ 0 (mod p)

 

То есть, 111...111 должно делиться на 'p'. Что значит есть более короткий цикл. Противоречие.

[E.K.]

Параграф 6. Теперь самое главное: несколько слов в качестве доказательства. Тут много было разных исследований поведения остатков от деления П1=многоединичия 111...111 на простые числа, циклов остатков, даже разности какие-то вычитали из кого-то куда-то. Теперь пора бы заканчивать весь этот балаган. И уже переходить к более серьёзным материям уже пора бы. А их есть у нас! Этих серьёзных материй, даже ссылки на Википедию будут. Для пущей убедительности.

 

Ибо, вот оно:

 

- Кто в последовательности делится на 'p' без остатка? Тот, у кого дельта до следующего равна единице. (на примере с 'p=7' чуть выше всё прекрасно видно даже близоруким и дальнозорким тоже).

 

- Между какими подряд идущими дельты = 1?

 

             1111...111 ≡ 1 (mod p) 

             0111...111 ≡ 0 (mod p) 

 

Вычитаем:

 

             1000...000 = 1 (mod p)

 

Смотрим сюда в Википедию. Малая Теорема Ферма!

 

Оно.

 

Если 'p' - простое число и 'a' - целое число, не делящееся на 'p', то ->

 

             a^(p−1) ≡ 1 (mod p)

 

То есть, число из 2016 единиц делится на 2017. А поскольку в этом числе 2016 единиц, а 2+1+6=9 - то это же признак делимости на девять! То есть, 2016 единиц делятся на 2017 и на 9.

 

Отлично! Но вдруг там есть числа поменьше, которые делятся на 2017? А на этот вопрос нам отвечает Теорема Эйлера: их там нет.

[E.K.]

Параграф 7. Завершающий. Даже, не побоюсь этого термина, - итоговый. Вот он, а начинается с фразы про «лукавство» -->

 

На самом деле есть лукавство в предыдущей фразе «их там нет». Теорема Эйлера – это эпохальное событие, без сомнений. Но в нашем случае она совершенно не доказывает, что нет чисел меньше 2016 единиц, которые делятся на 2017. Число из 2016 единиц – да, оно делится на 2017, это было показано в верхних параграфах. Но как же разбираться с оставшимися числами, в которых чуть поменьше единиц...

 

Что же делать? И кто виноват? (с)

 

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

 

Но, однако, есть маленькая радость. Все 2015 оставшихся вариантов перебирать не надо. Из «Параграфа 2 и 4» следует, что минимальное ‘m’ количества единиц, которое делится на 2017, является делителем числа 2016. А какие есть всякие делители этого 2016 = 32*9*7 ? Очевидно, вот они все:

 

      1008, 672, 504, 336, 288, 252, 224, 168, 144, 126, 112, 96, 84, 72, 63, 56, 48, 42, 36, 32, 28, 24, 21, 18, 16, 14, 12, 9, 8, 7, 6, 4, 3, 2

 

Что-то многовато как-то этих чисел.. Но делать как-бы нечего. Берём арифмометр в свои мозолистые руки и начинаем крутить его циферблаты. А самые хардкорные читатели могут потренироваться тоже самое на обычных деревянных счётах, если такие есть под рукой.

 

Поехали. По всем делителям волшебно-восхитительного числа 2016.

 

2 -> 10^2 = 100 (mod 2017)

3 -> 10^3 = 1000 (mod 2017)

 

Это как-бы очевидно и понятно, да и без арифмометра.

 

4 -> 10^4 = 10000 = 1932 (mod 2017)

 

Ну, вот.. Началось. А что же дальше будет? «Но мы не привыкли отступать! Нам разгадать его поможет тележурнал ХочуВсёЗнать!» (с) – это я просто вот так бодрюсь и укрепляю силу духа. Но что это?.. Мелькнула небольшая разумная мысль.

 

10^6 = 10^4 * 10^2 ≡ (остаток от деления 10^4) * (остаток от деления 10^2) на 2017. То есть,

 

6 -> 4+2 -> 1932*100 ≡  1585 (mod 2017)

7 -> 6+1 -> 15850 ≡  1731 (mod 2017)

8 -> 4+4 -> 1932*1932 ≡  1174 (mod 2017)

9 -> 8+1 -> 11740 ≡  1655 (mod 2017)

 

Так повеселее пойдёт

И так далее со всеми остановками.

 

12 -> 1060

14 -> 1116

16 -> 665

18 -> 1956

21 -> 1527

24 -> 131

28 -> 967

32 -> 502

36 -> 1704

42 -> 77

48 -> 1025

56 -> 1218

63 -> 593

72 -> 1153

84 -> 1895

96 -> 1785

112 -> 1029

126 -> 691

144 -> 206

168 -> 765

224 -> 1933

252 -> 1469

288 -> 79

336 -> 295

504 -> 1788

672 -> 294

1008 -> 2016 = -1. О как! Практически приехали.

2016 -> (-1)*(-1) = 1

 

То есть, минимальное число из единиц, делящееся на 2017 без остатка ≡ это есть 111...111 из 2016 единиц. Все остальные «единичные» числа, делящиеся на 2017, содержат количество единиц, кратное 2016. А поскольку 2+0+1+6=9, то все они делятся на 9.

 

Доказано.

 

Вот такая небольшая головоломная доказательная база для вроде бы на первый взгляд не самой сложной арифметической задачки.

 

Аплодисменты, даже овации, поклонницы прыгают и цветы на сцену, реверанс и занавес.