Автор Тема: Простые множители.  (Прочитано 2432 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн yurikol

  • Новичок
  • *
  • Сообщений: 6
    • Просмотр профиля
Простые множители.
« : 11 Март 2015, 23:11:15 »
Цитировать
Можно найти и два четырехзначных числа, произведение которых
записывается восемью единицами.
Требуемое свойство имеют числа 7373 и 1507. Для того чтобы
найти их, надо разложить на множители число 11 111 111. Легко
видеть, что  111 111 = 1111X10001 = 11X101X10001.
Числа 11 и 101 далее на множители не раскладываются. Это так 
называемые простые числа. Последний множитель 10 001 простым не является,
но найти его разложение на простые множители не легко. Путем
деления этого числа на 3, 5, 7, 11, 13, 17 и другие простые числа можно,
в конце концов, найти делители числа 10 001 и разложить его.
Можно значительно сократить число проб, если заметить, что каждый
простой делитель обязательно должен иметь вид 8k +1. Это связано
с тем, что 10 001 = 104+1. Остается проверить только делимость на
17, 41, 73, 89, 97. Оказывается, что 10 001 не делится на 17, 41 и делится
на 73. Так получается разложение 10 001=73X137 и
11 111 111 = 11Х101Х73Х137=(101Х73)Х(ИХ137)=7373Х1507.

Почему простой делитель должен иметь только такой вид: 8к+1 ?
Почему к примеру не: 2к+1, 4к+1 ?


Оффлайн Artem of 93

  • Эксперт
  • ******
  • Сообщений: 1499
    • Просмотр профиля
    • Mozgovarka
Re: Простые множители.
« Ответ #1 : 12 Март 2015, 00:14:37 »
Думаю, что здесь даётся это выражение (8k + 1) для того, чтобы максимально сократить время на перебор вариантов. Ведь числа 17, 41, 73, 89, 97 имеют как вид 8k + 1, так и виды 2k + 1 и 4k + 1, а, например, вид 16k + 1 имеет уже не каждое из этих простых чисел. То есть, 8k + 1 - это оптимальный вариант.

Оффлайн yurikol

  • Новичок
  • *
  • Сообщений: 6
    • Просмотр профиля
Re: Простые множители.
« Ответ #2 : 12 Март 2015, 03:10:54 »
Цитировать
Ведь числа 17, 41, 73, 89, 97 
и.т.п.

Каким образом  по виду числа 10001 заранее отбросили другие простые множители ?
« Последнее редактирование: 12 Март 2015, 03:12:31 от yurikol »

Оффлайн Artem of 93

  • Эксперт
  • ******
  • Сообщений: 1499
    • Просмотр профиля
    • Mozgovarka
Re: Простые множители.
« Ответ #3 : 12 Март 2015, 15:47:36 »
Каким образом  по виду числа 10001 заранее отбросили другие простые множители ?

Я решил провести один эксперимент, но доказательства правильности выводов, к которым я пришёл, у меня нет. Просто самому стало интересно, есть ли здесь какая-либо взаимосвязь.

Итак, рассмотрим числа 101 + 1, 102 + 1 и 108 + 1.

Число 101 + 1 или 11 - простое. У всех простых чисел есть только один собственный делитель - число 1. Но также все простые числа кратны и себе, и, как известно, 11 делится на 11 без остатка. Это очевидно. Числа 1 и 11 имеют оптимальный вид 2k + 1 (при неотрицательном целом k).
Число 102 + 1 или 101 - тоже простое. Аналогичные рассуждения: числа 1 и 101 имеют оптимальный вид 4k + 1, ведь 100 не кратно 8.
Число 108 + 1 является составным. Если его разложить на множители, то получим 5 882 353 * 17. Оба этих числа имеют оптимальный вид 16k + 1. Ни 16, ни 5 882 352 не кратны 32.

На основании этого можно прийти к выводу, что делители числа, имеющего вид 102^n + 1 при целом n >= 0 имеют вид 2n + 1k + 1. Возможно, этот вывод, конечно, ошибочен.
« Последнее редактирование: 12 Март 2015, 16:11:32 от Artem of 93 »

Оффлайн yurikol

  • Новичок
  • *
  • Сообщений: 6
    • Просмотр профиля
Re: Простые множители.
« Ответ #4 : 12 Март 2015, 23:31:39 »
Возможно, этот вывод, конечно, ошибочен.


Цитировать
Можно значительно сократить число проб, если заметить, что каждый
простой делитель обязательно должен иметь вид 8k +1.

Так, мимоходом.
Название книжки: "Старинные занимательные задачи", ничего подобного не предвещало.  ;D