Что значит найти множество делителей числа

Нахождение всех делителей числа, число делителей числа.

Материал этой статьи про нахождение всех делителей числа. Сначала доказана теорема, которая задает вид всех общих делителей данного числа, после чего рассмотрены примеры нахождения всех делителей. Дальше показано, как вычисляется число делителей числа. В заключение подробно разобраны примеры нахождения всех общих делителей нескольких чисел и их количества.

Навигация по странице.

Все делители числа, их нахождение

Дальнейшее изложение подразумевает хорошее владение информацией статьи делители и кратные числа. Мы будем говорить лишь о поиске всех делителей целых положительных чисел (натуральных чисел). Этого вполне достаточно, так как одно из свойств делимости утверждает, что множество делителей целого отрицательного числа −a совпадает со множеством делителей противоположного числа a (которое будет положительным). Напомним также, что число 0 имеет бесконечно много делителей, и нахождение всех делителей нуля не представляет интереса.

Интереснее проходит поиск всех делителей составных чисел. Теоретическая основа этого процесса заключается в следующей теореме.

Из рассмотренной теоремы следует алгоритм нахождения всех положительных делителей данного числа. Чтобы найти все делители числа a нужно:

Весь процесс нахождения делителей удобно проводить, заполняя таблицу следующего вида:

Сначала разложим на простые множители число 567 :

Еще немного усложним пример.

Число делителей числа

Разложим 84 на простые множители:

число 84 имеет 24 делителя.

Нахождение всех общих делителей чисел и их количества

Из свойств наибольшего общего делителя следует, что множество делителей данных целых чисел совпадает со множеством делителей НОД этих чисел. Это утверждение относится как к двум числам, так и к трем, и к большему их количеству. Таким образом, чтобы найти все общие делители данных чисел, нужно определить НОД этих чисел и найти все его делители.

Рассмотрим решения примеров, в которых находятся все общие делители некоторых чисел.

Источник

Увеличивает ли соседство простых чисел количество делителей числа?

В последнее время я думал о числе 60.

Вавилонские счетоводы и землемеры основывали свою арифметику на шестидесятеричном счислении, возможно потому, что эта система помогает в работе с дробями. Если упорядочить объекты в группы по 60, их можно делить на половины, на трети, четверти, пятые, шестые, десятые, двенадцатые, пятнадцатые, двадцатые, тридцатые и шестидесятые части. Ни одно меньшее число не имеет такого количества делителей, и благодаря этому число 60 относится к элитному классу высокосоставных чисел (этот термин и его определение были предложены в 1915 году Сринивасой Рамануджаном.)

Но у числа 60 есть и другая особенность, которую я заметил только несколько недель назад, хотя о ней могли знать вавилоняне, а уж Рамануджан знал точно. Число 60 с его выдающимся количеством делителей тесно расположено между двумя другими числами, вовсе не имеющими делителей, за исключением 1 и самого себя: и 59, и 61 являются простыми. Такие пары простых чисел, разделённые одним промежуточным целым, называются числами-близнецами. Примерами таких чисел являются пары (5, 7), (29, 31) и (1949, 1951). На протяжении многих лет исследователи теории чисел внимательно изучали числа-близнецы. Меньшего внимания удостоилось число посередине — непрошенный гость, отделяющий близнецов друг от друга. Рискуя выглядеть немного слащавым, я назову это число посередине братом близнецов, или просто братом.

Является ли случайностью то, что число, находящееся между двумя простыми, настолько непростое? Действительно ли 60 необычно в этом отношении, или существует некий паттерн, общий для всех чисел-близнецов и их братьев? Можно представить, что существует какой-то принцип справедливости: если число окружено с двух сторон бедными на делители соседями, оно должно иметь множество делителей, чтобы скомпенсировать, уравновесить ситуацию. Возможно, каждая пара чисел-близнецов образует сэндвич с курицей и салатом, состоящий из двух ломтей простого хлеба, между которыми сжата мягкая начинка, нарубленная на множество мелких кусков.

Чтобы быстро проверить эту гипотезу, давайте составим график количества делителей для каждого целого числа в интервале от до :

На Рисунке 1 числа-близнецы отмечены голубыми точками, а их братья — тёмно-синими. Высокосоставные числа (, которые имеют больше делителей, чем любое меньшее ) выделены жёлтым контуром. [Обратите внимание, что 1 и 2 отмечены как высокосоставные числа, хотя они вообще не составные. Поди их разбери.]

График даёт нам понять, что многие братья близнецов (4, 6, 12 и 60) и в самом деле являются высокосоставными числами-рекордсменами, однако другие братья ими не являются (18, 30, 42 и 72). А некоторые высокосоставные числа (24, 36, 48) не расположены между числами-близнецами. Как бы то ни было, тёмно-синие точки расположены ближе к верхнему краю графика, оставляя чёткое впечатление, что братья близнецов склонны иметь множество делителей, больше, чем типичное целое число того же размера.

Интервал 1–75 является очень небольшой выборкой натуральных чисел, к тому же он достаточно необычен, поскольку чисел-близнецов много среди небольших целых, но дальше вдоль числовой оси они становятся достаточно редкими. Чтобы взглянуть на тему шире, рассмотрим количество делителей для всех положительных целых чисел до . [Чемпионом по делимости среди этих чисел является , имеющее 768 делителей. Оно не является братом.]

Среднее значение на этом интервале равно 18,5751. Но если рассмотреть только братьев (а их на этом интервале 440312), то среднее количество делителей становится больше почти в три раза: 51,5889. Числа, имеющие единственного простого соседа (или , или , но не оба сразу), тоже имеют высокое среднее : 32,1199.

На Рисунке 2 представлен график для того же интервала; на нём последовательность из 100 миллионов чисел разбита на 500 блоков размером по 200000, и взято среднее значение для каждого блока.

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

Однако позвольте мне предложить менее изысканное объяснение. Все простые числа (за одним известным исключением) являются нечётными, то есть все ближайшие соседи простых чисел (опять-таки, за одним исключением) являются чётными. Иными словами, соседи простых чисел имеют делитель 2, что даёт им мгновенное преимущество в гонке по накоплению делителей. Соседи близнецов имеют и ещё одно преимущество: все они (за одним исключением) делимы и на 3, и на 2. Почему? Среди трёх последовательных чисел одно должно быть кратным 3, и это не может быть один из близнецов, следовательно, это их брат.

Делимость на 2 и 3 означает также делимость брата на 6. Любые другие простые делители брата умножаются на 2 и 3, создавая ещё больше делителей. Например, число, делящееся на 2, 3 и 5, также делится на 10, 15 и 30.

Учитывая этот мультипликативный эффект, кажется возможным, что делимости на 2 и 3 достаточно для объяснения выделяющегося на фоне остальных избытка делителей. Согласно этой гипотезе, близость простых чисел никак с этим не связана; братья богаты делителями просто потому, что являются кратными 6. Рисунок 3 подтверждает эту мысль. Для , целые числа, остаток от деления на 6 которых равен нулю, имеют в два раза больше делителей, чем любой другой класс. (Простые числа находятся в классах 1 и 5.)

Однако более внимательное изучение Рисунка 3 даёт нам основание для опасений. На графике среднее значение для делимых на 6 чисел примерно равно 43, но мы уже знаем, что для братьев (подмножества делимых на 6 чисел, расположенных между числами-близнецами) больше 51. Это наблюдение даёт нам понять, что в конечном итоге простые числа по соседству всё-таки имеют определённое влияние на избыток делителей.

Дополнительные доказательства можно получить из ещё одного графика для чисел с простыми соседями и без них, но на этот раз ограниченного числами, делимыми на 6. Следовательно, все элементы популяции выборки имеют одинаковое преимущество. На Рисунке 4 показаны результаты этого эксперимента.

Если бы простые соседи не оказывали влияния (кроме гарантий делимости на 6), то синяя, зелёная и красная кривые имели бы одну траекторию, но это не так. Хотя отрыв братьев в гонке делителей немного уменьшился, он не пропал полностью. Числа с двумя простыми соседями имеют примерно на 20% больше делителей, чем общее среднее для чисел, делящихся на 6. Числа с одним простым соседом тоже немного выше среднего. Следовательно, делители 2 и 3 не могут объяснить всё.

Вот простая попытка объяснения того, в чём может быть дело: аналогично тому, что любые три последовательные числа должны включать в себя одно, кратное 3, любые пять последовательных чисел должны включать в себя число, кратное 5. Если выбрать случайно, то мы можем быть уверены, что ровно один элемент множеста делится на 5. Так как выбирается случайно, все элементы множества с равной вероятностью могут брать на себя эту роль, поэтому можно сказать, что 5 является делителем с вероятностью 1/5.

Но предположим, что является братом близнецов. Тогда и являются простыми, и ни одно из них не может быть кратным 5. Следовательно, нам нужно перераспределить вероятность на три оставшихся элемента множества. Похоже, теперь кратно 5 с вероятностью 1/3. Подобные рассуждения можно применить к делимости на 7, на 11 или на любое другое простое число. В каждом из случаев вероятность увеличивается наличием соседних простых чисел.

То же рассуждение работает и в случае, если его перевернуть. Знание того, что чётно, даёт нам понять, что и нечётны. Если также кратно 3, мы знаем, что и не кратны 3. Аналогично с 5, 7, и так далее. Следовательно, нахождение избытка делителей повышает вероятность того, что соседи являются простыми.

Логична ли эта схема? У нас есть вполне обоснованные причины для сомнений. Вероятность никак не связана с распределением делителей среди целых чисел. Определяющий делимость процесс заключается в простом подсчёте, и в нём нет ничего случайного. Представьте, что вы раздаёте карты игрокам, сидящим за очень длинным столом, и их стулья пронумерованы от 1 до бесконечности. Сначала вы раздаёте каждому из игроков карту 1. Затем, начиная с игрока 2, вы раздаёте каждому второму игроку карту 2. Затем карту 3 игроку 3 и каждому третьему игроку после него, и так далее. Когда вы закончите (если вы закончите!), каждый игрок будет держать карты, соответствующие всем делителям числа на его стуле, и никаких других карт.

Эта процедура раздачи карт кажется мне логичным объяснением того, как устроены целые числа. Добавление вероятностного элемента коренным образом изменяет алгоритм. Так как мы раздаём делители, время от времени игрок отказывается брать карту, говоря «Извините, но я простое число, пожалуйста, передайте её одному из моих соседей». Затем вы случайным образом выбираете из множества соседей получателя, находящегося в подходящем интервале.

Построение числовой системы случайной раздачей делителей подобно лотерейным билетам может быть приятным развлечением, но оно не даст нам те числа, которые мы знаем и любим. Простые числа не отказывают раздающему делители; напротив, простое число является простым, потому что ни одна из карт от 1 до не попадает на его место. И числа, делящиеся на 5, не разбросаны по числовой прямой в соответствии с каким-то локальным распределением вероятности; они встречаются с абсолютным постоянством на каждой пятой позиции. Добавление вероятности в этот контекст кажется запутывающим и бесполезным.

Но тем не менее… Тем не менее! Оно работает.

На Рисунке 5 показана доля всех , делимых на 5, классифицированных согласно количеству близких к простых чисел. Общее среднее равно 1/5, как и должно быть. Но среди братьев с двумя простыми соседями доля близка к 1/3, как и предсказывает вероятностная модель. И примерно 1/4 чисел с одним простым соседом является кратным 5, что опять-таки соответствует прогнозам вероятностной модели. И обратите внимание, что значения без простых соседей имеют меньшую, чем средняя доля кратных 5. В каком-то смысле этот факт не удивляет и даже неизбежен: если среднее постоянно, и одна подгруппа имеет избыток, то дополнение к этой подгруппе должно иметь дефицит. Тем не менее, это кажется странным. Как может отсутствие простых соседей опускать плотность делящихся на 5 чисел ниже общего среднего? В конце концов, мы знаем, что кратные 5 числа неизменно становятся каждым пятым целым числом.

Рассказывая о подобных причудах братьев, я не хочу сказать, что в теории чисел есть какой-то глубокий изъян или парадокс. Фундамент арифметики не трескается из-за того, что я встретил больше ожиданного количества пятёрок в богатых простыми числами сегментах числовой прямой. Никакие числа не удалились со своих мест в последовательности целых чисел; нам не нужно их выслеживать и возвращать на нужные позиции. Изменения требует только моё понимание их распределения. Иными словами, вопрос не столько в том, что происходит, сколько в том, как правильно это воспринимать.

Я знаю множество неверных способов. Мысль о том, что числа-близнецы отпугивают делители, а братья привлекают их — это просто сказка вроде истории о крокодиле, вытянувшем нос слонёнка. Её можно принять в качестве метафоры, но не как механизм. Между целыми числами не действуют никакие силовые поля. Числа не могут ощущать свойств своих соседей. Не имеют они и индивидуальности; они не жадны и не расточительны, не общительны и не замкнуты.

Вероятностная формулировка кажется более подходящей, чем наша сказка, тем, что позволяет избежать явного упоминания причинных связей между числами. Но эта мысль всё равно таится под её поверхностью. Что значит выражение «Присутствие простых соседей увеличивает шансы числа делиться на 5»? Уж точно не то, что простое число каким-то образом влияет на результат броска монеты или вращение колеса рулетки. Это заявление имеет смысл только как эмпирическое, статистическое наблюдение: при исследовании большого количества целых чисел выяснено, что те из них, которые находятся ближе к простым числам, имеют делитель 5 чаще, чем те, которые находятся дальше. Это утверждение истинно, но оно не говорит нам, почему оно истинно. (И нет гарантии, что это наблюдение истинно для всех чисел.)

Вероятностные рассуждения не новы в теории чисел. В 1936 году Харальд Крамер писал:

Что касается порядковых простых чисел, то хорошо известно, что, грубо говоря, мы можем оценить вероятность того, что целое число должно быть простым, приблизительно как .

Крамер даже построил целую вероятностную модель простых чисел, проигнорировав все вопросы о делимости и просто объявив каждое целое число простым или составным на основании броска монеты (с перекосом в соответствии с вероятностью ). В некоторых аспектах эта модель работала потрясающе. Как показано на Рисунке 6, она не только соответствует общей тенденции распределения простых чисел, но и даёт достаточно хорошую оценку распространённости чисел-близнецов.

Однако в случайной модели Крамера отсутствует намного большее. В частности, в ней совершенно упущены необычные свойства братьев чисел-близнецов. В области числовой прямой, показанной на Рисунке 6, от 1 до , истинные братья имеют в среднем 44 делителя. Братья Крамера являются просто случайной выборкой порядковых целых чисел, имеющей в среднем 16 делителей.

По существу, распределение братьев нераздельно связано с распределением чисел-близнецов. Одних не может быть без других. Этот вывод бесполезен, ведь распределение простых чисел (как близнецов, так и не близнецов) — одна из глубочайших загадок современной математики.

В своих рассуждениях я охарактеризовал уникальные свойства братьев, подсчитывая их делители. Существуют и другие способы подхода к этой задаче, дающие схожие результаты. Например, можно вычислить сумму делителей вместо количества . Это приведёт нас к классическим понятиям избыточных, совершенных и недостаточных чисел. Число избыточно, если 2n$» data-tex=»inline»/>, идеально, если , и недостаточно, если . Когда я написал программу для сортировки братьев на эти три категории, то с удивлением обнаружил, что за исключением 4 и 6 каждый брат близнецов является избыточным числом. Такой характерный результат показался мне примечательным и важным. Но потом я узнал, что каждое число, делимое на 6, кроме самой шестёрки, является избыточным.

Ещё один подход заключается в подсчёте простых множителей , а не делителей. Эти две величины имеют сильную корреляцию, хотя и количество делителей не является просто функцией от количества множителей; она также зависит от делимости множителей.

Как видно из Рисунка 7, подсчёт простых множителей рассказывает нам историю, похожую на историю подсчёта делителей. Типичное целое число в интервале до имеет около четырёх простых множителей, а типичный брат в том же интервале — больше шести.

Также мы можем рассмотреть размер самого большого простого множителя (), который связан с концепцией гладкого числа. Число является гладким, если все его простые множители меньше какой-то заданной границы, которая может быть фиксированной константой или функцией от , например . Одним из показателей гладкости является . Вычисления показывают, что по этому определению братья более гладкие, чем среднее: соотношение логарифмов примерно равно 2,0 для братьев и примерно 1,7 для всех чисел.

Ещё один посторонний факт: ни один брат, за исключением 4, не является полным квадратом. Доказательство: предположим, что — брат. Тогда , а это число имеет множители и , то есть не может быть простым. Обобщив это рассуждение, мы исключим из списка возможных братьев кубы и все полные степени более высокого порядка.

Когда я впервые начал разбираться с братьями, то стал изучать, что по этой теме могли сказать другие люди. Я не нашёл особо много информации. Хотя объём литературы по числам-близнецам огромен, в ней рассматриваются сами простые числа, и особенно вопрос о существовании бесконечного количества близнецов — гипотеза, остававшаяся недоказанной в течение 170 лет. В этих трудах редко упоминаются числа, зажатые в сэндвиче между двумя простыми числами.

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

Может ли быть так, что я первым заметил любопытные свойства братьев чисел-близнецов? Нет. Я уже давно вышел из возраста подобных забавных мечтаний. Если я не обнаружил никаких ссылок, то это без сомнения указывает на то, что я ищу не там.

В конечном итоге я нашёл несколько интересных статей и писем. Неудивительно, что ключом к их обнаружению была Онлайн-энциклопедия целочисленных последовательностей (OEIS), которая, похоже, всё больше начинает функционировать как Индексный указатель математики. Сначала я обратился к нему, но в статье о последовательностях братьев, названной «Среднее пар чисел-близнецов» имелась только одна ссылка, и она явно не была обильным источником просвещения. Она привела меня к тому журнала Eureka за 1967 год, выпускаемого кембриджским математическим сообществом The Archimedians. Всё, что я там нашёл (на странице 16) — это очень краткая задача, в которой нужно было продолжить последовательность 4, 6, 12, 18, 30, 42,…

На этом дело на несколько недель приостановилось, но позже я вернулся к OEIS, чтобы изучить перекрёстные ссылки на другие похожие последовательности. В разделе высокосоставных чисел я нашёл ссылку на статью Бенни Лима Prime Numbers Generated From Highly Composite Numbers (Parabola, 2018 год). Лим изучил соседей первой тысячи высокосоставных чисел. В верхней части интервала числа очень велики (), а простые числа крайне редки, но, как выяснил Лим, они не так редки среди ближайших соседей высокосоставных чисел.

Ещё одна перекрёстная ссылка привела меня к последовательности A002822, помеченной как «Числа , такие, что , являются числами-близнецами». Другими словами, это множество чисел, которые при умножении на 6 дают братьев чисел-близнецов. Вот несколько первых членов последовательности: 1, 2, 3, 5, 7, 10, 12, 17, 18, 23, 25, 30, 32, 33, 38. Статья в OEIS содержит ссылку на статью 2011 года Франчески Балестриери, в которой предлагается интригующая идея, но усвоить её полностью мне пока не удалось. Балестриери показала, что является составным, если можно выразить как для неких целочисленных и ; в противном случае оно является простым. Существует и похожее, но чуть более сложное правило для . Далее она доказывает следующую теорему:

Гипотеза о числах-близнецах истинна тогда и только тогда, когда существует бесконечное множество , таких, что и и для всех .

Другие цитаты вывели меня на три статьи Антони Динкулеску, датированные 2012-2018 годами, в которых исследуются близкие темы. Но самыми впечатляющими документами стали два письма, написанные Нилу Слоуну, основателю и главной движущей силе OEIS. В 1984 году достопочтенный Соломон Голомб написал ему, чтобы сообщить о множестве публикаций 1950-х и 60-х, в которых упоминается связь между и числами-близнецами. Самым первым из таких упоминаний стала задача в American Mathematical Monthly, предложенная и решённая самим Голомбом. Когда он совершил это открытие, ему было 17 лет, и это была его первая математическая публикация. Чтобы подтвердить своё заявление о первенстве, он предложил награду в 100 долларов тому, кто сможет найти более раннюю литературу.

Во втором письме Мэттью Майерс из Спрюс-пайн (Северная Каролина) представил два таких более ранних материала. Первый — это хорошо известная история теории чисел Л. Диксона, опубликованная в 1919 году. Второй — это Essai sur les nombres premiers Вольфганга Людвига Крафта, коллеги Эйлера по Академии наук в Санкт-Петербурге. Эссе было прочитано академии в 1798 году и опубликовано в 12-м томе Nova Acta Academiae Scientiarum Imperialis Petropolitanae. В ней подробно раскрывается тема . Эссе было выпущено за пятьдесят лет до появления понятия чисел-близнецов, а гипотеза об их бесконечности была предложена Альфонсом де Полиньяком.

Майерс сообщил об этих археологических находках в 2018 году. К сожалению, Голомб скончался двумя годами ранее.

Источник