У султана было два визиря. Захотел он проверить, насколько они мудры. Позвал он их обоих и сказал: я загадал два целых числа от 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 используется так называемый алгоритм Евклида, но о нем мы поговорим позже. Сейчас же смотрите завершение доказательства Основной Теоремы Арифметики.

Каковы бы ни были два целых числа а и b, всегда найдутся такие два целых числа x и y, что ax + by = ( a, b ). В частности, если а и b взаимно просты, то найдутся такие х и y, что ax + by = 1.

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

Наибольший общий делитель чисел 15 и 69 равен трем.

( 15, 69 ) = 3.

Легко убедиться, что 69 х 2 − 15 х 9 = 3.

НОД ( 12, 30 ) = 6.

Соотношение Безу имеет вид: 12 × 3 − 30 × 1 = 6.

Это представление не единственно. Возможен и другой вариант.

Например, такой: 30 × 1 − 12 × 2 = 6.

Если числа а и b не являются взаимно простыми, то их, вообще говоря, можно было бы сократить на ( a, b ) и получить новое соотношение для чисел

В частности, в нашем первом примере мы могли бы сократить числа 15 и 69 на 3, и получить пару взаимно простых чисел 5 и 23, для которых выполнялось бы соотношение 23 × 2 − 5 × 9 = 1.

которые уже будут взаимно просты:

и

Вообще, соотношение Безу лежит в основе критерия существования целочисленных решений у уравнения вида ax + by = с

Уравнения, решения которых отыскиваются только в целых числах, называются диофантовыми

Итак:

Действительно, если ( a, b ) не делит с, то число, стоящее в левой части уравнения, будет делиться на ( a, b ), а число, стоящее справа — нет.

Это же соотношение может быть использовано и для нахождения частного решения уравнения данного вида, поскольку зачастую решение ( u, v ) уравнения au + bv = 1 подобрать проще.

И тогда решение исходного уравнения

Действительно, поскольку

то

,

.

То есть,

или

А это, в свою очередь, означает, что

имеет вид 5k, где k- любое целое число.

И аналогично

имеет вид 7k.

В результате решениями нашего уравнения будут все такие пары х и y,

a

В частности, при k= − 11 мы получим решение

попроще: 2 и − 1.

что

Во-первых, заметим, что остатки от деления на 7, 8 и 9 не могут быть больше 6, 7 и 8, соответственно. Значит, чтобы остатки в сумме давали 21, они в каждом случае должны быть максимальными.

У Ани есть любимое число. Когда Аня поделила его на 7, 8 и 9, то сумма трёх остатков оказалась равной 21.

Решение:

Тогда любимое число Ани имеет вид:

Воспользуемся сначала первым и вторым соотношениями:

Теперь подставим выражение для k в первое соотношение и приравняем его с третьим:
7 ( 8n + 7 ) + 6 = 9m + 8. Или 9m − 56n = 47.

Опять-таки, одним решением будет
m = 1 и n = − 1, что приводит нас к соотношению:
9 ( m − 1 ) = 56 ( n + 1 ), т. е. m − 1 имеет вид 56p,
или m = 56p + 1 при любом целом р.

В результате имеем
N = 9 ( 56p + 1 ) + 8 = 504p + 17.

Можно также заметить, что, поскольку последняя формула есть, вообще говоря вид Аниного числа при делении с остатком на 9, то остаток 17 можно было бы уменьшить на кратное 9 число. И получить 8, или даже − 1. Другими словами, N = 504p − 1, и при наименьшем положительном p = 1

Докажите, что любимое число Ани больше 500.

Вообще говоря, у этой задачи существует и более элегантное решение.

Поскольку остатки от деления числа N на 7, 8 и 9 максимальны, следовательно, при прибавлении к нему единицы оно разделится нацело на 7, на 8 и на 9. А это означает, что N должно делиться на наименьшее общее кратное чисел 7, 8 и 9. Но поскольку эти числа попарно взаимно просты, то их наименьшее общее кратное равно их произведению. То есть N + 1 делится на 7 × 8 × 9 = 504, следовательно N = 503k.

В этом варианте решения мы воспользовались незнакомым для нас еще объектом — наименьшим общим кратным чисел а и b, а также важной теоремой, которую мы сформулируем и докажем в самом конце.

N = 503.

следовательно

Соотношение Безу гарантирует нам существование целочисленных решений этого диофантова уравнения. Одним таким решением будет пара чисел:

Остальные k, как видно из прошлого примера, будут иметь вид k = 8n + 7.

и

В общей теории, когда речь уже необязательно идет о числах, этот вариант Леммы по сути используется как определение простого элемента! Элемент а кольца R* а называют простым, если из того, что он делит bc, следует, что он либо делит b, либо с.

*кольцо — множество элементов, с определенными на нем операциями сложения и умножения

Вот насколько мощным орудием является эта Лемма. Не говоря уже о том, что из нее почти немедленно следует ОТА.

Заметим, что данное утверждение может оказаться неверным в случае, когда р не является простым числом. Например, р = 10 не делит числа 4 и 15, но делит их произведение 4 х 15 = 60. Именно это наблюдение и позволяет использовать Лемму в качестве критерия простоты элемента.

Важно:

Если какое-нибудь число мы разложили на простые множители, то эти множители мы можем располагать в каком угодно порядке, например в порядке возрастания.

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

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

На то, что невозможность двух существенно различных разложений одного и того же числа на простые множители вовсе не очевидна и нуждается в доказательстве, первым обратил внимание К. Ф. Гаусс, он же первым сформулировал это утверждение и доказал его в 1801 году.

В связи с этим у нас вопрос к читателям.

В одном из видео Наташа предположила, что мы воспользовались ОТА, когда воспроизводили доказательство Евклида о бесконечном множестве простых чисел. Я высказал сомнение.

Ссылается ли доказательство Евклида на ОТА? Если да, то на какую ее часть: на существование разложения на простые множители или на его единственность?

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

Всякое целое число, кратное всем данным числам a, b,..., l, называется их общим кратным. Наименьшее положительное общее кратное называется наименьшим общим кратным и обозначается как [a, b,..., l]

Теорема о наименьшем общем кратном:

Пусть М — какое-либо общее кратное чисел а и b, причем (а, b) = d. Так как М кратно а, то M = ak, где k — целое.

Сокращая на d, получаем, что

— целое.

Но

следовательно, k должно делиться на

т. е.

где t — целое.

Отсюда

Но М кратно и b, поэтому

— тоже должно быть целым.

Очевидно, что наименьшее положительное из этих кратных, т. е. наименьшее общее кратное мы получим при t = 1.

Следствие:

Или

Значит,

Значит с = [a, b] × t, и, следовательно, [a, b] делит с.

Если a делит с и b делит с, то [a, b] делит с. Действительно, по условию с является общим кратным а и b.

Теперь, пусть нам даны числа а и b. По основной теореме арифметики оба эти числа единственным образом представимы в виде произведения простых.

И пусть

— это все простые числа, участвующие в разложении а и b.

Тогда оба числа мы можем записать в виде:

То есть, какие-то простые числа могут входить по нескольку раз в разложение одного числа (в этом случае степень, в которой простое число

входит в разложение, будет больше 1), или вовсе не входить в разложение второго — в таком случае степень просто будет нулевой. Если теперь мы обозначим через

а

то

Если кого-то пугает этот формализм (хотя здесь он выглядит необычайно изящно), то на словах это равносильно следующему:

НОД чисел а и b — это произведение тех простых сомножителей, которые входят в разложение обоих чисел;

НОК чисел а и b — это произведение тех простых сомножителей, которые входят в разложение хотя бы одного из этих чисел.

Пример:

a=2200, b=76230

Простые числа, входящие в разложение а и b: 2, 3, 5, 7, 11

Если бы такое представление чисел не было единственным, то мы бы имели несколько «наибольших» общих делителей и «наименьших» общих кратных — что абсурдно.

Важно

x + 1

x, y

010100