3.8. Разложение на множители. Признаки делимости

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

$\dfrac{1092}{1638}$.

Спрашивается: можно ли ее сократить и, если можно, то как? Поиском ответа на подобного рода вопросы мы сейчас и займемся.

Простые и составные числа

До сих пор задачи на умножение для нас заключались в том, чтобы по двум или нескольким сомножителям найти их произведение. Теперь попробуем решить обратную задачу. Нам дано какое-то натуральное число, и от нас требуется разбить его на множители, то есть подобрать такой пример на умножение с натуральными числами, результатом которого как раз является данное число. Вообще говоря, эта задача может иметь несколько решений. Например, число $30$ можно разбить на множители следующими пятью способами:

$\begin{align} &30 = 1 \cdot 30;\\ &30 = 2 \cdot 15;\\ &30 = 3 \cdot 10;\\ &30 = 5 \cdot 6;\\ &30 = 2 \cdot 3 \cdot 5. \end{align}$

Вместе с тем, число $31$ разбивается на множители единственным способом:

$31 = 1 \cdot 31$.

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

$\begin{align} &31 = 1 \cdot 31;\\ &31 = 31 \cdot 1;\\ &31 = 1 \cdot 31 \cdot 1. \end{align}$

Говорят, что натуральное число $k$ кратно натуральному числу $d$, если $k$ можно разбить на множители таким образом:

$k = n \cdot d$,

где $n$ — тоже какое-то натуральное число. При этом число $d$ называется делителем числа $k$.

Например, число $30$ кратно каждому из восьми своих делителей: $1$, $2$, $3$, $5$, $6$, $10$, $15$ и $30$, в то время как число $31$ кратно только двум числам: $1$ и $31$.

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

Давайте выпишем первые несколько натуральных чисел и посмотрим, какие из них простые, а какие составные:

$1$ — не является ни простым, ни составным, потому что у него только один делитель;

$2$ — простое;

$3$ — простое;

$4 = 2 \cdot 2$ — составное;

$5$ — простое;

$6 = 2 \cdot 3$ — составное;

$7$ — простое;

$8 = 2 \cdot 2 \cdot 2$ — составное;

$9 = 3 \cdot 3$ — составное;

$10 = 2 \cdot 5$ — составное;

$11$ — простое;

$12 = 2 \cdot 2 \cdot 3$ — составное;

$13$ — простое.

Процедура разложения на простые множители

Напомню, что мы начали эту главу с задачи о том, как можно сократить дробь

$\dfrac{1092}{1638}$.

Мы уже на полпути к ответу. Давайте разложим на простые множители числитель и знаменатель этой дроби и выясним, что из этого получится. Прежде всего рассмотрим числитель, то есть число $1092$. Попытаемся найти какой-либо его делитель. Для этого будем брать все числа подряд и проверять, не подойдут ли они в качестве делителя. Начнем с двойки. Просто поделим наше число на $2$:

$\dfrac{1092} {2} = 546$.

В результате получилось целое число. Значит, двойка действительно является делителем, и мы можем разложить наше число на множители в таком виде:

$1092 = 2 \cdot 546$.

Возьмем второй сомножитель в этом выражении и проверим его на делимость на двойку:

$\dfrac{546} {2} = 273$.

Результатом снова оказалось целое число. Разложение на множители можно продолжить следующим образом:

$1092 = 2 \cdot 2 \cdot 273$.

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

$\dfrac{273} {2} = 136\dfrac{1}{2}$.

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

$\dfrac{273} {3} = 91$.

Тройка подошла. Значит, мы можем записать так:

$1092 = 2 \cdot 2 \cdot 3 \cdot 91$.

Проверяем тройку повторно:

$\dfrac{91}{3} = 30\dfrac{1}{3}$.

Тройка больше не подходит. Берем четверку? Нет, четверку проверять не нужно. Четверка — это составное число, в «состав» которого входят две двойки:

$4 = 2 \cdot 2$.

Мы уже знаем, что число $91$ на двойку не делится. Следовательно на число ${2 \cdot 2}$ оно не делится и подавно. По аналогичной причине, нам вообще не нужно проверять делимость на какие-либо составные числа. Пропускаем четверку и устраиваем проверку следующему простому числу, то есть пятерке:

$\dfrac{91}{5} = 18\dfrac{1}{5}$.

Пятерка не подошла. Шестерку, как составное число, пропускаем. Следующий «кандидат» в делители — это семерка:

$91 / 7 = 13$.

Семерка подходит. Разложение на множители принимает вид:

$1092 = 2 \cdot 2 \cdot 3 \cdot 7 \cdot 13$.

Надо ли нам теперь проверять последний множитель ($13$) на делимость на $7$? Нет, не надо. Это не надо делать по той причине, что $13$ меньше, чем $7 \cdot 7$:

$13 < 7 \cdot 7 = 49$.

Все числа, которые меньше, чем $49$, и которые при этом делятся на $7$, можно записать в виде ${n \cdot 7}$, где $n$ — какое-то натуральное число, которое должно быть меньше, чем $7$. Но все такие числа мы уже проверили и выяснили, что на роль делителей они не подходят. Значит, число $13$, будучи меньше, чем $49$, не может делиться на семерку. По этой же причине нет смысла проверять, делится ли $13$ на числа, которые больше $7$. Отсюда мы заключаем, что $13$ — простое число. И действительно, в списке чисел, который мы выписали выше, оно значится как простое. Вообще, процедуру разложения на множители следует прекращать тогда, когда «кандидат» в делители (в данном случае $7$), умноженный сам на себя (${7 \cdot 7}$), оказывается больше, чем последний (то есть самый большой) множитель разложения ($13$).

Итак, мы разложили числитель дроби

$\dfrac{1092}{1638}$

на простые множители:

$1092 = 2 \cdot 2 \cdot 3 \cdot 7 \cdot 13$.

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

$1638 = 2 \cdot 3 \cdot 3 \cdot 7 \cdot 13$.

Теперь, чтобы сократить дробь, достаточно просто вычеркнуть пары одинаковых чисел сверху и снизу:

$\require{cancel}\dfrac{1092}{1638} = \dfrac{2 \cdot 2 \cdot 3 \cdot 7 \cdot 13}{2 \cdot 3 \cdot 3 \cdot 7 \cdot 13} = \dfrac{\cancel{\,2\,} \cdot 2 \cdot \cancel{\,3\,} \cdot \cancel{\,7\,} \cdot \cancel{13}}{\cancel{\,2\,} \cdot \cancel{\,3\,} \cdot 3 \cdot \cancel{\,7\,} \cdot \cancel{13}} = \dfrac{\,2\,}{3}\,$.

Замечание. Мы заодно убедились в справедливости так называемой основной теоремы арифметики: всякое натуральное число, которое больше двух, можно единственным образом представить в виде произведения простых чисел. (При этом формально считается, что произведение может состоять всего из одного сомножителя. Именно такие «усеченные» произведения получаются, когда мы раскладываем на множители простые числа.)

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

$\dfrac{28}{45} = \dfrac{2 \cdot 2 \cdot 7}{3 \cdot 3 \cdot 5}$.

Признаки делимости

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

Мы уже знаем признак делимости на $10$. Этот признак можно сформулировать с помощью двух фраз:

(1) Всякое натуральное число, которое оканчивается цифрой $0$, делится на $10$.

(2) Всякое натуральное число, которое оканчивается любой другой цифрой, на $10$ не делится.

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

Натуральное число делится на $10$ тогда и только тогда, когда оно оканчивается нулем.

Отметим, что словосочетание «тогда и только тогда» несколько избыточно. Достаточно было бы сказать просто «только тогда». Но так уж у математиков принято выражаться, и мы не будем нарушать эту традицию. В то же время, когда мы говорим «число делится на $10$», то подразумеваем не просто «делится», а «делится нацело». Также заметим, что хотя мы формулируем признаки делимости для натуральных чисел, они с тем же успехом подходят и для целых чисел: если $a$ делится на $b$, то и $(-a)$ делится на b.

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

$5670 = 2 \cdot 5 \cdot 567$.

А если число оканчивается двумя нулями? Тогда будем писать так:

$56700 = 2 \cdot 2 \cdot 5 \cdot 5 \cdot 567$.

Признак делимости на $\textbf{2}$. Натуральное число делится на $2$ тогда и только тогда, когда его последняя цифра делится на $2$, то есть равна $0$, $2$, $4$, $6$ или $8$.

Целые числа, которые делятся на $2$, называются четными. Целые числа, которые не делятся на $2$, называются нечетными.

Признак делимости на $\textbf{5}$. Натуральное число делится на $5$ тогда и только тогда, когда его последняя цифра делится на $5$, то есть равна $0$ или $5$.

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

$a = n \cdot 10 + b$,

где $n$ — это число полных десятков в числе $a$ (то есть число $a$ с отброшенным последним знаком), а $b$ — однозначное число, выраженное последней цифрой числа $a$. После несложных преобразований получаем:

$a = 2n \cdot 5 + b = m \cdot 5 + b$,

где мы ввели новое обозначение, а именно ${m = 2n}$. Поскольку нас интересует делимость на $5$, поделим это равенство на $5$:

$a / 5 = m + b / 5$.

Отсюда видно, что число $a$ делится на $5$ тогда и только тогда, когда на $5$ делится число $b$. Прелесть этого утверждения заключается в том, что число $a$ может быть очень большим. Оно может состоять из очень многих цифр, и, вероятно, нам потребовалось бы весьма много времени, если бы мы в самом деле захотели поделить его на $5$. Но нам этого вовсе не нужно! Достаточно просто взглянуть на число $b$, которое настолько маленькое, что мы сразу же можем сказать, делится ли оно на $5$ или нет. По этой причине $b$ называется проверочным числом. В принципе, на роль проверочного подойдет любое достаточно малое число, которое можно записать в виде

$a - b = m \cdot 5$.

Здесь $a$ — по-прежнему произвольное натуральное число, делимость которого мы хотим установить, а ${m \cdot 5}$ обозначает просто некоторое число, делящееся на $5$.

Перейдем к обобщениям. Почти все признаки делимости, с которыми мы будем иметь дело, формулируются примерно одинаково: число $a$ делится на число $d$ тогда и только тогда, когда число $b$ делится на $d$. При этом проверочное число $b$ может быть легко получено из числа $a$, а чтобы доказать признак делимости, достаточно убедиться, что разность ${a - b}$ кратна $d$, то есть представима в виде ${m \cdot d}$ (где $m$, как и ранее, — некоторое натуральное число).

Признак делимости на $\textbf{3}$. Натуральное число делится на $3$ тогда и только тогда, когда сумма его цифр делится на $3$. Например, число $123$ делится на $3$, поскольку ${1 + 2 + 3 = 6}$ делится на $3$.

Действительно, представим произвольное натуральное число $a$ в виде:

$a = \ldots + v\cdot 10000 + w\cdot 1000 + x\cdot 100 + y\cdot 10 + z$,

где под буквами $v$, $w$, $x$, $y$, $z$ подразумеваются значения соответствующих разрядов числа $a$, а многоточие (${...}$) говорит о том, что вместо него могут присутствовать еще и другие слагаемые. Тогда проверочное число $b$ равно

$b = \ldots + v + w + x + y + z$.

Разность чисел $a$ и $b$ представима в виде:

$\begin{align} &a - b =\\ &\ldots + 9999\cdot v + 999\cdot w + 99\cdot x + 9\cdot y =\\ &3\cdot 3 \cdot(\,\,\ldots + 1111\cdot v + 111\cdot w + 11\cdot x + 1\cdot y). \end{align}$

Ясно, что эта разность кратна трем, что и доказывает данный признак делимости. Более того, эта разность кратна девяти. Поэтому отсюда же мы получаем —

признак делимости на $\textbf{9}$. Натуральное число делится на $9$ тогда и только тогда, когда сумма его цифр делится на $9$. Например, число $234$ делится на $9$, поскольку ${2 + 3 + 4 = 9}$ делится на $9$.

Признак делимости на $\textbf{7}$. Пусть $a$ — произвольное целое число, причем его последняя цифра равна $v$, а число, которое получается после отбрасывания последней цифры, равно $u$:

$a = u \cdot 10 + v$.

Число $a$ делится на $7$ тогда и только тогда, когда делится на $7$ число

$b = u - 2 \cdot v$.

Иными словами, проверочное число получается, если из проверяемого числа с отброшенной последней цифрой вычесть удвоенную последнюю цифру. Например, число $112$ делится на $7$, поскольку ${11 - 2\cdot 2 = 7}$ делится на $7$.

Для доказательства этого утверждения мы рассмотрим не разность ${a - b}$, а сумму ${2a + b}$. Мы как бы подменяем задачу и рассматриваем делимость не числа $a$, а числа ${2a}$, причем в качестве проверочного числа берем не $b$, а $(-b)$. Но такая подмена совершенно законна, потому что числа $a$ и $2a$ одновременно либо делятся на $7$, либо не делятся (в разложении того и другого на простые множители семерка либо присутствует, либо нет). То же самое можно сказать и про числа $b$ и $(-b)$. Для указанной суммы имеем:

$2\cdot a + b = 2 (u \cdot 10 + v) + (u - 2 \cdot v) =$

$= 20\cdot u + 2\cdot v + u - 2\cdot v = 21\cdot u = 3\cdot 7\cdot u$.

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

Признак делимости на $\textbf{11}$. Натуральное число делится на $11$ тогда и только тогда, когда сумма его цифр, взятых с чередующимися знаками, делится на $11$. Например, число $759$ делится на $11$, поскольку ${7 - 5 + 9 = 11}$ делится на $11$.

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

$\begin{align} &99 = 11 \cdot 9;\\ &1001 = 990 + 11 = 11 \cdot 90 + 11 = 11 \cdot 91;\\ &9999 = 11 \cdot 909;\\ &100001 = 99990 + 11 = 11 \cdot 9090 + 11 = 11 \cdot 9091;\\ &999999 = 11 \cdot 90909;\\ \end{align}$

и так далее.

Запишем, как мы это уже делали раньше, число $a$ в виде:

$a = \ldots + u\cdot 100000 + v\cdot 10000 + w\cdot 1000 + x\cdot 100 + y\cdot 10 + z$.

Тогда проверочное число равно

$b = \ldots - u + v - w + x - y + z$.

Вычитая $b$ из $a$, получаем:

$\begin{align*} &a - b =\\ &... +~u\cdot 100001 + v\cdot 9999 + w\cdot 1001 + x\cdot 99 + y\cdot 11 =\\ &11 \cdot (9091\cdot u + 909\cdot v + 91\cdot w + 9\cdot x + y). \end{align*}$

Для полноты картины приведем еще признаки делимости на $4$, на $6$ и на $8$. (Впрочем, поскольку это всё составные числа, практическая польза от этих признаков невелика.)

Признак делимости на $\textbf{4}$. Натуральное число делится на $4$ тогда и только тогда, когда две его последние цифры делятся на $4$.

Признак делимости на $\textbf{8}$. Натуральное число делится на $8$ тогда и только тогда, когда три его последние цифры делятся на $8$.

Признак делимости на $\textbf{6}$. Натуральное число делится на $6$ тогда и только тогда, когда оно делится на $2$ и на $3$.

Признак «неделимости»

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

Запись разложения на простые множители

Теперь у нас есть полный набор инструментов для разложения чисел на простые множители. При этом удобно пользоваться записью «в столбик», которую мы покажем на примере разложения числа $4340$:

$\begin{array}{r|l} 4340 & 2\cdot 5 \\ 434 & 2 \\ 217 & 7 \\ 31 &31 \end{array}$

Конспект

1. Натуральное число $k$ называется кратным натуральному числу $d$, если $k$ делится нацело на $d$, то есть если ${k = n \cdot d}$, где $n$ — тоже какое-то натуральное число. При этом число $d$ называется делителем числа $k$. Например, число $30$ имеет восемь делителей: $1$, $2$, $3$, $5$, $6$, $10$, $15$ и $30$. Число $31$ имеет только два делителя: $1$ и $31$.

2. Натуральное число, у которого есть в точности два различных делителя, называется простым. (При этом неизбежно оказывается, что один из делителей — это единица, а второй делитель равен самому этому числу.) Например, простым является число $31$. Натуральное число, у которых имеется больше двух делителей, называется составным. Таковым является, например, число $30$.

3. Чтобы сократить какую-либо дробь — например, ${1092 / 1638}$ — мы раскладываем ее числитель и знаменатель на простые множители, а затем вычеркиваем пары одинаковых чисел сверху и снизу:

$\dfrac{1092}{1638} = \dfrac{2 \cdot 2 \cdot 3 \cdot 7 \cdot 13}{2 \cdot 3 \cdot 3 \cdot 7 \cdot 13} = \dfrac{\cancel{\,2\,} \cdot 2 \cdot \cancel{\,3\,} \cdot \cancel{\,7\,} \cdot \cancel{13}}{\cancel{\,2\,} \cdot \cancel{\,3\,} \cdot 3 \cdot \cancel{\,7\,} \cdot \cancel{13}} = \dfrac{\,2\,}{3}\,$.

Не всякая дробь может быть сокращена, например,

$\dfrac{28}{45} = \dfrac{2 \cdot 2 \cdot 7}{3 \cdot 3 \cdot 5}$.

4. При разложении чисел на простые множители удобно пользоваться признаками делимости, которые формулируются следующим образом: $a$ делится на $d$ тогда и только тогда, когда $b$ делится на $d$. При этом $a$ может быть очень большим, а проверочное число $b$, легко вычисляемое по числу $a$, является, напротив, сравнительно маленьким. Чтобы доказать признак делимости, достаточно установить, что разность ${a - b}$ делится на $d$.

Проверочные числа $b$, используемые в признаках делимости числа a на число $d$

5. Целые числа, которые делятся на $2$, называются четными. Целые числа, которые не делятся на $2$, называются нечетными.

6. При разложении чисел на простые множители удобно пользоваться записью «в столбик», например:

$\begin{array}{r|l} 4340 & 2\cdot 5 \\ 434 & 2 \\ 217 & 7 \\ 31 &31 \end{array}$

Из «бесконечного» сборника типовых упражнений

Разложение на простые множители

Примеры на сокращение «большой» дроби