Таблицы Брадиса

Но при этом задача о

Но при этом задача о

Элементы математики в задачах - Г. А. Мерзон

В первой части листка обсуждаются простейшие свойства дели­мости. Для их доказательства достаточно аккуратно расписать опре­деление: число а делится на число Ь, если и только если существует такое целое число к, что а = к ■ Ь. Этот несложный прием может по­мочь и при решении более сложных задач, так как дает возможность использовать весь арсенал средств работы с равенствами — можно прибавлять к обеим частям одно и то же число, умножать левую и правую часть на одно и то же число, и т. д. Отметим еще, что если

а. Ь, то обязательно Ь = 0, поэтому равенства можно сокращать на Ь всюду, где это необходимо.

Важно понимать, что в листке определяется отношение делимо­сти, но не операция деления: мы можем сказать, что некоторые числа делятся на другие, но нигде пока не было определено, что означает разделить одно число на другое (это будет сделано позже, в лист­ках «Поля» и «Рациональные числа»). Поэтому рассуждения в стиле «разделим 5 на 7 — получим число 5/7, которое не является целым; значит, 5 на 7 не делится» пока (до определения рациональных чисел) формально лишны смысла.

Во второй части листка впервые возникают простые числа и об­суждается разложение на простые множители (но доказательство единственности разложения отложено до следующего листка).

До последнего времени теория простых чисел являлась, в основ­ном, предметом глубоких исследований наиболее абстрактных обла­стей математики. Однако в последние десятилетия ряд значительных открытий в криптографии привел к тому, что такие задачи, как раз­ложение числа на простые множители, проверка простоты числа, по­строение больших простых чисел, играют важнейшую роль в обмене конфиденциальной информацией. Так, в 2004 году был создан доста­точно быстрый («полиномиальный») алгоритм проверки простоты числа. Но при этом задача о разложении числа на простые множители на сегодняшний день еще далека от эффективного решения. Одна из