Мой друг инженер недавно меня удивил. Он сказал, что не уверен, является число 1 простым или нет. Я удивилась, потому что никто из математиков не считает единицу простым.Путаница начинается с определения, которое дают простому числу: это положительное целое число, которое делится только на 1 и само на себя. Число 1 делится на 1, и оно делится само на себя. Но деление на себя и на 1 здесь не является двумя различными факторами. Так простое число это или нет? Когда я пишу определение простого числа, то пытаюсь устранить эту двусмысленность: я прямо говорю о необходимости ровно двух различных условий, деление на 1 и само на себя, или что простое число должно быть целым числом больше 1. Но зачем идти на такие меры, чтобы исключить 1?
Моё математическое образование научило меня, что хорошей причиной того, почему 1 не считается простым, является основная теорема арифметики. Она утверждает, что каждое число может быть записано как произведение простых чисел ровно одним способом. Если бы 1 было простым, мы бы потеряли эту уникальность. Мы могли бы записать 2 как 1?2, или 1?1?2, или 1594827?2. Исключение 1 из простых чисел устраняет это.
Изначально я планировала в статье объяснить основную теорему арифметики и покончить с этим. Но на самом деле не так сложно изменить формулировку теоремы для решения проблемы с единицей. В конце концов, вопрос моего друга разжёг моё любопытство: как математики остановились на этом определении простого числа? Беглый поиск по Википедии показал, что единица раньше считалась простым числом, а сейчас нет. Но статья Криса Колдуэлла и Енг Сюна демонстрирует немного более сложную историю. Это можно понять с самого начала их статьи: «Во-первых, является ли число (особенно единица) простым — это вопрос определения, то есть вопрос выбора, контекста и традиции, а не вопрос доказательства. Тем не менее, определения не возникают случайным образом; выбор связан с нашим использованием математики и, особенно в этом случае, нашей нотацией».
Колдуэлл и Сюн начинают с классических греческих математиков. Они не считали 1 числом так же, как 2, 3, 4 и так далее. 1 считалась цифрой, а число состояло из нескольких цифр. По этой причине 1 не могла быть простым — это даже не число. Арабский математик IX века аль-Кинди писал, что это не число и, следовательно, не является чётным или нечётным. В течение многих веков преобладало представление, что единица — это строительный блок для составления всех чисел, но не само число.
В 1585 году фламандский математик Саймон Стевин указал, что в десятичной системе нет никакой разницы между 1 и любыми другими числами. Во всех отношениях 1 ведёт себя как любая другая величина. Хотя и не сразу, но это наблюдение в конечном итоге привело математиков к принятию 1 как любого другого числа.
До конца XIX века некоторые выдающиеся математики считали 1 простым, а некоторые нет. Насколько я могу судить, это не было причиной разногласий; для самых популярных математических вопросов различие не являлось критически важным. Колдуэлл и Сюн цитируют Г. Х. Харди как последнего крупного математика, считающего 1 простым (он явно указал его в качестве простого числа в первых шести изданиях «Курса чистой математики», опубликованных между 1908 и 1933 годами, а в 1938 году изменил определение и назвал 2 наименьшим простым).
В статье упоминаются, но не разбираются подробно изменения в математике, из-за которых 1 исключили из списка простых чисел. В частности, одним из важных изменений стала разработка множеств за пределами множества целых чисел, которые ведут себя как целые.
В самом простом примере мы можем спросить, является ли число -2 простым. Вопрос может показаться бессмысленным, но он побуждает нас выразить словами уникальную роль единицы среди целых чисел. Самым необычным аспектом 1 является то, что его обратное значение тоже является целым числом (обратное значение x — это число, которое при умножении на x даёт 1. У числа 2 обратное значение 1/2 входит в множество рациональных или действительных чисел, но не является целым: 1/2?2=1). Число 1 оказалось собственным обратным числом. Ни у какого другого положительного целого числа нет обратного значения в множестве целых чисел. Число с обратным значением называется обратимым элементом. Число ?1 тоже является обратимым элементом в наборе целых чисел: опять же, оно обратимый элемент само для себя. Мы не рассматриваем обратимые элементы как простые или составные, потому что вы можете умножить их на некоторые другие обратимые элементы без особых изменений. Тогда мы можем считать, что число -2 не так уж отличается от 2; с точки зрения умножения. Если 2 является простым, то и ?2 должно быть таким же.
Я старательно избегала в предыдущем абзаце определения простого из-за неудачного факта, что для этих больших множеств такое определение не подходит! То есть оно немного нелогично, и я бы выбрала другое. Для положительных целых чисел у каждого простого числа p два свойства:
Его нельзя записать как произведение двух целых чисел, ни одно из которых не является обратимым элементом.
Если произведение m?n делится на p, то m или n должны быть делимы на p (для примера, m=10, n=6, а p=3.)
Первое из этих свойств — то, как мы могли бы охарактеризовать простые числа, но, к сожалению, тут получается неприводимый элемент. Второе свойство — это простой элемент. В случае натуральных чисел, конечно, одни и те же числа удовлетворяют обоим свойствам. Но это не относится к каждому интересному набору чисел.
В качестве примера рассмотрим множество чисел вида a+bv?5 или a+ibv5, где a и b — целые числа, а i — квадратный корень из ?1. Если вы умножите числа 1+v?5 и 1-v?5, то получите 6. Конечно, вы также получите 6, если умножите 2 и 3, которые тоже находятся в этом множестве чисел при b=0. Каждое из чисел 2, 3, 1+v?5, и 1?v?5 нельзя представить как произведение чисел, которые не являются обратимыми элементами (если не верите мне на слово, это не слишком трудно проверить). Но произведение (1+v?5)(1?v?5) делится на 2, а 2 не делится ни на 1+v?5, ни на 1?v?5 (опять же, можете проверить, если не верите мне). Таким образом, 2 является неприводимым элементом, но не простым. В этом наборе чисел 6 можно разложить на неприводимые элементы двумя различными способами.
Приведённое выше число, которое математики могут назвать Z[v-5], содержит два обратимых элемента: 1 и ?1. Но есть аналогичные множества чисел с бесконечным количеством обратимых элементов. Поскольку такие множества стали объектами изучения, есть смысл чётко разграничить определения обратимого, неприводимого и простого элементов. В частности, если есть множества чисел с бесконечным числом обратимых элементов, становится всё труднее понять, что мы подразумеваем под уникальной факторизацией чисел, если не уточнить, что обратимые элементы не могут быть простыми. Хотя я не историк математики и не занимаюсь теорией чисел и хотела бы прочитать больше, как именно происходил этот процесс, но я думаю, что это одна из причин, которые Колдуэлл и Сюн считают причиной исключения 1 из простых чисел.
Как это часто бывает, мой первоначальный аккуратный и лаконичный ответ на вопрос, почему всё устроено так, как есть, в конечном итоге стал только частью проблемы. Спасибо моему другу за то, что задал вопрос и помог мне узнать больше о сложной истории простоты.
Комментарии (50)
TheGodfather
07.05.2019 15:52Путаница начинается с определения, которое дают простому числу: это положительное целое число, которое делится только на 1 и само на себя.
Сами определение выдумали? Википедия, конечно, не самый авторитетный источник, но все же:
A prime number (or a prime) is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers
Просто?е число? — натуральное (целое положительное) число, имеющее ровно два различных натуральных делителя — единицу и самого себя[
math.wikia:
Просто?е число? — это натуральное число, больше единицы, имеющее ровно два натуральных делителя: 1 и само себя
Кажется, вы взяли за основу неверное определение и на его основе начали что-то выдумывать…
Mingun
07.05.2019 16:58Это проблема курицы и яйца — естественно, сейчас в Википедии и других современных источниках определение, исключающее единицу из числа простых
5oclock
07.05.2019 19:34"… каждое число может быть записано как произведение простых чисел ровно одним способом. Если бы 1 было простым, мы бы потеряли эту уникальность. Мы могли бы записать 2 как 1?2, или 1?1?2, или 1594827?2. Исключение 1 из простых чисел устраняет это"
А тогда произведением каких простых чисел записать любое простое число?
2, 3, 11, 29?yeputons
07.05.2019 22:38+1Произведение из одного элемента: самого простого числа. Примерно как
SUM(1)=1в SQL.5oclock
08.05.2019 06:09В математике такое практикуется?
Первый раз слышу.yeputons
08.05.2019 09:43+1Да, вполне себе практикуется, когда надо перемножить произвольное число членов. С суммой аналогично, например, сумма квадратов чисел от 1 до n:
Тут вполне разумно считать, что для n=1 эта сумма равна своему единственному члену
o5a
08.05.2019 13:09Сумма все же несколько другое, она представляет собой сложение всех элементов. А можно ссылку, где применяется произведение из одного числа, без указания множителя? Т.к. произведение подразумевает «взять некое число N раз».
masai
08.05.2019 19:49Почему сумма — это другое? Сумма и произведение отличаются только операцией, которая «расставляется» между значениями.
Mingun
08.05.2019 21:02А степень подразумевает «умножить некое число N раз». Тем не менее, думаю вы не будете спорить, что дробные или отрицательные степени очень даже практикуются в математике
ainoneko
08.05.2019 09:56То есть сумма/произведение принимают в качестве аргумента список.
Если он пуст, возвращают "нейтральный элемент" этой операции.
Это, кстати, отвечает на вопрос, произведением каких простых чисел является единица: никаких (пустой список).
o5a
08.05.2019 12:59+1Думаю, все пошло от некорректного (или устаревшего в связи с признанием 1 непростым) определения. В английском варианте основная теорема арифметики имеет как раз уточнение, отвечающее на ваш вопрос (wiki):
every integer greater than 1 either is a prime number itself or can be represented as the product of prime numbers
yurixi
07.05.2019 21:18+1Попробуем определить простые числа так:
Простые числа это натуральные числа которые не делятся на другие простые числа.
Единица как минимальное натуральное не делится на другие числа, значит оно простое, а дальше, раз все другие числа делятся на единицу, то других простых чисел, кроме единицы, нет. Приехали.
Наша попытка дать определение провалилась. Ведь это не определение, а свойство простого числа. Если взять второе свойство — не быть единицей, то определение будет в том, что у простого числа два представленных свойства. И тогда все нормально. 2, 3, 5, 7, ...
То есть, свойство простого числа не быть единицей обязательно.
Mingun
07.05.2019 23:01Просто нужно ввести 2 типажа:
trait Prime {}иtrait One : Prime {}.
Или даже 3:
trait PrimeBase {}trait One : PrimeBase {}trait Prime : PrimeBase {}— для определений, которые к единице неприменимы. В общем-то сейчас так и сделали, просто почему-то не сказали об этой явно, и в разных контекстах возможно под словосочетанием "простое число" имеют ввиду один из этих 3-х типов.
Sirion
08.05.2019 10:44в разных контекстах возможно под словосочетанием «простое число» имеют ввиду один из этих 3-х типов.
Насколько мне известно, нет. Честно говоря, я не могу сходу придумать естественных примеров, когда включение единицы в простые числа сделает что-то проще. Ну, кроме определения простых чисел.Mingun
08.05.2019 21:12Откуда тогда споры если все сходятся в определении?
Sirion
08.05.2019 23:11Насколько мне известно, среди математиков-специалистов споров нет. Я могу, конечно, ошибаться, я так и не стал настоящим математиком, и в мир труъ-науки заглядываю одним глазком. Но все споры на эту тему, которые слышал лично я, происходили с участием людей, не изучавших математику дальше школьной и того странного предмета, который называется «Высшей математикой» в вузах.
Alexey_Alive
08.05.2019 05:43А вот что меняется от того является ли единица простым числом или нет? То есть какой практический толк от спора?
yeputons
08.05.2019 09:47Какие-то теоремы чуть проще формулировать, если единицу простым числом не считать. Например, основная теорема арифметики, которая упоминается в статье.
Какие-то теоремы про простые числа тогда также хорошо обобщаются на более общие структуры вроде целых чисел (а не натуральных) и гауссовых целых чисел. Получаем одно общее определение — удобнее работать.
Cadil_TM
08.05.2019 10:56Несколько не по теме: о формуле простых чисел. Многие серьезные математики (и не только) занимались этой проблемой, но до сих пор — вопрос открытый. Запомнилась одна из последних попыток (автора не помню): 6i — 1, 6i + 1, где i = 1,2,3….
Дело, казалось бы, за малым: убрать из ряда квазипростые числа — произведение простых чисел. Например, 5 * 7 = 35 — не простое число.
Интересно, будет в ближайшее время найдена формула простых чисел? Какие прогнозы?yeputons
08.05.2019 11:33Определить "формулу" мы можем либо очень узко (вроде "можно использовать только арифметические операции", тогда там вообще ничего разумного не сделать), либо так, что получается выражать произвольные алгоритмы. А написать программу для вычисления простых чисел, конечно же, можно. Про это есть прекрасный ответ на английском от Alon Amit на Quora.
Например, вот формула, которая выдаёт 1, если число простое, и 0 иначе (взята из ответа выше):
Как работает: надо проверить, что для каждого числа от 2 до n-1 выражение n%d не равно нулю. Другими словами, все выражения вида d-(n%d) равны нулю. А деление на d с округлением вниз — это как раз такой "if". То есть внутренняя сумма — это количество делителей числа n от 2 до n-1.
Если захотим выразить простое число под номером n, это тоже легко делается через P(n):
Тут мы просто нашли минимальное m такое, что от 2 до m встречается ровно n простых чисел.
Каким-то аналогичным образом можно, например, закодировать любой алгоритм в виде многочлена, в том числе для простых чисел.
vics001
09.05.2019 02:45Полином Матиясевича — habr.com/ru/news/t/406485/#comment_18361061.
Разные теоремы, например, теорема Ферма помогают отсеять множество псевдопростых чисел.
Тест на простоту
GeMir
08.05.2019 14:38это положительное целое число, которое делится только на 1 и само на себя
Если честно, никогда не слышал определения простого числа без упоминания «больше единицы».
IgorKh
Я не математик, но статью воспринял, как «число 1 формально соответствует определению простого числа, кроме того оно имеет еще ряд дополнительных интересных „свойств“».
Не знаю, как по мне, наличие каких-то дополнительных опций не повод исключать число из простых.
Это как сказать: смартфон — это не телефон, у него конечно есть опция разговора, но ведь он еще умеет фотографировать, а в классическом понимании у всех телефонов есть только опция разговора.
martin_wanderer
В поисках глубинных причин, мне кажется, автор забыл упомянуть одну сугубо практическую: если единицу не исключить из числа простых, то для нее придется делать исключение не только в основной теореме арифметики, но и во многих других местах, где простые числа используются
IgorKh
Складывается ощущение, что практическая причина, как раз единственная и есть
catsmile
Проще отрефакторить в одном месте, чем потом плодить if-ы в сотне методов. Логично.
orion_tvv
я бы сказал закостылить
Zenitchik
Наоборот. Исправление в одном месте — это более удобная абстракция. А исправления во многих местах — костыли.
Kib0rg
Соответствует или нет — зависит только от определения. Если в каких-то случаях (пример в статье про множества с бесконечным количеством обратимых элементов) удобнее считать простыми только необратимые элементы, а во всех остальных это не играет роли, то почему бы не использовать одинаковое определение везде? Собственно, я так понимаю, что современное определение простого числа как раз учитывает эту особенность и единица из множества простых исключается.
Ну да, можно сказать что причина практическая, но ведь в этом и есть суть определения — им должно быть удобно пользоваться.
IgorKh
Математика все-таки не субъективная наука, не округляем же мы Пи до 3.0 что бы удобнее пользоваться было. Потому мне собственно и не понравился подход.
Да я примерно понял все за и против в статье, но было бы неплохо все таки формализировать понятия и определения.
Kib0rg
Определения — это не что-то отлитое в граните, всякое определение кто-то однажды придумал для того, чтобы им воспользоваться. Здесь и возникает вопрос удобства. Если можно использовать другое определение без существенной потери смысла, но при этом новое определение удобнее — почему нет?
Пи — это просто обозначение (не определение), оно здесь ни при чём. Хотя и утверждение про «мы же не округляем» тоже неверно само по себе, потому что во многих случаях всё-таки округляем.
BigBeaver
oskolkov
BigBeaver
Ну в алгебре-то понятно, что ничего не округляют. Но такие равенства ведь не численно получены.
Cerberuser
"Для гренландского кита число Пи равно трём"?
5oclock
Кстати, насчёт биологии и пи…
Читал на просторах интернета:
(Приписывается этому товарищу: vk.com/kknop
типа копирайт соблюдён)
411
Никто не запрещает иметь определение множества, включающего и простые числа и 1, но на него не будут распространяться некоторые свойства множества простых чисел, а также будут распространяться некоторые другие.
В этом плане нет субъективности, названия определений придуманы людьми, математических противоречий они не создают.
masai
А разве нужны ещё какие-то причины? В математике очень многое делается просто для удобства и для консистентности рассуждений.
Если хочется с кем-то похоливарить, можно, например, вспомнить споры насчёт того, чему равно 0? при n=0. :) И таких примеров достаточно много.
Sirion
А в чём холивар? Это вполне явно запрещённая операция в стандартной аксиоматике действительных чисел.
masai
Процессоры с вами не согласны. :)
А вообще, потому в математике и не используют обычно, так как единственного удобного обобщения нет, как в случае, например, с возведением чисел в дробную степень.
Sirion
Вообще да, я сначала ляпнул не подумав, а потом задумался. Действительно, это не связано напрямую с аксиоматикой, скорее с разрывностью функции в этой точке.
ainoneko
Остаётся решить, к чему относится 0^0 (или запретить такое совсем).
Soffort
Насколько я знаю, раньше 0^0 считалось равным 1, но с недавних пор некоторые считают равным 0.
А вообще, это интересная тема:
https://ru.wikipedia.org/wiki/Ноль_в_нулевой_степени
Zenitchik
del.
Опередили
Zibx
Смартфоны как раз формально были телефонами, а вот то что сейчас на рынке — ранее именовалось комуникаторами.