Иногда мы совершаем какие-то математические действия как что-то очевидное.
Например, приведём дробь 8/12 к несократимой.
Алгоритм такой:
1) Разложим 8 на простые множители: 8 = 2⋅2⋅2.
2) Проделаем то же со знаменателем: 12 = 2⋅2⋅3.
3) Возьмём общую часть: 2⋅2 и сократим на неё:
8/12 = (2⋅2⋅2)/(2⋅2⋅3) = 2/3.
Подключаются дотошные математики
Казалось бы, всё логично. Но дотошные математики всегда сомневаются: а почему мы решили, что это единственно верный вариант? Может быть, можно разложить 8 и 12 на простые множители по-другому, получится другая общая часть и в результате сокращения выйдет не 2/3, а например, 1/2?
Как ни крути, разложить 8 и 12 по-другому нельзя. Но что насчёт чисел побольше? Можно брать их, пробовать и убеждаться, что разложение на простые множители всегда единственно (только порядок множителей может быть разный, это ок).
Но проверить все числа мы не можем. Остаётся вопрос: если взять какие-то огромные числа — там точно получится так же?
Основная теорема арифметики
И пока математики размышляют над такими вещами, они убеждаются, что:
любое натуральное число больше 1 можно представить в виде произведения простых чисел единственным образом (с точностью до перестановки). Это значит, что разложения 8 = 2⋅2⋅2, 12 = 2⋅2⋅3 — единственные. Никаких других простых множителей в разложении быть не может, но и убрать из записи какой-то множитель нельзя.
Теорема называется основной теоремой арифметики. Её сформулировал Евклид ещё в 3 веке до н.э. Она как будто простая и логичная, но, повторимся, математики такое доказывают — чтобы не просто верить, а знать, что всё, что мы делаем в арифметике, правильно всегда, то есть в общем случае.
Когда появилась
Эта теорема занимала умы математиков две тысячи лет: похожие формулировки встречаются ещё в «Началах» Евклида, потом у многих других математиков, но полное строгое доказательство привёл Гаусс лишь в начале 19 века.
Зачем это надо
Основная теорема арифметики даёт нам право делать разные действия и приходить к единственному результату, например:
• сокращать дроби;
• выносить множитель за скобки;
• находить делители числа;
• находить наибольший общий делитель чисел;
• находить наименьшее общее кратное.
А ещё не ломается криптография
Криптография прям держится на основной теореме арифметики!
Вся история с шифрованием с открытым ключом построена на поиске простых множителей числа. Если бы это разложение числа на простые множители было не единственным, то закодировать что-то мы бы могли, а вот однозначно расшифровать — нет.
Спасибо математикам за их дотошность и наши защищённые данные! ☺️
Подробнее о работе криптографических ключей смотрите в посте.