У султана было два визиря. Захотел он проверить, насколько они мудры. Позвал он их обоих и сказал: я загадал два целых числа от 2 до 100. Вы должны их мне назвать. При этом султан сообщил первому визирю произведение этих чисел, а второму — их сумму.

Первый визирь говорит:
– Я не знаю что это за числа
Второй отвечает:
– Я знал это.
Первый:
– В таком случае, я знаю, что это за числа.
Второй:
– Тогда и я знаю.
Какие числа загадал султан?

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

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

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

Если частное от деления а на b — целое, то, обозначив его буквой q, мы получим, что a=bq, то есть а есть произведение b на некоторое целое. В таком случае говорят, что а делится на b или что b делит а.

При этом а называют кратным числа b, а b — делителем числа а.

Сформулируем и докажем некоторые очевидные свойства:

Свойство №1

Если а кратно m, а m кратно b, то а кратно b.

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

Значит,

где

− целое

Что и завершает доказательство.

Если в равенстве k + l +...+ n = p + q +...+ s все слагаемые, кроме одного, кратны b, то и это оставшееся слагаемое кратно b.

Пусть таким слагаемым будет k.

Тогда

Именно этим свойством мы и воспользовались, когда доказывали, что число

будучи составным, тем не менее, не может делиться ни на одно из

в самом деле, если бы Q было кратно какому-то из

,

то, поскольку число

кратно любому из

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

.

числу

(по свойству 2)

Если а делит b и а делит с, то а делит b±c

Предлагаем читателям попробовать самостоятельно доказать это свойство.

В общем случае всякое целое а единственным способом представимо через положительное целое b в виде:

Число q в этом случае называется неполным частным, а r — остатком от деления а на b.

a = bq + r, 0 ≤ r < b.

Хотим обратить внимание читателей на то, что остаток r строго меньше! делителя b.

Этот факт будет очень часто использоваться в доказательствах свойств делимости в целых числах. Им же мы воспользуемся и сейчас.

( 1 )

Одно представление числа а в виде ( 1 ) мы получим, взяв в качестве bq наибольшее число, кратное b, и не превосходящее a.

Итак, докажем теорему.

Предположим, что оно не единственное. Значит, существуют такие

Но тогда

и

что

,

Помните, один из способов сказать о равенстве двух чисел — это сказать, что их разность равна нулю?

Откуда (опять-таки по свойству 2) следует, что

должно быть кратно b.

Но поскольку

(пользуемся тем, что оба остатка положительны, и оба строго меньше b), то это возможно, только если

или

.

Значит,

Следовательно (так как по условию b > 0), и

или

Последнее доказательство является очень характерным примером того, как вообще проводятся доказательства в теории чисел — настоятельно рекомендуем несколько раз проделать его самостоятельно, чтобы прочувствовать специфику рассуждений. Для многих она оказывается непривычной и оттого — сложной.

Важно

Заметим, что единица не является простым числом! Таким образом, самое маленькое простое число - это 2. Оно же является единственным четным простым.

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

В следующем видео мы начнем разговор о единственности еще одного представления любого целого числа а — на этот раз в виде произведения простых чисел, т. е. таких, которые делятся только на единицу и на самих себя.

то оно бы разделилось раньше,

Но поскольку обсуждаемый в видео прием факторизации (так называется разложение на простые множители) числа n состоит в последовательном переборе всех делителей от 1 до

то это действительно равносильно

Дальше делимость можно не проверять, так как если число n делится на какое-то число, большее

отысканию всех простых чисел (в данном случае — делителей n) в диапазоне от 1 до

поскольку его второй делитель будет всегда меньше

Упражнение:

выписать, используя решето Эратосфена, все простые числа до

Нажми на бежевые полосы, чтобы увидеть ответ

и разложить на простые множители путем перебора их простых делителей следующие числа:

Всякое целое, делящее одновременно целые числа a, b,...,l, называется их общим делителем.

Наибольший из общих делителей называется наибольшим общим делителем и обозначается ( a, b,...,l ). Если ( a, b,...,l ) = 1, то числа a, b,...,l называются взаимно простыми.

Если каждое из чисел a, b,...,l взаимно просто с каждым другим из них, то числа a, b,...,l называются попарно простыми.

Числа 6, 10, 15 — взаимно простые, поскольку ( 6, 10, 15 ) = 1.

Пример:

Числа же 8, 13, 21 уже будут и попарно простыми.

Но они не являются попарно простыми, так как ( 6, 10 ) = 2, а ( 10, 15 ) = 5.

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

Числа 6, 10, 15 — взаимно простые, поскольку
( 6, 10, 15 ) = 1. Но они не являются попарно простыми, так как ( 6, 10 ) = 2, а ( 10, 15 ) = 5.

Два следующих свойства НОД чрезвычайно важны.

Если а кратно b, то множество общих делителей чисел а и b, совпадает с множеством делителей одного b. В частности, (а, b)=b.

Доказательство. Любой общий делитель а и b делит b. Обратно, поскольку а кратно b, то любой делитель b, является также и делителем а. Поэтому совокупность делителей а и b совпадает с совокупностью делителей b.

Понятно также, что наибольшим делителем b будет само b. Поэтому (а, b)=b.

Если a = bq + с, то множество общих делителей а и b совпадает с множеством общих делителей b и с. В частности, ( а, b ) = ( b, с ).

Из записанного равенства следует, что любой общий делитель а и b делит и с (все то же Свойство 2 из предыдущей части), и поэтому является общим делителем b и c. С другой стороны, из того же равенства следует, что любой общий делитель b и с делит также и а.

То есть, множество общих делителей чисел а и b действительно совпадает с множеством общих делителей чисел b и с. В частности, должны совпадать и их наибольшие общие делители.

Для отыскания наибольшего общего делителя чисел а и b используется так называемый алгоритм Евклида, но о нем мы поговорим позже. Сейчас же смотрите завершение доказательства Основной Теоремы Арифметики.