§ 2.3. Теорема деления

В § 2.1 мы говорили о том, что всякому алгоритму соответствует теорема. Сформулируем теорему, отвечающую алгоритму деления.

Теорема деления. Пусть a и b — натуральные числа. Тогда существует единственная пара неотрицательных целых чисел таких, что

Теорема содержит два утверждения про числа Во-первых, они существуют, во-вторых, они единственны. Мы

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

Посмотрим, почему это правда. Пусть два натуральных числа, которые мы предложили разным людям, скажем, Карлу и Софии, и попросили их найти неполное частное и остаток, удовлетворяющие условиям, сформулированным в теореме. Результатом работы Карла являются числа а София нашла числа Нам известно только, что

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

С другой стороны, оба числа меньше По нашему предположению, откуда Однако поэтому

Число b положительно, так что на него можно разделить. Значит, Но число целое, поэтому последнее

неравенство выполняется в том и только в том случае, если Другими словами, откуда и единственность неполного частного и остатка доказана.

Подводя итог, мы доказали, что алгоритм деления приводит к теореме, состоящей из двух утверждений: неполное частное и остаток от деления двух натуральных чисел всегда существуют и они единственны. Многие из теорем, которые еще будут обсуждаться в нашей книге, также утверждают существование и единственность некоторых объектов. Наиболее важная из них — теорема о разложении на простые множители из главы 3.