16. Делимость. Представления чисел. Профильный уровень

Что такое алгебра целых чисел

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

Но есть задачи, где нужно остановиться на натуральных или целых числах.

Мы знаем, что разделить 11 человек на две равные по количеству людей команды не получится (см. рис. 1).

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

Такого рода задачи решаются алгеброй целых чисел. Чаще её называют теорией чисел.

Теория кодирования, приближённые вычисления, даже биология и другие дисциплины используют теорию целых чисел. Даже в «обычной» алгебре, когда мы приводим две дроби к общему знаменателю (то есть работаем никак не с целыми числами), мы ищем общее кратное двух целых чисел ― знаменателей:

;

.

А это уже и есть теория целых чисел.

Делимость. Простые числа. Основная теорема арифметики

Итак, первая задача теории чисел, о которой мы поговорим, ― делимость.

Группу из 30 детей можно разбить на 5 равных по численности спортивных команд, а из 29 или 32 нельзя (см. рис. 2).

Иначе говоря, 30 делится нацело на 5, а 29 или 32 нет.

Пусть есть два целых числа и . (В дальнейшем в течение этого урока мы всегда будем подразумевать, что речь идёт о целых числах.)

Число делится на число , если существует такое целое число , что : , где .

Не нужно путать термины «делить» и «делиться». Когда мы говорим «30 делить на 5» или «40 делить на 5», то нам нужен результат деления ― 6 или 8:

;

.

С этой точки зрения числа 30 и 40 различаются: они дают разные результаты при делении на 5.

А когда мы говорим «30 делится на 5» или «40 делится на 5», нас интересует только сама возможность разделить:

;

.

С этой точки зрения 30 и 40 не отличаются друг от друга: они оба делятся на 5.

Если делится на , то a называют кратным числа , а ― делителем числа :, где ― кратное числа ; ― делитель числа .

30 делится на 5, поэтому 30 ― кратное 5, а 5 ― делитель 30:, где 30 ― кратное 5; 5 ― делитель 30.

Пример использования делимости

Один из алгоритмов современного шифрования основан на делимости.

Он основан на следующем математическом факте: если взять два больших простых числа и и перемножить их, получится некое число . Оказывается, что подобрать это разложение на множители числа A (не зная или ) очень сложно и даже компьютерные алгоритмы не позволяют сделать этого за достаточно быстрое время.

Тогда, если ― зашифрованное число, то, умножив его на , получим число . Его можно передавать, не пряча от потенциального мошенника или шпиона. Он всё равно не сможет за относительно небольшое время, не зная ключа , отгадать . А получатель, обладая ключом, сделает это очень быстро (см. рис. 3).

Конечно, описана только идея, её конкретные реализации гораздо сложнее. Но это хороший пример того, как математические инструменты помогают решать практические задачи.

Единица имеет единственный делитель ― единицу, зато любое целое число будет её кратным:

;

.

Любое число, большее единицы, точно имеет два различных делителя ― единицу и само себя:

;

.

Может так оказаться, что больше делителей у него и нет. Например, число 7 делится только на 1 и на 7. Такие числа называют простыми: ― простое число.

У числа 15, кроме 1 и 15, есть ещё делители ― 3 и 5. Такие числа называются составными: ― составное число.

Понятно, что составных чисел бесконечное количество. Например, все чётные числа, начиная с 4, являются составными, так как имеют делитель, отличный от 1 и себя, ― 2:

;

.

При этом сама 2 является простым числом, единственным простым чётным числом.

Простых чисел тоже бесконечное количество, хотя это и не такой очевидный факт (см. рис. 4).

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

Доказательства этого факта были известны ещё в древности. Первое, известное на данный момент, было приведено у Евклида в III веке до н. э.

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

Бесконечность количества простых чисел

Приведём доказательство методом от противного.

Пусть простых чисел конечное число:

.

Рассмотрим произведение этих чисел и прибавим к нему 1:

.

Полученное число, очевидно, не делится ни на одно из этих простых чисел (иначе  тоже должна делиться на это простое число, но у 1 нет делителей, кроме 1). Но тогда у числа нет ни одного простого делителя, то есть нет делителей, кроме 1 и самого :

.

Таким образом, ― тоже простое число.

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

Если число является составным, то его можно представить в виде произведения: , где , .

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

Этот процесс можно продолжить. Понятно, что он будет конечным, так как все эти числа меньше и с каждым шагом уменьшаются:

.

В итоге мы получим произведение , где все множители простые.

Такое представление называется разложением числа a на простые множители.

Число 420 можно представить в виде произведения:

.

42 и 10 ― тоже составные числа, продолжаем процесс:

.

Мы получили разложение на простые множители.

Из примера видно, что множители могут повторяться. Понятно также, что если множители переставлять местами, то их произведение не изменится.

Тогда разложение можно записать от меньшего множителя к большему с использованием степени:

.

Такую запись называют канонической и используют чаще всего.

Понятно, что число 420 можно было начать раскладывать иначе:

.

Мы получили тот же самый результат. И это неслучайно.

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

Общие делители. Алгоритм Евклида

Предположим, что мы разложили числа на простые множители. Теперь можно посмотреть, что общего может быть у чисел ― какие из их множителей одинаковы. То есть можно искать общие делители. Если взять все общие делители нескольких чисел, то их произведение ― это уже известный нам наибольший общий делитель (НОД).

Рассмотрим числа 30 и 40.

 и , где 5 ― делитель и 30, и 40.

То есть 5 ― общий делитель 30 и 40. При этом 5 не наибольший общий делитель, так как 30 и 40 делятся одновременно на 10:

.

и .

Следовательно, 30 ― кратное 5 и 6, то есть 30 ― общее кратное 5 и 6. При этом кратных у двух чисел бесконечно много, например любое число, кратное 30, будет кратным одновременно 5 и 6:

.

Если нам удалось найти самое меньшее из кратных нескольких чисел, то это будет уже известное нам наименьшее общее кратное ():

.

Очевидно, что двух чисел не может быть больше, чем их произведение.

У двух чисел всегда есть общий делитель ― единица.

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

Почему важен именно наибольший делитель? Всё дело в том, что если мы знаем наибольший общий делитель, то мы уже знаем и все остальные делители.

Например, числа 1050 и 462 имеют несколько общих делителей: 2, 3, 14 и несколько ещё (см. рис. 5).

Наибольший общий делитель ― 42. Для этого мы используем такую запись:

.

И он содержит в качестве множителей все остальные делители ― и 2, и 3, и 14, а также и другие ― 6, 7, 21, 42:

.

Евклид в III веке до н. э. описал алгоритм отыскания наибольшего общего делителя. Интересно, что сегодня его продолжают использовать, например, в криптографии или для доказательств различных теорем в алгебре.

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

Рассмотрим алгоритм Евклида на приведённом ранее примере. Найдём .

Разделим 1050 на 462 с остатком:

;

;

;

.

Таким образом, .

Такая строчечная запись удобна для объяснения, как работает алгоритм, или для вычисления НОД с калькулятором в руках. Если калькулятора нет, то удобнее всего использовать деление уголком (см. рис. 6).

Сначала делим 1050 на 462 с остатком. Получаем в остатке 126.

Перед этим остатком приписываем 462 и уже делим 462 на 126. Получаем в остатке 84.

Приписываем впереди 126. Делим. Остаток ― 42.

Приписываем впереди 84. Остаток ― ноль.

НОД ― последний ненулевой остаток, то есть 42.

В ответвлении вы можете посмотреть обоснование алгоритма Евклида.

Доказательство алгоритма Евклида

Итак, разберёмся, почему же алгоритм Евклида работает.

1. Сначала рассмотрим простой факт:

Если ― общий делитель и (необязательно наибольший), то ― общий делитель суммы и разности этих чисел.

В самом деле

,

.

Тогда

,

.

2. Это же относится и к наибольшему общему делителю, то есть

.

В самом деле пусть . Тогда и делятся на , а значит, тоже делится на. То есть ― общий делитель и .

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

3. Итак, если в паре чисел одно заменить на их разность, то НОД не изменится. Но ведь так можно сделать несколько раз.

А следовательно, заменить одно число на остаток от деления большего на меньшее.

Если , то .

Тогда .

Пусть теперь .

Тогда .

Продолжая этот процесс, мы дойдём до ситуации, когда один остаток поделится на следующий. Но если одно число делится на другое, то меньшее является их НОДом.

Таким образом, становится понятно, как работает алгоритм. Мы в паре чисел заменяем большее число на остаток от деления, который, конечно, меньше обоих чисел, не меняя при этом НОДа. И доводим до того момента, когда одно число становится делителем другого. Оно и будет искомым НОДом.

Два составных числа могут не иметь общих делителей. Например, 8 и 15 имеют делители, кроме единицы, но общих нет:

;

.

Такие числа называют взаимнопростыми.

Понятно, что единица ― это их единственный общий делитель, он же наибольший:

.

То есть равенство  и есть определение взаимно простых чисел и :  и ― взаимно простые.

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

Цепные дроби

Алгоритм Евклида связан ещё с одним интересным объектом теории чисел ― с цепными дробями.

Рассмотрим дробь .

Проведём с ней следующую процедуру:

.

Как только мы получили дробь с числителем единица, то процедура закончена. Дальше переворачивать нет смысла.

Полученный объект называется цепной дробью.

Возможно, вы уже заметили, что мы использовали здесь алгоритм Евклида (рис. 7).

Все неполные частные из алгоритма и есть коэффициенты цепной дроби.

Чтобы запись была более линейна, цепную дробь часто записывают так:

.

Поскольку алгоритм Евклида конечен, то любая дробь (рациональное число) представимо в виде конечной цепной дроби: , где ― это целая часть дроби, она может быть равна нулю. Остальные коэффициенты нулю не равны.

Разложим ещё одну дробь в цепную ―.

Эта дробь правильная, целая часть, то есть первый коэффициент, равна нулю. Остальные найдём по алгоритму Евклида (см. рис. 8).

Получаем .

Проверим себя:

.

Главное (но далеко не единственное) назначение цепных дробей состоит в том, что они позволяют находить хорошие приближения вещественных чисел в виде обычных дробей.

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

q-ичные системы счисления

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

Сначала достаточно символов I, V, X, потом появляются L, C, D, M. Для ещё больших чисел используются более странные и, на наш взгляд, неудобные символы (см. рис. 9).

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

Но развитие науки потребовало работы с большими числами. Нужно было придумать удобную и эффективную систему записи чисел, которая смогла бы обойтись конечным числом знаков для записи (цифр), а также позволила бы быстро и эффективно выполнять действия с числами. Такую систему удалось придумать ― сейчас мы используем десятичную позиционную систему, в которой любое число записывается с помощью 10 цифр. А для действия с числами есть эффективные алгоритмы вычислений в столбик.

Привычная нам десятичная система счисления представляет собой частный случай так называемых позиционных систем счисления.

Почему система позиционная?

Потому что значение, приписываемое цифре, входящей в запись, зависит от позиции (разряда), на которой оно находится.

Вот три числа, состоящих из одного и того же набора цифр:

11115;

11151;

11511.

В первом случае цифра пять означает число 5, во втором ― 50, в третьем ― 500.

В общем виде число в десятичной записи имеет вид: , где с разными индексами ― это цифры от 0 до 9.

Это короткая запись следующего выражения:

.

Например, .

Число 10 здесь называется основанием системы счисления. Исторически выбор такого основания, скорее всего, связан с использованием пальцев на руках для счёта.

Но выбор 10 в качестве основания совершенно необязателен. В качестве основания можно выбрать любое натуральное число, начиная с двух. Название системы будет образовываться от этого числа. Например, двоичная система, 8-ричная, 10-тичная.

Число цифр будет равно основанию ― в десятичной системе 10 цифр (от нуля до девяти), в восьмеричной ― 8 (от нуля до 7), в двоичной ― две (ноль и один).

Выбор основания определяется задачей, которую мы решаем.

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

Если записи идут в разных системах счисления, то в конце числа пишут индекс ― основание системы счисления, например: ,.

Это два разных числа, хотя имеют одинаковую позиционную запись:

;

.

Понятно, чем меньше основание, тем больше визуально получается запись числа.

Запишем  в двоичной записи.

Вспомним степени двойки: 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048 (см. рис. 10).

Поделим с остатком 1323 на максимально возможную степень:

.

Дальше то же самое сделаем с остатком 299:

Осталось записать разложение точно так же, как десятичной записи, отсутствующие разряды заполнив нулями:

.

Для бытового использования такая запись, конечно, будет неудобной, уж слишком длинной получается запись даже достаточно небольших чисел. Зато она очень хорошо согласуется с шифрованием электронными сигналами: есть заряд ― единица, нет ― ноль. Именно поэтому двоичная система используется в компьютерных технологиях.

Есть другая крайность. В древнем Вавилоне люди использовали 60-ричную систему счисления. Конечно, числа записываются сравнительно коротко, но нужно использовать 60 различных цифр. Вот так выглядел этот набор (см. рис. 11).

А чтобы выучить таблицу умножения в том виде, как это делаем мы, нужно было бы запомнить 60 на 60 = 3600 значений.

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

Час у нас делится на 60 минут, а минута на 60 секунд.

Измерение времени и углов в астрономии ― это связанные вещи. Поэтому при измерении углов в градусах мы тоже используем 60-ричную систему, но, конечно, только её элементы, а не в полной мере.

Так, запись в градусах, минутах и секундах означает следующее:

.

Список литературы

1. Алгебра и начала математического анализа: базовый и углублённый уровни: учеб. для 10–11 кл. / Ш. А. Алимов, Ю. М. Колягин, М. В. Ткачёва и др. ― М.: Просвещение, 2017–2019.

2. Алгебра и начала математического анализа: базовый и профильный уровни: учеб. для 10 кл. / С. М. Никольский, М. К. Потапов, Н. Н. Решетников и др. ― М.: Просвещение, 2021.

Дополнительные рекомендованные ссылки на интернет-ресурсы

1. Интернет-портал kvant.mccme.ru (Источник, Источник)

Домашнее задание

1. Разложите на простые множители число 6345.

2. Используя алгоритм Евклида, найдите НОД чисел 258 и 1935.

3. Запишите число  в виде цепной дроби. Укажите краткую форму записи полученной цепной дроби.

4. Переведите число  в двоичную систему счисления.