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

Разложение на множители. Признаки делимости
Рассмотрим дробь
1092 / 1638.
Спрашивается: можно ли ее сократить и, если можно, то как? Поиском ответа на подобного рода вопросы мы сейчас и займемся.
Простые и составные числа
До сих пор задачи на умножение для нас заключались в том, чтобы по двум или нескольким сомножителям найти их произведение. Теперь попробуем решить обратную задачу. Нам дано какое-то натуральное число, и от нас требуется разбить его на множители, то есть подобрать такой пример на умножение с натуральными числами, результатом которого как раз является данное число. Вообще говоря, эта задача может иметь несколько решений. Например, число 30 можно разбить на множители следующими пятью способами:
30 = 1 ∙ 30;
30 = 2 ∙ 15;
30 = 3 ∙ 10;
30 = 5 ∙ 6;
30 = 2 ∙ 3 ∙ 5.
Вместе с тем, число 31 разбивается на множители единственным способом:
31 = 1 ∙ 31.
(Можно еще менять сомножители местами, но мы условимся считать, что это не прибавляет новых способов. Также не добавляет новых способов умножение на единицу. Смысл следующих записей является для нас совершенно одинаковым:
31 = 1 ∙ 31;
31 = 31 ∙ 1;
31 = 1 ∙ 31 ∙ 1.)
Говорят, что натуральное число k кратно натуральному числу d, если k можно разбить на множители таким образом:
k = n ∙ d,
где n — тоже какое-то натуральное число. При этом число d называетсяделителем числа k.
Например, число 30 кратно каждому из восьми своих делителей: 1, 2, 3, 5, 6, 10, 15 и 30, в то время как число 31 кратно только двум числам: 1 и 31.
Натуральное число, у которого есть в точности два различных делителя, называется простым. (При этом неизбежно оказывается, что один из делителей — это единица, а второй делитель равен самому этому числу.) Например, простым является число 31. Что касается натуральных чисел, у которых имеется больше двух делителей, то они называются составными. Число 30 — это типичное составное число.
Давайте выпишем первые несколько натуральных чисел и посмотрим, какие из них простые, а какие составные:
1 — не является ни простым, ни составным, потому что у него только один делитель;
2 — простое;
3 — простое;
4 = 2 ∙ 2 — составное;
5 — простое;
6 = 2 ∙ 3 — составное;
7 — простое;
8 = 2 ∙ 2 ∙ 2 — составное;
9 = 3 ∙ 3 — составное;
10 = 2 ∙ 5 — составное;
11 — простое;
12 = 2 ∙ 2 ∙ 3 — составное;
13 — простое.
Процедура разложения на простые множители
Напомню, что мы начали эту главу с задачи о том, как можно сократить дробь
1092 / 1638.
Мы уже на полпути к ответу. Давайте разложим на множители числитель и знаменатель этой дроби и выясним, что из этого получится. Прежде всего рассмотрим числитель, то есть число 1092. Попытаемся найти какой-либо его делитель. Для этого будем брать все числа подряд и проверять, не подойдут ли они в качестве делителя. Начнем с двойки. Просто поделим наше число на 2:
1092 / 2 = 546.
В результате получилось целое число. Значит, двойка действительно является делителем и мы можем разложить наше число на множители в таком виде:
1092 = 2 ∙ 546.
Возьмем второй сомножитель в этом выражении и проверим его на делимость на двойку:
546 / 2 = 273.
Результатом снова оказалось целое число. Разложение на множители можно продолжить следующим образом:
1092 = 2 ∙ 2 ∙ 273.
Далее, опять — берем из полученного выражения последний сомножитель и выясняем, не кратен ли он двойке:
273 / 2 = 136¹/₂.
На этот раз мы не получили целого числа. Следовательно, на этот раз на роль очередного делителя двойка не подходит. Пробуем тройку:
273 / 3 = 91.
Тройка подошла. Значит, мы можем записать так:
1092 = 2 ∙ 2 ∙ 3 ∙ 91.
Проверяем тройку повторно:
91 / 3 = 30¹/₃.
Тройка больше не подходит. Берем четверку? — Нет, четверку проверять не нужно. Четверка — это составное число, в «состав» которого входят две двойки:
4 = 2 ∙ 2.
Мы уже знаем, что число 91 на двойку не делится. Следовательно на число 2∙2 оно не делится и подавно. По аналогичной причине, нам вообще не нужно проверять делимость на какие-либо составные числа. Пропускаем четверку и устраиваем проверку следующему простому числу, то есть пятерке:
91 / 5 = 18¹/₅.
Пятерка не подошла. Шестерку, как составное число, пропускаем. Следующий «кандидат» в делители — это семерка:
91 / 7 = 13.
Семерка подходит. Разложение на множители принимает вид:
1092 = 2 ∙ 2 ∙ 3 ∙ 7 ∙ 13.
Надо ли нам теперь проверять последний множитель (13) на делимость на 7? — Нет, не надо. Это не надо делать по той причине, что 13 меньше, чем 7∙7:
13 < 7 ∙ 7 = 49.
Если бы 13 делилось нацело на 7, то мы могли бы тогда написать:
13 = n ∙ 7,
где n — какое-то натуральное число, которое должно оказаться меньше, чем 7. Но все такие числа мы уже проверили и выяснили, что на роль делителей они не подходят. Значит, 13 не может делиться нацело на семерку. По этой же причине, нет смысла проверять числа, которые больше 7. Отсюда мы заключаем, что 13 — простое число. И действительно, в списке чисел, который мы выписали выше, оно значится как простое. Вообще, процедуру разложения на множители следует прекращать тогда, когда «кандидат» в делители, умноженый сам на себя, оказывается больше, чем последний (то есть самый большой) множитель разложения.
Итак, мы разложили числитель дроби
1092 / 1638
на простые множители:
1092 = 2 ∙ 2 ∙ 3 ∙ 7 ∙ 13.
С помощью точно такой же процедуры раскладываем на простые множители знаменатель и получаем:
1638 = 2 ∙ 3 ∙ 3 ∙ 7 ∙ 13.
Теперь дробь сокращается очевидным образом:

1092	=	2 ∙ 2 ∙ 3 ∙ 7 ∙ 13	=	2	.
1638		2 ∙ 3 ∙ 3 ∙ 7 ∙ 13		3

Замечание. Мы заодно убедились в справедливости так называемой основной теоремы арифметики: всякое натуральное число, которое больше двух, можно единственным образом представить в виде произведения простых чисел. (При этом формально считается, что произведение может состоять всего из одного сомножителя. Именно такие «усеченные» произведения получаются, когда мы раскладываем на множители простые числа.)
Признаки делимости
Процедура разбиения натурального числа на простые множители существенно упростилась бы, если бы проверку на делимость можно было делать каким-нибудь быстрым способом, не выполняя в реальности трудоемкую операцию деления. Такая возможность действительно есть. Для этого надо воспользоваться признаками делимости.
Мы уже знаем признак делимости на 10. Этот признак можно сформулировать с помощью двух фраз:
(1) Всякое натуральное число, которое оканчивается цифрой 0, делится на 10.
(2) Всякое натуральное число, которое оканчивается любой другой цифрой, на 10 не делится.
Если воспользоваться формальным математическим языком, то эти две фразы можно объединить в одну:
Натуральное число делится на 10 в том и только том случае, когда оно оканчивается нулем.
Отметим, что словосочетание «в том и только том случае» несколько избыточно. Достаточно было бы сказать просто «только в том случае». Но так уж у математиков принято выражаться, и мы не будем нарушать эту традицию. В то же время, когда мы говорим «число делится на 10», то подразумеваем не просто «делится», а «делится нацело». Также заметим, что хотя мы формулируем признаки делимости для натуральных чисел, они с тем же успехом подходят и для целых чисел: если a делиться нацело на b, то и −aделится на b.
Таким образом, если нам нужно будет разложить на простые множители какое-либо число, которое оканчивается нулем, например 5670, то мы начнем с того, что напишем:
5670 = 2 ∙ 5 ∙ 567.
А если число оканчивается двумя нулями? — Тогда будем писать так:
56700 = 2 ∙ 2 ∙ 5 ∙ 5 ∙ 567.
Признак делимости на 2. Натуральное число делится на 2 в том и только том случае, если его последняя цифра делится на 2, то есть равна 0, 2, 4, 6 или 8.
Целые числа, которые делятся на 2, называются четными. Целые числа, которые не делятся на 2, называются нечетными.
Признак делимости на 5. Натуральное число делится на 5 в том и только том случае, если его последняя цифра делится на 5, то есть равна 0 или 5.
Прежде чем переходить к признакам делимости на другие числа, сделаем небольшое отступление. Рассмотрим для определенности делимость на 3. Возьмем два целых числа, a и d, — такие что число a совершенно произвольно, а про число d известно, что оно кратно трем. Это можно записать так:
a = 3m + r,
d = 3n,
Здесь n, m и r — некоторое целые числа, причем на r наложено дополнительное ограничение:
0 ≤ r < 3.
Пусть число b равно разности a и d:
b = a − d = 3m + r − 3n = 3(m − n) + r.
Очевидно, что a делится нацело на 3 тогда и только тогда, когда r = 0. Но то же самое мы можем сказать и про число b. Теперь предположим, что a — это большое, многозначное число, которое было бы очень трудно поделить на 3, аb — напротив, число маленькое, которое поделить на 3 не составит никаких проблем. Тогда признак делимости на 3 можно сформулировать таким образом: a делится на 3 в том и только том случае, когда b делится на 3. Именно так и формулируются все признаки делимости, только вместо числа 3 может стоять любое другое натуральное число k. Для доказательства такого признака нам достаточно показать, что «проверочное число» b представимо в виде:
b = a − kn,
где n — некоторое натуральное число, то есть что разность чисел a и bделится на k:
a − b = kn.
Продемонстрируем сказанное на примере признаков делимости на 2 и на 5. Будем для определенности считать что a ≥ 0. В самом общем случае его можно представить в таком виде:
a = u ∙ 10 + v,
где u — некоторое целое неотрицательное число (равное числу a с отброшенным последним знаком), а v — некоторое однозначное число (равное последней цифре числа a). В качестве «проверочного числа» bвозьмем число v:
b = v.
Тогда для разности чисел a и b получаем:
a − b = u ∙ 10 = 2 ∙ 5 ∙ u.
Очевидно, что эта разность делится нацело на 2 и на 5. Таким образом, мы получили формальное доказательство признаков делимости, которые были сформулированы выше.
Признак делимости на 3. Натуральное число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3. Например, число 123 делится на 3, поскольку 1 + 2 + 3 = 6 делится на 3.
Действительно, представим произвольное натуральное число a в виде:
a = ... + v∙10000 + w∙1000 + x∙100 + y∙10 + z,
где под буквами v, w, x, y, z подразумеваются значения соответствующих разрядов числа a, а многоточие (...) говорит о том, что вместо него могут присутствовать еще и другие слагаемые. Тогда «проверочное число» b равно
b = ... + v + w + x + y + z.
Разность чисел a и b представима в виде:
a − b =
... + 9999∙v + 999∙w + 99∙x + 9∙y =
3∙3∙(... + 1111∙v + 111∙w + 11∙x + 1∙y)
Ясно, что эта разность кратна трем, что и доказывает данный признак делимости. Более того, эта разность кратна девяти. Поэтому отсюда же мы получаем —
признак делимости на 9. Натуральное число делится на 9 тогда и только тогда, когда сумма его цифр делится на 9. Например, число 234 делится на 9, поскольку 2 + 3 + 4 = 9 делится на 9.
Признак делимости на 7. Пусть a — произвольное целое число, причем его последняя цифра равна v, а число, которое получается после отбрасывания последней цифры, равно u:
a = u ∙ 10 + v.
Число a делится нацело на 7 тогда и только тогда, когда делится нацело на 7 число
b = u − 2∙v.
Иными словами, «проверочное число» получается, если из числа с отброшенной последней цифрой вычесть удвоенную последнюю цифру. Например, число 112 делится на 7, поскольку 11 − 2∙2 = 7 делится на 7.
Для доказательства этого утверждения мы рассмотрим не разность a − b, а сумму 2a + b. Такая подмена совершенно законна, потому что числа a и 2aодновременно либо делятся нацело на 7, либо не делятся (в разложении того и другого на простые множители семерка либо присутствует, либо нет). То же самое можно сказать и про числа b и −b.
2∙a + b =
20∙u + 2∙v + u − 2∙v =
21∙u =
3∙7∙u.
Таким образом, мы получили число, кратное семи. Доказательство завершено.
Признак делимости на 11. Натуральное число делится нацело на 11 тогда и только тогда, когда сумма его цифр, взятых с чередующимися знаками, делится нацело на 11. Например, число 759 делится на 11, поскольку 7 − 5 + 9 = 11 делится на 11.
Прежде чем приводить доказательство, заметим, что следующие числа делятся нацело на 11:
99 = 11 ∙9;
1001 = 990 + 11 = 11 ∙ 90 + 11 = 11 ∙ 91;
9999 = 11 ∙ 909;
100001 = 99990 + 11 = 11 ∙ 9090 + 11 = 11 ∙ 9091;
999999 = 11 ∙ 90909;
и так далее.
Запишем, как мы это уже делали раньше, число a в виде:
a = ... + u∙100000 + v∙10000 + w∙1000 + x∙100 + y∙10 + z.
Тогда «проверочное число» равно
b = ... − u + v − w + x − y + z.
Вычитая b из a, получаем:
a − b =
... + u∙100001 + v∙9999 + w∙1001 + x∙99 + y∙11 =
11 ∙ (9091∙u + 909∙v + 91∙x + 9∙y).
Для полноты картины приведем еще признаки делимости на 4, на 6 и на 8. (Впрочем, поскольку это всё составные числа, практическая польза от этих признаков невелика.)
Признак делимости на 4. Натуральное число делится на 4 в том и только том случае, если две его последние цифры делятся на 4.
Признак делимости на 8. Натуральное число делится на 8 в том и только том случае, если три его последние цифры делятся на 8.
Признак делимости на 6. Натуральное число делится на 6 в том и только том случае, если оно делится на 2 и на 3.

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

4340
434
217
31

2∙5
2
7
31

» Признаки делимости на 3, 6 и 9