Определение. Пусть даны натуральные числа а и b. Говорят, что число а делится на число b, если существует такое натуральное число q, что а = bq.
В этом случае число b называютделителем числа а , а число а - кратным числа b.
Например , 24 делится на 8, так как существует такое q = 3, что 24 = 8×3. Можно сказать иначе: 8 - это делитель числа 24, а 24 есть кратное числа 8.
В том случае, когда а делится на b, пишут: а M b. Эту запись часто читают и так: «а кратно b».
Заметим, что понятие «делитель данного числа» следует отличать от понятия «делитель», обозначающего то число, на которое делят. Например, если 18 делят на 5, то число 5 - делитель, но 5 не является делителем числа 18. Если 18 делят на 6, то в этом случае понятия «делитель» и «делитель данного числа» совпадают.
Из определения отношения делимости и равенства a = 1 × а, справедливого для любого натурального а, вытекает, что 1 является делителем любого натурального числа.
Выясним, сколько вообще делителей может быть у натурального числа а. Сначала рассмотрим следующую теорему.
Теорема 1. Делитель b данного числа а не превышает этого числа, т. е. если а M b, то b £ а.
Доказательство. Так как а M b, то существует такое qÎ N, что а = bq и, значит, а - b = bq - b = b ×(q - 1). Поскольку qÎ N, то q ³ 1. . Тогда b ×(q - 1) ³ 0 и, следовательно, и b £ а.
Из данной теоремы следует, что множество делителей данного числа конечно. Назовем, например, все делители числа 36. Они образуют конечное множество {1,2,3,4,6,9, 12, 18,36}.
В зависимости от числа делителей среди натуральных чисел различают простые и составные числа.
Определение. Простым числом называется такое натуральное число, большее 1, которое имеет только два делителя - единицу и само это число.
Например , 13 – простое, поскольку у него только два делителя: 1 и 13.
Определение. Составным числом называется такое натуральное число, которое имеет более двух делителей.
Так число 4 составное, у него три делителя: 1, 2 и 4. Число 1 не является ни простым, ни составным числом в связи с тем, что оно имеет только один делитель.
Чисел, кратных данному числу, можно назвать как угодно много, -их бесконечное множество. Так, числа, кратные 4, образуют бесконечный ряд: 4, 8, 12, 16, 20, 24, .... и все они могут быть получены по формуле а = 4q, где q принимает значения 1, 2, 3,... .
Нам известно, что отношение делимости на множестве N обладает рядом свойств, в частности, оно рефлексивно, антисимметрично и транзитивно. Теперь, имея определение отношения делимости, мы можем доказать эти и другие его свойства.
Теорема 2. Отношение делимости рефлексивно, т.е. любое натуральное число делится само на себя.
Доказательство. Для любого натурального а справедливо равенство а = а× 1. Так как 1 Î N то, по определению отношения делимости, аMа.
Теорема 3 . Отношение делимости антисимметрично, т.е. если а M b и а ¹ b, то .
Доказательство. Предположим противное, т. е. что bMа. Но тогда а£ b, согласно теореме, рассмотренной выше.
По условию а M b и а ¹ b. Тогда, по той же теореме, b £ а.
Неравенства а £ b и b £ а.будут справедливы лишь тогда, когда а = b, что противоречит условию теоремы. Следовательно, наше предположение неверное и теорема доказана.
Теорема 4. Отношение делимости транзитивно, т.е. если а M b и b M с, то а M с.
Доказательство. Так как а M b, q, что а = b q , а так как bM с, то существует такое натуральное число р , что b = ср. Но тогда имеем: а = b q = (ср)q = с(рq). Число рq - натуральное. Значит, по определению отношения делимости, а. M с.
Теорема 5 (признак делимости суммы). Если каждое из натуральных чисел а 1, а 2 ,…а п делится на натуральное число b, то и их сумма а 1 + а 2 + … + а п делится на это число.
Например , не производя вычислений, можно сказать, что сумма 175 + 360 +915 делится на 5, так как на 5 делится каждое слагаемое этой суммы.
Теорема 6 (признак делимости разности). Если числа а 1 и а 2 делятся на b и а 1 ³ а 2 , то их разность а 1 - а 2 делится на b.
Теорема 7 (признак делимости произведения). Если число а делится на b, то произведение вида ах, где х е N. делится на b.
Из теоремы следует, что если один из множителей произведения делится на натуральное число b, то и все произведение делится на b.
Например , произведение 24×976×305 делится на 12, так как на 12 делится множитель 24.
Рассмотрим еще три теоремы, связанные с делимостью суммы и произведения, которые часто используются при решении задач на делимость.
Теорема 8. Если в сумме одно слагаемое не делится на число b, а все остальные слагаемые делятся на число b, то вся сумма на число b не делится.
Например, сумма 34 + 125 + 376 + 1024 на 2 не делится, так как 34:2,376: 2,124: 2,но 125 не делится на 2.
Теорема 9. Если в произведении аb множитель а делится на натуральное число т, а множитель b делится на натуральное число п то а b делится на тп.
Справедливость этого утверждения вытекает из теоремы о делимости произведения.
Теорема 10. Если произведение ас делится на произведение bс, причем с - натуральное число, то и а делится на b.
Определение. Говорят, что число а делится на число в, если существует такое число c Î N 0 , что а = в · с.
В том случае, когда а делится на в пишут: а в. Читают: «а делится на в »; «а кратно в »; «в – делитель а ». Например, 12 делится на 6, так как существует такое с = 2, что 12 = 6 · 2, иначе 12 6.
Замечание . Записи и а : в не равносильны. Первое обозначает, что между числами а и в имеет место отношение делимости (возможно нацело число а разделить на число в ). Второе – есть обозначение частного чисел а и в .
Отношение делимости обладает рядом свойств.
1°. Нуль делится на любое натуральное число, т.е.
(" в Î N ) .
Доказательство. 0 = в · 0для любого в, отсюда по определению следует, что 0 в .
2°. Ни одно натуральное число не делится на нуль, т.е. ("а Î N ) [а 0].
Доказательство (от противного). Пусть существует c Î N 0 , такое, что а = 0· с, но по условию а ≠ 0,значит ни при каком с это равенство не выполняется. Значит, наше предположение о существовании с было неверным и а 0.
3°. Любое целое неотрицательное число делится на единицу, т.е.
("а Î N ) [а 1].
Доказательство. а = 1· а => а 1.
4°. Любое натуральное число делится само на себя (рефлексивность), т.е.("а Î N ) [а а ].
Доказательство. а = а · 1Þ а а.
5°. Делитель в данного натурального числа а не превышает этого числа, т.е. (а в Ù а > 0) Þ (а ≥ в ).
Доказательство. Так как а в, то а = в · с, где c Î N 0 . Определим знак разности а – в.
а – в = вс – в = в (с – 1),поскольку а > 0, то с ≥ 1, следовательно, в (с – 1) ≥ 0,значит а – в ≥ 0 Þ а ≥ в .
6°. Отношение делимости антисимметрично, т.е.
("a, в ÎN 0 )[(a в Ùв а ) Þ а = в ].
Доказательство.
1 случай. Пусть а > 0, в > 0,тогда имеем:
(по свойству 5°). Значит, а
= в
.
2 случай. Пусть хотя бы одно из чисел а или в равно 0.
Пусть а = 0, то в = 0по 2°, т.к. иначе в не могло бы делиться на а. Значит а = в.
7°. Отношение делимости транзитивно, т.е.
(" a, в, с Î N 0 ) [(a в Ù в с )Þ а с ].
Доказательство. а в Þ ($к )[а = вк ]; в с Þ ($ℓ )[в = cℓ ].
а = вк = (сℓ )к = с (ℓк ), ℓк – произведение двух неотрицательных целых чисел ℓ и к и потому само является целым неотрицательным, т.е. а с.
8°. Если каждое из чисел а и в делится на с, то их сумма а + в делится на с, т.е. ("a, в, с Î N 0 ) [(a с Ù в с ) Þ (а + в ) с ].
Доказательство, а с Þ а = ск, в с Þ в = cℓ.
а + в = ск + cℓ = с (к + ℓ ), т.к. к + ℓ –целое неотрицательное число, значит (а + в ) с.
Доказанное утверждение справедливо и в случае, когда число слагаемых больше двух.
Если каждое из чисел а 1 , ..., а п делится на с, то их сумма а 1 + ... + а п делится на с.
Кроме того, если числа а и в делятся на с, причем а ≥ в , то их разность а – в делится на с.
9°. Если число а делится на с , то произведение вида ах, где x ÎN 0 , делится на с, т.е. а с Þ (" x Î N 0 )[ax с ].
Доказательство. а с Þ а = ск, но тогда ах = скх = с (к · х ), к, x Î N 0 , значит ах с.
Следствие из 8°, 9°.
Если каждое из чисел а 1 , а 2 , ..., а п делится на с, то каковы бы ни были числа х 1 , х 2 , ... , х n число а 1 х 1 + а 2 х 2 + ... + а n х n делится на с.
10°. Если ас делится на вс, причем с ≠ 0, то а делится на в, т.е. (ас вс Ù с ≠ 0) Þ а в.
Доказательство.
ас = вс · к; ас = (вк ) · с Ù с ≠ 0 Þ а = вк => а в .
Признаки делимости
Встречаются задачи, в которых, не производя деления, требуется установить делится или нет натуральное число а на натуральное число в. Чаще всего такие задачи возникают, когда число а надо разложить на множители. В подобных задачах пользуются признаками делимости. Признак делимости – это предложение, позволяющее ответить на вопрос, делится или нет некоторое число на данный делитель, не производя самого деления.
Применяя признак делимости, делить все-таки приходится, конечно. Из школы хорошо известен признак делимости числа на 3. Делится ли число 531246897 на 3? Для ответа на вопрос определим сумму цифр этого числа 5 + 3 + 1 + 2 + 4 + 6 + 8 + 9 + 7 = 45, т.к. 45 делится на 3, то данное число делится на 3.
Итак, вопрос о делимости данного натурального числа сведен к вопросу о делимости меньшего натурального числа.
Признаки делимости зависят от системы счисления. Рассмотрим некоторые признаки делимости в десятичной системе счисления.
Лекция 4. Делимость на множестве целых неотрицательных чисел
1. Понятие отношения делимости, его свойства.
2. Признаки делимости суммы, разности, произведения.
3. Признаки делимости на 2, 3, 4, 5, 9 (два доказать).
В начальном курсе математики делимость натуральных чисел, как правило, не изучается, но многие факты из этого раздела математики неявно используются.
Отношение делимости и его свойства
Рассмотрим отношение делимости на множестве целых неотрицательных чисел.
Определение 1. Пусть даны целые неотрицательные числа а и b . Говорят, что число а b , если существует такое целое неотрицательное число q , что а=bq . В этом случае число b называют делителем числа а , а число а - кратным числа b.
Обознаение: а b и говорят а кратно b , а b называют делителем числа а .
Заметим, что понятие "делитель данного числа" следует отличать от понятия "делитель", обозначающего то число, на которое делят. Например, если 18 делят на 5, то число 5 - делитель, но не является делителем числа 18. Если 18 делят на 6, то в этом случае понятия "делитель" и "делитель данного числа" совпадают.
Замечание. Из определения 1 и равенства а=1а , следует, что 1 является делителем любого целого неотрицательного числа.
Свойства отношения делимости:
Отношение делимости рефлексивно, антисимметрично, транзитивно.
Теорема 1. Отношение делимости рефлексивно, т.е. любое натуральное число делится само на себя 
.
Доказательство:
Для 
справедливо равенство а=а 1. Т.к. 1 , то по опр. 1 .
Теорема 2. Отношение делимости антисимметрично, т. е.
Доказательство (методом от противного): Предположим, что 
. Тогда очевидно, что b≥a. Но по условию 
и значит а≥b. Выполнение этих неравенств возможно только при а=b, что противоречит условию. Следовательно, наше предположение неверно и справедливость свойства установлена.
Теорема 3. Отношение делимости транзитивно, то есть
Доказательство:
Т.к. , то по опр.1 
. Аналогично, т.к. b с, то .
Тогда a=bq=(cp)q=c(pq). Число рq- натуральное. Это означает по опр.1, что а с.
Таким образом, отношение делимости на множестве N, обладая свойствами рефлексивности, антисимметричности и транзитивности, является отношением нестрогого порядка.
Делимость суммы, разности, произведения целых неотрицательных чисел
Теорема 4 (признак делимости суммы): Если каждое слагаемое суммы делится на натуральное число b, то и вся сумма делится на это число, то есть
Доказательство:
Пусть 
. Тогда существуют q 1 ,q 2 ,…q n 
N такие, что выполняются равенства: а 1 =bq 1 , а 2 =bq 2 , …, а 1 n = bq n . Из этих равенств следует, что а 1 +а 2 +…а n =bq 1 +bq 2 +…+bq n =b(q 1 +q 2 +…+q n), где q 1 +q 2 +…+q n =q N 0 . По определению отношения делимости это означает, что .
Теорема 5 (признак делимости разности): Если каждое из чисел а и b делится на с и а≥b , то разность а-b делится на с , т. е. если .
Доказательство:
Пусть 
. Тогда существуют q 1 ,q 2 N такие, что а=cq 1 , b=cq 2 . Поскольку а≥b, то q 1 >q 2 . Таким образом, имеем а-b
=cq 1 -cq 2 =c(q 1 -q 2)=cq,
где q 1 -q 2 =q
N. Следовательно, .
Теорема 6 (признак делимости произведения):
Если хотя бы один из множителей произведения делится на натуральное число b, то и все произведение делится на это число, то есть 
.
Доказательство:
Пусть а k b, тогда существует q N такое, что а k =bq. Отсюда, используя коммутативный и ассоциативный законы умножения, можем записать . Поскольку произведение целых неотрицательных чисел является целым неотрицательным числом, то последнее равенство означает, что 
.
Теорема 7: Если в произведении ab множитель а делится на натуральное число m , а множитель b делится на натуральное число n , то произведение ab делится на произведение nm , то есть .
Доказательство:
Пусть a m и b n, тогда существуют q 1 ,q 2 N такие что, a=mq 1 , b=nq 2 . Отсюда на основании комм. и ассоц. законов умножения имеем ab=(mq 1)(nq 2)=(mn)(q 1 q 2)=(mn)q, где q 1 q 2 =q N . следовательно, ab mn.
Теорема 8: Если в сумме одно слагаемое не делится на натуральное число b , а все остальные слагаемые делятся на это число, то и вся сумма на число b не делится.
Доказательство:
Пусть S=a 1 +a 2 +…+a n +c, где а 1 b, a 2 b, …, a n b, но 
. Докажем, что 
. Предположим противное, то есть S b. Тогда с=S-(a 1 +a 2 +…+a n), где S b, и (a 1 +a 2 +…+a n) b. По теореме о делимости разности это означает, что с b. Полученное противоречие и доказывает теорему.
Признаки делимости
Теорема 9 (признак делимости на 2) Для того чтобы число х делилось на 2, необходимо и достаточно, чтобы его десятичная запись оканчивалась одной из цифр 0,2,4,6,8.
Доказательство. Пусть число х
х = а n ·10 + а n-1 ·10 n-1 + ... + а 1 · 10 + а 0 , где а n , а n-1,…, a 1 принимают значения 0, 1, 2, ...9, а n ≠0 и а 0 принимает значения 0,2,4,6,8. Докажем, что тогда х: .2.
Так как 10: .2, то 10 2: .2, 10 3: .2,…,10 n: .2 и, значит, (а n ·10 + а n-1 ·10 n-1 + ... + а 1 · 10) : .2. По условию а 0 тоже делится на 2, поэтому число х можно рассматривать как сумму двух слагаемых, каждое из которых делится на 2. Следовательно, согласно признаку делимости суммы, число хделится на 2.
Докажем обратное: если число х делится на 2, то его десятичная запись оканчивается одной из цифр 0,2,4,6,8.
Запишем равенство х = а n ·10 + а n-1 ·10 n-1 + ... + а 1 · 10 + а 0 в таком виде: а 0 = х - (а n ·10 + а n-1 ·10 n-1 + ... + а 1 · 10). Но тогда, по теореме о делимости разности, а 0: . 2, поскольку х: . 2 и (а n ·10 + а n-1 ·10 n-1 + ... + а 1 · 10) : . 2. Чтобы однозначное число а 0 делилось на 2, оно должно принимать значения 0,2,4,6,8.
Теорема 10 (признак делимости на 5). Для того чтобы число х делилось на 5, необходимо и достаточно, чтобы его десятичная запись оканчивалась цифрой 0 или 5.
Доказать самостоятельно!
Доказательство этого признака аналогично доказательству признака делимости на 2.
Теорема 11 (признак делимости на 4). Для того чтобы число х делилось на 4, необходимо и достаточно, чтобы на 4 делилось двузначное число, образованное последними двумя цифрами десятичной записи числа х .
Доказательство . Пусть число х записано в десятичной системе счисления, т.е.
х = а n ·10 + а n-1 ·10 n-1 + ... + а 1 · 10 + а 0 и последние цифры в этой записи образуют число, которое делится на 4. Докажем, что тогда х: . 4.
Так как 100: . 4, то (а n ·10 + а n-1 ·10 n-1 + ... + а 2 · 10 2) : . 4. По условию, а 1 ·10 + а 0 (это и есть запись двузначного числа) также делится на 4. Поэтому число х можно рассматривать как сумму двух слагаемых, каждое из которых делится на 4. Следовательно, согласно признаку делимости суммы, и само число х делится на 4.
Докажем обратное, т.е. если число х делится на 4, тo двузначное число, образованное последними цифрами его десятичной записи, тоже делится на 4.
Запишем равенство х = а n ·10 + а n-1 ·10 n-1 + ... + а 1 · 10 + а 0 в таком виде:
а 1 · 10 + а 0 = х- (а n ·10 + а n-1 ·10 n-1 + ... + а 2 · 10 2) .
Так как х: . 4 и (а n ·10 + а n-1 ·10 n-1 + ... + а 2 · 10 2) : . 4, то по теореме о делимости разности (а 1 · 10 + а 0) : . 4. Но выражение а 1 · 10 + а 0 есть запись двузначного числа, образованного последними цифрами записи числа х.
Теорема12 (признак делимости на 9) Для того чтобы число х делилось на 9, необходимо и достаточно, чтобы сумма цифр его десятичной записи делилось на 9.
Доказательство . Докажем сначала, что числа вида 10 n - 1 делятся на 9. Действительно, 10 n - 1 = (9·10 n-1 + 10 n-1) - 1 = (9·10 n-1 +9·10 n-2 + 10 n-2)-1 = (9·10 n-1 +9·10 n-2 + …+10)-1=9·10 n-1 +9·10 n-2 + …+9. Каждое слагаемое полученной суммы делится на 9, значит, и число 10 n - 1 делится на 9.
Пусть число х = а n ·10 + а n-1 ·10 n-1 + ... + а 1 · 10 + а 0 и (a n +a n-1 +…+a 1 +a 0) : . 9. Докажем, что тогда х: . 9.
Преобразуем сумму а n ·10 + а n-1 ·10 n-1 + ... + а 1 · 10 + а 0 , прибавив и вычтя из нее выражение a n +a n-1 +…+a 1 +a 0 и записав результат в таком виде:
х = (а n ·10 - a n)+( а n-1 ·10 n-1 - a n-1)+…+( а 1 · 10 - a 1)+ (а 0 – а 0)+ (a n +a n-1 +…+a 1 +a 0)= =а n ·(10 n -1)+ a n-1 ·(10 n-1 -1)+…+ a 1 ·(10 -1)+ (a n +a n-1 +…+a 1 +a 0).
В последней сумме каждое слагаемое делится на 9:
а n ·(10 n -1) : . 9, так как (10 n -1) : . 9,
a n-1 ·(10 n-1 -1) : . 9,так как(10 n-1 -1) : . 9 и т.д.
a 1 ·(10 -1) : . 9, так как (10- 1) : . 9,
(a n +a n-1 +…+a 1 +a 0) : . 9 по условию.
Следовательно, х: . 9.
Докажем обратное, т.е. если х: . 9, то сумма цифр его десятичной записи делится на 9.
Равенство х = а n ·10 + а n-1 ·10 n-1 + ... + а 1 · 10 + а 0 запишем в таком виде:
a n +a n-1 +…+a 1 +a 0 = х - (а n (10 n - 1) + а n-1 ·(10 n-1 -1) +…+ a 1 ·(10 -1).
Так как в правой части этого равенства и уменьшаемое, и вычитаемое кратны 9, то по теореме о делимости разности (a n +a n-1 +…+a 1 +a 0) : . 9, т.е. сумма цифр десятичной записи числа x делится на 9, что и требовалось доказать.
Теорема15 (признак делимости на 3): Для того чтобы число х делилось на 3, необходимо и достаточно, чтобы сумма цифр его десятичной записи делилась на 3.
Доказательство этого утверждения аналогично доказательству признака делимости на 9.
Определение. Пусть даны натуральные числа а и b. Говорят, что число а делится на число b, если существует такое натуральное число q, что a = bq.
В этом случае число b называют делителем числа а, а число а - кратным числа b.
Например, 24 делится на 8, так как существует такое q =3, что 24 = 8·3. Можно сказать иначе: 8 - это делитель числа 24, а 24 есть кратное числа 8. В том случае, когда а делится на b, пишут: а: . b. Эту запись »« читают и так: «а кратно b». Заметим, что понятие «делитель данного числа» следует отличать от понятия «делитель», обозначающего то число, на которое делят. Например, если 18 делят на 5, то число 5 -делитель, но 5 не является делителем числа 18. Если 18 делят 6, то в этом случае понятия «делитель» и «делитель данного числа» совпадают.
Из определения отношения делимости и равенства а = 1·а, справедливого для любого натурального а, вытекает, что 1 является делителем любого натурального числа.
Выясним, сколько вообще делителей может быть у натурального числа а. Сначала рассмотрим следующую теорему.
Теорема 1. Делитель b данного числа а не превышает этого числа, т.е. если
а: . b, то b < а.
Доказательство. Так как а: . b, то существует такое q Є N,что a = bq u, значит, a-b = bq – b= b·(q - 1). Поскольку q Є N,тоq≥ 1. Тогда b· (q - 1) ≥ 0 и, следовательно, b ≤ а.
Из данной теоремы следует, что множество делителей данного числа конечно. Назовем, например, все делители числа 36. образуют конечное множество {1,2,3,4,6,9,12,18,36}.
В зависимости от числа делителей среди натуральных чисел различают простые и составные числа.
Определение. Простым числом называется такое натуральное число, которое имеет только два делителя - единицу и само это число.
Например, число 13- простое, поскольку, у него только два делителя: 1 и 13.
Определение. Составным числом называется такое натуральное число, которое имеет более двух делителей.
Так число 4 составное, у него три делителя: 1,2 и 4.
Число 1 не является ни простым, ни составным числом в связи с тем, что оно имеет только один делитель.
Чисел, кратных данному числу, можно назвать как угодно много, - их бесконечное множество. Так, числа, кратные 4, образуют бесконечный ряд: 4, 8, 12, 16, 20, 24, …, и все они могут быть получены по формуле а = 4q, где q принимает значения 1, 2, 3,....
Нам известно, что отношение делимости обладает рядом свойств, в частности, оно рефлексивно, антисимметрично и транзитивно. Теперь, имея определение отношения делимости, мы можем доказать эти и другие его свойства.
Теорема 2. Отношение делимости рефлексивно, т.е. любое натуральное число делится само на себя.
Доказательство. Для любого натурального а справедливо равенство а = а·1. Так как 1 Є N, то, по определению отношения делимости, а: . а.
Теорема 3. Отношение делимости антисимметрично, т.е. если а: . b и а ≠ b,
то b ⁞͞ a.
Доказательство. Предположим противное, т.е. что b⁞ a. Но тогда а ≤ b, согласно теореме, рассмотренной выше.
По условию и а ⁞ . b и а ≠ b. Тогда, по той же теореме, b ≤ а.
Неравенства а ≤ b и b ≤ а будут справедливы лишь тогда, когда а = b, что противоречит условию теоремы. Следовательно, наше предположение неверное и теорема доказана.
Теорема 4 . Отношение делимости транзитивно, т.е. если а⁞ b и b⁞ с, то а⁞ с.
Доказательство. Так как а: . b, то существует такое натуральное число q, что a = bq, а так как b⁞ с, то существует такое натуральное число р, что b = ср. Но тогда имеем: a = bq = (cp)q = c(pq)- Число pq - натуральное. Значит, по определению отношения делимости,
а⁞ с.
Теорема 5 (признак делимости суммы). Если каждое из натуральных чисел а 1 , а 2 , ...,а п делится на натуральное число b, то и их сумма a 1 + а 2 + ... + а n делится на это число.
Доказательство. Так как а 1 ⁞ b, то существует такое натуральное число q 1 , что а 1 =bq 1 . Так как а 2 ⁞ b, то существует такое натуральное число q 2 , что а 2 = bq 2 . Продолжая рассуждения, получим, что если а n: . b, то существует такое натуральное число q n , что а п = bq n . Эти равенства позволяют преобразовать сумму а 1 + а 2 + ... +а п в сумму вида bq 1 + bq 2 + ... + bq n . Вынесем за скобки общий множитель b, а получившееся в скобках натуральное число q 1 + q 2 + ... + q n обозначим буквой q. Тогда a 1 + a 2 + ... + a n = b(q 1 + q 2 +... + q n) = bq, т.е. сумма а 1 + а 2 +… + а п оказалась представленной в виде произведения числа b и некоторого натурального числа q. А это значит, что сумма а 1 + а 2 +… + а п делится на b, что и требовалось доказать.
Например, не производя вычислений, можно сказать, что 175 + 360 + 915 делится на 5, так как на 5 делится каждое слагаемое этой суммы.
Теорема 6 (признак делимости разности). Если числа а 1 и а 2 делятся на b и а 1 ≥ а 2 , то их разность а 1 - а 2 делится на b.
Доказательство этой теоремы аналогично доказательству признака делимости суммы.
Теорема 7 (признак делимости произведения). Если число а делится на b, то произведениe вида ах, где х Є N, делитcя на b.
Доказательство. Так как а: . b, то существует такое натуральное число q, что a = bq. Умножим обе части этого равенства на натуральное число х. Тогда ах=(bq)x, откуда на основании свойства ассоциативности умножения (bq)x = b(qx)и, значит, ax = b(qx), где qx - натуральное число. Согласно определению отношения делимости, ax: . b, что и требовалось доказать.
Из доказанной теоремы следует, что если один из множителей произведения делится на натуральное число b, то и все произведение делится на b. Например, произведение 24·976·305 делится на 12, так как на 12 делится множитель 24.
Рассмотрим еще три теоремы, связанные с делимостью суммы и произведения, которые часто используются при решении задач на делимость.
Теорема 8. Если в сумме одно слагаемое не делится на число b, а все остальные слагаемые делятся на число b, то вся cумма на число b не делится.
Доказательство. Пусть s = а 1 + а г + ... + а п +" с и известно, что а 1: . B, а 2: . B,
а 3: . b, … а n: . b, но с: . b. Докажем, что тогда s: . b
Предположим противное, т.е. Пусть s: . b. Преобразуем сумму s к виду с = s- (а 1 + а 2 +… + а n ). Так как s: . b по предположению, (а 1 + а 2 +… + а n ) : . b согласно признаку делимости суммы, то по теореме делимости разности с: .b
Пришли к противоречию с тем, что дано. Следовательно, s: . b.
Например, сумма 34 + 125 + 376 + 1024 на 2 не делится, так 34: .2,376: .2,124: .2, но 125 не делится на 2.
Теорема 9 . Если в произведении ab множитель a делится на натуральное число т, а множитель b делится на натуральное число n,то ab делится на mn.
Справедливость этого утверждения вытекает из теоремы о делимости произведения.
Теорема 10. Если произведение ас делится на произведение bс, причем с - натуральное число, то и а делится на b.
Доказательство. Так как ас делится на bc, то существует такое натуральное число q, что ас = (bc)q, откуда ас = (bq)c и, следовательно, а = bq, т.е. а : .b.
Упражнения
1. Объясните, почему число 15 является делителем числа 60 и не является делителем числа 70.
2. Постройте граф отношения «быть делителем данного числа», заданного на множестве Х = {2, 6,. 12, 18, 24}. Как отражены на этом графе свойства данного отношения?
3. Известно, что число 24 - делитель числа 96, а число 96 -делитель числа 672. Докажите, что число 24 делитель числа 672, не выполняя деления.
4. Запишите множество делителей числа.
а) 24; 6)13; в) 1.
5 .На множестве X ={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11; 12} задано отношение «иметь одно и то же число делителей». Является ли оно отношением эквивалентности?
6 .Постройте умозаключение, доказывающее, что:
а) число 19 является простым;
б) число 22 является составным.
7. Докажите или опровергните следующие утверждения:
а) Если сумма двух слагаемых делится на некоторое число, то и каждое слагаемое делится на это число.
б) Если одно из слагаемых суммы не делится на некоторое число, то и сумма не делится на это число.
в) Если ни одно слагаемое не делится на некоторое число, то и сумма не делится на это число.
г) Если одно из слагаемых суммы делится на некоторое число, а другое не делится на это число, то и сумма не делится на это число.
8. Верно ли, что:
а) а: . ти b: . n =>ab: .mn
б) а: .п и b: .n => ab: .n;
в) ab: .n => а: .п или b: .n.