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

Навигация по странице.

Понятие делимости

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

Целое число a делится на целое число b , которое отлично от нуля, если существует такое целое число (обозначим его q ), что справедливо равенство a=b·q . В этом случае также говорят, что b делит a . При этом целое число b называется делителем числа a , целое число a называется кратным числа b (для получения более детальной информации о делителях и кратных обращайтесь к статье делители и кратные), а целое число q называют частным .

Если целое число a делится на целое число b в указанном выше смысле, то можно сказать, что a делится на b нацело . Слово «нацело» в этом случае дополнительно подчеркивает, что частное от деления целого числа a на целое число b является целым числом.

В некоторых случаях для данных целых чисел a и b не существует такого целого числа q , при котором справедливо равенство a=b·q . В таких случаях говорят, что целое число a не делится на целое число b (при этом имеется в виду, что a не делится на b нацело). Однако в этих случаях прибегают к .

Разберемся с понятием делимости на примерах.

Любое целое число a делится на число a , на число −a , a , на единицу и на число −1 .

Докажем это свойство делимости.

Для любого целого числа a справедливы равенства a=a·1 и a=1·a , из которых следует, что a делится на a , причем частное равно единице, и что a делится на 1 , причем частное равно a . Для любого целого числа a также справедливы равенства a=(−a)·(−1) и a=(−1)·(−a) , из которых следует делимость a на число, противоположное числу a , а также делимость a на минус единицу.

Отметим, что свойство делимости целого числа a на себя называют свойством рефлексивности.

Следующее свойство делимости утверждает, что нуль делится на любое целое число b .

Действительно, так как 0=b·0 для любого целого числа b , то нуль делится на любое целое число.

В частности, нуль делится и на нуль. Это подтверждает равенство 0=0·q , где q – любое целое число. Из этого равенства вытекает, что частным от деления нуля на нуль является любое целое число.

Также нужно отметить, что на 0 не делится никакое другое целое число a , отличное нуля. Поясним это. Если бы нуль делил целое число a , отличное от нуля, то должно было бы быть справедливо равенство a=0·q , где q – некоторое целое число, а последнее равенство возможно только при a=0 .

Если целое число a делится на целое число b и a меньше модуля числа b , то a равно нулю. В буквенном виде это свойство делимости записывается так: если ab и , то a=0 .

Доказательство.

Так как a делится на b , то существует целое число q , при котором верно равенство a=b·q . Тогда должно быть справедливо и равенство , а в силу должно быть справедливо и равенство вида . Если q не равно нулю, то , откуда следует, что . Учитывая полученное неравенство, из равенства следует, что . Но это противоречит условию . Таким образом, q может быть равно только нулю, при этом получим a=b·q=b·0=0 , что и требовалось доказать.

Если целое число a отлично от нуля и делится на целое число b , то модуль числа a не меньше модуля числа b . То есть, если a≠0 и ab , то . Это свойство делимости непосредственно вытекает из предыдущего.

Делителями единицы являются только целые числа 1 и −1 .

Во-первых, покажем, что единица делится на 1 и на −1 . Это следует из равенств 1=1·1 и 1=(−1)·(−1) .

Осталось доказать, что никакое другое целое число не является делителем единицы.

Предположим, что целое число b , отличное от 1 и −1 , является делителем единицы. Так как единица делится на b , то в силу предыдущего свойства делимости должно выполняться неравенство , которое равносильно неравенству . Этому неравенству удовлетворяют только три целых числа: 1 , 0 , и −1 . Так как мы приняли, что b отлично от 1 и −1 , то остается лишь b=0 . Но b=0 не может быть делителем единицы (что мы показали при описании второго свойства делимости). Этим доказано, что никакие числа, отличные от 1 и −1 , не являются делителями единицы.

Чтобы целое число a делилось на целое число b необходимо и достаточно, чтобы модуль числа a делился на модуль числа b .

Докажем сначала необходимость.

Пусть a делится на b , тогда существует такое целое число q , что a=b·q . Тогда . Так как является целым числом, то из равенства следует делимость модуля числа a на модуль числа b .

Теперь достаточность.

Пусть модуль числа a делится на модуль числа b , тогда существует такое целое число q , что . Если числа a и b положительные, то справедливо равенство a=b·q , которое доказывает делимость a на b . Если a и b отрицательные, то верно равенство −a=(−b)·q , которое можно переписать как a=b·q . Если a – отрицательное число, а b – положительное, то имеем −a=b·q , это равенство равносильно равенству a=b·(−q) . Если a – положительное, а b – отрицательное, то имеем a=(−b)·q , и a=b·(−q) . Так как и q и −q являются целыми числами, то полученные равенства доказывают, что a делится на b .

Следствие 1.

Если целое число a делится на целое число b , то a также делится на число −b , противоположное числу b .

Следствие 2.

Если целое число a делится на целое число b , то и −a делится на b .

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

Делимость обладает свойством транзитивности: если целое число a делится на некоторое целое число m , а число m в свою очередь делится на некоторое целое число b , то a делится на b . То есть, если am и mb , то ab .

Приведем доказательство этого свойства делимости.

Так как a делится на m , то существует некоторое целое число a 1 такое, что a=m·a 1 . Аналогично, так как m делится на b , то существует некоторое целое число m 1 такое, что m=b·m 1 . Тогда a=m·a 1 =(b·m 1)·a 1 =b·(m 1 ·a 1) . Так как произведение двух целых чисел является целым числом, то m 1 ·a 1 - это некоторое целое число. Обозначив его q , приходим к равенству a=b·q , которое доказывает рассматриваемое свойство делимости.

Делимость обладает свойством антисимметричности, то есть, если a делится на b и одновременно b делится на a , то равны либо целые числа a и b , либо числа a и −b .

Из делимости a на b и b на a можно говорить о существовании целых чисел q 1 и q 2 таких, что a=b·q 1 и b=a·q 2 . Подставив во второе равенство b·q 1 вместо a , или подставив в первое равенство a·q 2 вместо b , получим, что q 1 ·q 2 =1 , а учитывая, что q 1 и q 2 – целые, это возможно лишь при q 1 =q 2 =1 или при q 1 =q 2 =−1 . Отсюда следует, что a=b или a=−b (или, что то же самое, b=a или b=−a ).

Для любого целого и отличного от нуля числа b найдется такое целое число a , не равное b , которое делится на b .

Таким числом будет любое из чисел a=b·q , где q – любое целое число, не равное единице. Можно переходить к следующему свойству делимости.

Если каждое из двух целых слагаемых a и b делится на целое число c , то сумма a+b также делится на c .

Так как a и b делятся на c , то можно записать a=c·q 1 и b=c·q 2 . Тогда a+b=c·q 1 +c·q 2 =c·(q 1 +q 2) (последний переход возможен в силу ). Так как сумма двух целых чисел является целым числом, то равенство a+b=c·(q 1 +q 2) доказывает делимость суммы a+b на c .

Это свойство можно распространить на сумму трех, четырех и большего количества слагаемых.

Если еще вспомнить, что вычитание из целого числа a целого числа b представляет собой сложение числа a с числом −b (смотрите ), то данное свойство делимости справедливо и для разности чисел. Например, если целые числа a и b делятся на c , то разность a−b также делится на с .

Если известно, что в равенстве вида k+l+…+n=p+q+…+s все члены, кроме какого-то одного, делятся на некоторое целое число b , то и этот один член делится на b .

Допустим, этим членом является p (мы можем взять любой из членов равенства, что не повлияет на рассуждения). Тогда p=k+l+…+n−q−…−s . Выражение, получившееся в правой части равенства, делится на b в силу предыдущего свойства. Следовательно, число p также делится на b .

Если целое число a делится на целое число b , то произведение a·k , где k – произвольное целое число, делится на b .

Так как a делится на b , то справедливо равенство a=b·q , где q – некоторое целое число. Тогда a·k=(b·q)·k=b·(q·k) (последний переход осуществлен в силу ). Так как произведение двух целых чисел есть целое число, то равенство a·k=b·(q·k) доказывает делимость произведения a·k на b .

Следствие: если целое число a делится на целое число b , то произведение a·k 1 ·k 2 ·…·k n , где k 1 , k 2 , …, k n – некоторые целые числа, делится на b .

Если целые числа a и b делятся на c , то сумма произведений a·u и b·v вида a·u+b·v , где u и v – произвольные целые числа, делится на c .

Доказательство этого свойства делимости аналогично двум предыдущим. Из условия имеем a=c·q 1 и b=c·q 2 . Тогда a·u+b·v=(c·q 1)·u+(c·q 2)·v=c·(q 1 ·u+q 2 ·v) . Так как сумма q 1 ·u+q 2 ·v является целым числом, то равенство вида a·u+b·v=c·(q 1 ·u+q 2 ·v) доказывает, что a·u+b·v делится на c .

На этом закончим обзор основных свойств делимости.

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

• Виленкин Н.Я. и др. Математика. 6 класс: учебник для общеобразовательных учреждений.
• Виноградов И.М. Основы теории чисел.
• Михелович Ш.Х. Теория чисел.
• Куликов Л.Я. и др. Сборник задач по алгебре и теории чисел: Учебное пособие для студентов физ.-мат. специальностей педагогических институтов.

Если первое число делится на второе, а второе на третье, то первое число делится на третье.

Например, дано три числа 777, 111 и 3. Число 777 делится на 111, а 111 делится на 3, значит 777 также делится на 3:

Делимость суммы и разности

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

Например, дано два числа: 27 и 12. Число 27 делится на 3, и 12 делится на 3. Из этого следует, что сумма 27 и 12 и разность 27 и 12 делятся на 3:

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

Например, дано два числа: 64 и 10. Число 64 делится на 8, а 10 не делится на 8, значит сумма 64 и 10 и разность 64 и 10 не делятся на 8:

10: 8 = 1 (остаток 2)

74: 8 = 9 (остаток 2)

54: 8 = 6 (остаток 6)

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

Если один из множителей делится на некоторое число, то и произведение делится на это число.

Например, дано два числа: 8 и 9. Число 8 делится на 4, значит и произведение 8 и 9 делится на 4.

Понятие отношения делимости

Определение. Число а делится на число в тогда и только тогда, когда существует такое число q, что а = в × q. а в ( q N 0) [а = вq].

Обозначают: а в. Читают: «число а кратно числу в», «число в – делитель числа а», «а кратно в».

Равенство а=вq называют формулой кратности числа а числу в.

Число а, кратное 2, называют четным. Общий вид четного числа: а = 2n, n N 0 .

Число, кратное 3 имеет формулу: а = 3n, n N 0 .

Определение. Отношение делимости на множестве N 0 N содержит те и только те пары чисел (а, в), у которых первая координата кратна второй. Обозначают: « ».

« » = {(а, в)| (а, в) N 0 N а в}.

Если отношение делимости обозначить , то N 0 N ={(а, в)| (а, в) N 0 N а=вq}.

Теорема. Делитель в данного числа а не превышает этого числа, то есть, если а в в а.

Доказательство. Так как а в, то ( q N 0) [а = вq] а – в=вq-в=в(q – 1), так как q N q 1.

Тогда в (q – 1) 0 в а. Из определения отношения делимости и равенства а = 1 × а, следует, что 1 является делителем для любого натурального числа.

Следствие. Множество делителей данного числа конечно.

Например, делители числа 18 является конечное множество: {1, 2, 3, 6, 9, 18}.

Свойства отношения делимости

1. Отношение делимости рефлексивно, то есть любое натуральное число делится само на себя: ( а N) [(а,а) ], то есть а: а = 1.

Доказательство. ( а N)[а = а × 1] по определению отношения делимости а: а.

2. Отношение делимости антисимметрично, то есть для различных чисел а и в из того, что а в, следует, что в не кратно а. ( а, в N 0 N)[а в а в ].

Доказательство. Допустим, что в а, тогда в а. Но по условию а в, так как а в.

Неравенства в а а в истины только в том случае, если а = в. пришли к противоречию с условием. Следовательно, допущение, что в а Л. Таким образом, отношение делимости антисимметрично.

3. Отношение делимости транзитивно. ( а,в,с N 0 N)[а в в с а с].

Доказательство. Если а в ( q N)[а = вq] (1) Из того, что в с ( t N)[в = сt] (2)

Подставим в = сt в равенство (1), получим: а = (сt)q = c(tq), t,q N tq N tq = р а = ср, р N. А это значит, что а с.

Признаки делимости. Делимость суммы, разности, произведения

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

Теорема (признак делимости суммы). Если числа а и в делится на число n, то их сумма делится на это число, ( а,в, n N 0 N)[а n в n (а + в) n].

Доказательство. Из того что а n в n (по определению отношения делимости)

а=nq 1 (1), q 1 N. в=nq 2 (2), q 2 N. Преобразуем сумму (а + в) к виду:

а + в = nq 1 + nq 2 = n (q 1 + q 2) = nq,q = q 1 + q 2 . а + в = nq.

Следовательно, по определению отношения делимости, что (а + в) n.

Теорема (признак делимости разности). Если числа а и в делятся на число n и а в, то их разность а – в делится на число n, то есть

( а,в,n N 0 N)[а n в n а в (а – в) n].

Теорема (признак делимости произведения). Если один из множителей произведения делится на число n, то и все произведение делится на число n.

( а,в,n N 0 N)[а n (ав) n].

Доказательство. Из того, что а n а = nq (1). Умножим обе части равенства (1) на в N, получим: ав = nqв (по ассоциативности умножения) ав = n(qв) = nt, где t = qв ав = nt. А это значит, что ав n (по определению отношения делимости). Таким образом, для делимости произведения на число достаточно чтобы на данное число делился хотя бы один из множителей этого произведения.

Теорема. Если в произведении ав множитель а делится на натуральное число m, а множитель в делится на натуральное число n, то ав делится на mn.

( а,в,m,n N)[а m в n ав mn].

Доказательство. Из того, что а m а = mq 1 , q 1 N; в n в = nq 2 , q 2 N

ав = mq 1 × nq 2 , = mn(q 1 × q 2) = mnq, q 1 × q 2 = q N. ав = mnq ав mn.

Теорема (признак делимости на 2). Для того, чтобы число х делилось на 2 необходимо и достаточно, чтобы его десятичная запись оканчивалась одной из цифр: 0, 2, 4, 6, 8.

Доказательство. Пусть число х записано в десятичной системе счисления, то есть:

х = а n 10 n + a n –1 10 n –1 + …+a 1 10 + a 0 , где а n , a n –1 , …, а 1 – цифры, принимающие значения 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 и а n 0, а 0 – принимает значения 0, 2, 4, 6, 8.

Докажем, что число х 2. Так как 10 2, то любая степень числа 10 2. Десятичную запись числа х представим в виде: х = (а n 10 n + a n –1 10 n –1 + …+a 1 10) + a 0

I слагаемое II слагаемое

В этой сумме первое слагаемое по признаку делимости суммы делится на 2. Второе слагаемое а 0 2 (по условию). Следовательно, по признаку делимости суммы на число х делится на 2.

Обратно, если число х делится на 2, то его десятичная запись оканчивается цифрой 0, 2, 4, 6, 8.

Запишем число х = а n 10 n + a n –1 10 n –1 + …+a 1 10 + a 0 в виде: а 0 = х – (а n 10 n + a n –1 10 n –1 + …+a 1 10).

В этой разности число х 2 (по условию), вычитаемое (а n 10 n + a n –1 10 n –1 + …+a 1 10) 2 (по признаку делимости суммы). Следовательно, по теореме о делимости разности а 0 2. Чтобы однозначное число а 0 делилось на 2, оно должно принимать значения 0, 2, 4, 6, 8.

Признак делимости на 2. На 2 делятся те и только те числа, в разряде единиц которых содержится число, делящееся на 2 или на 2 делятся те и только те числа, десятичная запись которых оканчивается одной из цифр 0, 2, 4, 6, 8.

Теорема (признак делимости на 5). Для того, чтобы число х делилось на 5, необходимо и достаточно, чтобы его десятичная запись оканчивалась цифрой 0 или 5.

Лемма . ( n N) .

Доказательство. Так как 100 = 4 × 25, то по признаку делимости произведения

100 4. Тогда ( n N n > 1) 10 n = 100 × 10 n–2 и по признаку делимости произведения 10 n 4.

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

Пусть х = а n 10 n + a n –1 10 n –1 + …+a 1 10 + a 0 и пусть десятичная запись двух последних цифр a 1 10 + a 0 выражает число , которое делится на 4.

Доказательство. Представим число х в виде суммы двух слагаемых:

х = (а n 10 n + a n –1 10 n –1 + …+a 2 10 2) + (а 1 10 + а 0),

I слагаемое II слагаемое

где первое слагаемое, по доказанной выше Лемме, делится на 4, второе слагаемое делится на 4 по условию. Следовательно, согласно признака делимости суммы на число, число х делится на 4.

Обратно, если число х 4, то – двузначное число, образованное последними цифрами его десятичной записи, делится на 4.

По условию х 4. Докажем, что (а 1 10 + а 0) 4.

Доказательство. Десятичная запись числа х имеет вид:

х = а n 10 n + a n –1 10 n –1 + …+а 2 10 2 + a 1 10 + a 0 , представим число х в виде суммы двух слагаемых:

х = (а n 10 n + a n –1 10 n –1 + …+a 2 10 2) + (а 1 10 + а 0) и запишем равенство в виде:

х – (а n 10 n + a n –1 10 n –1 + …+a 2 10 2) = а 1 10 + а 0 , где х 4 (а n 10 n + a n –1 10 n –1 + …+a 2 10 2) 4 (по лемме).

Следовательно, по признаку делимости разности а 1 10 + а 0 4. выражение а 1 10 + а 0 = – есть запись двузначного числа, образованного последними цифрами записи числа х.

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

Теорема. Для того чтобы число х делилось на 25 необходимо и достаточно, чтобы на 25 делилось двузначное число, образованное последними двумя цифрами десятичной записи числа х.

Доказывается аналогично.

Признак делимости на 25. На 25 делятся те и только те числа, у которых две последние цифры в записи числа 00, 25, 50, 75.

Лемма. ( n N) [(10 n – 1) 9].

Докажем методом математической индукции.

1. Проверим справедливость утверждения для n = 1, И 3

Признак делимости на 3. На 3 делятся те и только те числа, сумма цифр которых делится на 3.

Говорят, что целое число a делится на целое число b, отличное от 0, если такое целое число с, определенное однозначно, что a=b*c.

Свойства: евклид лемма арифметика позиционный

• 1) Отношение делимости рефлексивно, т.е. . Действительно, число 1, а=а*1
• 2) Отношение делимости транзитивно, т.е. если

Из этого следует, что a=(c*k)*t=c*(k*t)=c*m

А это значит, что ас

• 3) Если аb, то (-a)b, (-a)(-b), a(-b)
• 4) Если ac и bc, то (ab)c

a=c*t, b=c*k (ab)=c*tc*k=c*(tk)(ab)c

НО: обратное утверждение неверно.

• 5) Если ab и cZ (произвольное число), то (a*c)b
• 6) Если каждое из чисел a1, a2…an делится на b, то (r1a1+…+rnan)b, где r1,…,rnZ
• 7) Если ac, b неc, то (a+b)нес

Пусть (a+b)=t и tc, t-a=b это противоречит условию.

• 8) 0на любое число, 0
• 9) Всякое целое число1, т.к. всякое число можно записать в виде а=1*а
• 10) На 0 делить нельзя: а=0*с, если а0, то это равенство неверно; если а=0, то имеем 0=0*с, сZ - в этом случае нарушается условие единственности определения с.
• 11) Если ab,то. a=b*c, где b,cZ

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

Разделить целое число а на целое число b0, это значит найти такие целые числа q и r, что a=bq+r, 0

Теорема: в кольце целых чисел всегда возможно выполнение деления с остатком и причем единственным образом.

Доказательство:

1) Существование:

Рассмотрим целые числа кратные b. Это числа -2b,-b,b,2b… и пусть bq-последнее кратное b, не превышающее число а, тогда оно является наибольшим среди записанных кратных. В этом случае b(q+1)>a. Получили:

bqa

Пусть a-bq=r. Тогда получим: a=bq+r, причем 0r<

Это доказательство проходит для случая b>0.

Теперь пусть b<0,тогда (-b)>0.

Тогда a=(-b)*q+r, a=b*(-q)+r, где 0r<-b, -b=, где b<0, 0r<

Таким образом, деление с остатком возможно при любых а и b0

2) Единственность:

Предположим, что это не так:

a=bq1+r1 и a=bq2+r2;

b(q1-q2)=r2-r1; где 0r1,r2<;

Где 0r2-r1<, r2>r1.

Равенство возможно, если, =>q1=q2, r1=r2.

Следовательно, деление с остатком однозначно: q-неполное частное, r-остаток.

Определение. Пусть даны натуральные числа а и b. Говорят, число а делится на число b, если существует такое натура число q, что а= 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×a , справедливого для любого натурального а, вытекает, что 1 является делителем любого натурального числа.

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

Теорема 1. Делитель b данного числа а не превышает этого числа, т.е. если а b, то b £ а.

Доказательство. Так как а 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, то, по определению отношения делимости, a a .

Теорема 3 . Отношение делимости антисимметрично, т.е. если а b и а ¹ b, то

Доказательство. Предположим противное, т. е. что b а. Но тогда а £ b, согласно теореме, рассмотренной выше.

По условию а b и а ¹ b. Тогда, по той же теореме, b £ а.

Неравенства а £ b и b £ а будут справедливы лишь тогда, когда а = b что противоречит условию теоремы. Следовательно, наше предположение неверное и теорема доказана.

Теорема 4 . Отношение делимости транзитивно, т.е. если а b и b с, то а с.

Доказательство. Так как а b, q, что а = bq, а так как b с, то существует такое натуральное число р, что b = ср. Но тогда имеем: а = bq = (ср)q = с(рд). Число pq -натуральное. Значит, по определению отношения делимости, а с .

Теорема 5. (признак делимости суммы). Если каждое из натуральных чисел а 1 , а 2 , …, а п делится на натуральное число b, то и их сумма a 1 + а 2 + ... + а п делится на это число.

Доказательство. Так как а 1 b, то существует такое натуральное число q 1 , что а 1 – bq 1 . Так как а 2 b, то существует такое натуральное число q 2 , что а 2 = bq 2 . Продолжая рассуждения, получим, что если а п b, то существует такое натуральное число q п, что а п = bq n . Эти равенства позволяют преобразовать сумму а 1 + а 2 + ... + а n в сумму вида bq 1 + bq 2 + ... + bq п. Вынесем за скобки общий множитель b, а получившееся в скобках натуральное число q 1 + q 2 + ... + q n обозначим буквой q. Тогда a 1 + а 2 + ... + а п = b(q 1 + q 2 + ... + q п) = bq, т.е. сумма a 1 + а 2 + ... + а п оказалась представленной в виде произведения числа и некоторого натурального числа q. А это значит, что сумма а 1 + a 2 + ... + а п делится на b, что и требовалось доказать.

Например, не производя вычислений, можно сказать, что сумма 175 + 360 + 915 делится на 5, так как на 5 делится каждое слагаемое этой суммы.

Теорема 6 (признак делимости разности). Если числа а 1 и a 2 делятся на b и a 1 ³ а 2 , то их разность а 1 - а 2 делится на b.

Доказательство этой теоремы аналогично доказательству признака делимости суммы.

Теорема 7 (признак делимости произведения). Если число а делится на b, то произведение вида ах, где х Î N. делится на b.

Доказательство. Так как а b, то существует такое натуральное число q, что а = bq. Умножим обе части этого равенства на натуральное число х. Тогда ах = (bq )х, откуда на основании свойства ассоциативности умножения (bq)х = b(qх) и, значит, ах = b(qх), где qх – натуральное число. Согласно определению отношения делимости, ах b, что и требовалось доказать.

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

Например, произведение 24×976×305 делится на 12, так как на 12 делится множитель 24.

Рассмотрим еще три теоремы, связанные с делимостью суммы и произведения, которые часто используются при решении задач на делимость.

Теорема 8. Если в сумме одно слагаемое не делится на число b, а все остальные слагаемые делятся на число b, то вся сумма на число b не делится.

Доказательство. Пусть s = a 1 + а 2 + ... + а п + с и известно, что

а 1 b, а 2 b,а 3 b, ...,а п b, но . Докажем, что тогда .

Предположим противное, т.е. пусть s. Преобразуем сумму 5 к виду с = 5 - (й| + а 2 + ... + а п). Так как s b по предположению, (a 1 + а 2 + + ... + а п) b согласно признаку делимости суммы, то по теореме о делимости разности с b. Пришли к противоречию с тем, что дано. Следовательно, .

Например, сумма 34 + 125 + 376 + 1024 на 2 не делится, так как 34 2,376 2, 124 2, но .

Теорема 9. Если в произведении аb множитель а делится на натуральное число т, а множитель b делится на натуральное число n , то ab делится на тп.

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

Теорема 10. Если произведение ас делится на произведение bс, причем с - натуральное число, то и a делится на b.

Доказательство. Так как ас делится на bс, то существует такое натуральное число q, что ас = (bс)q, откуда ас - (bq)с и, следовательно, a = bq, т.е a b .

Упражнения

1. Объясните, почему число 15 является делителем числа 60 и не ляется делителем числа 70.

2. Постройте граф отношения «быть делителем данного числа», заданного на множестве X = {2, 6, 12, 18, 24}. Как отражены на этом графе свойства данного отношения?

3. Известно, что число 24 - делитель числа 96, а число 96 - делите числа 672. Докажите, что число 24 делитель числа 672, не выполнять деления.

4. Запишите множество делителей числа.

а) 24; б)13; в) 1.

5. На множестве X = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} задано отношение «иметь одно и то же число делителей». Является ли оно отношением эквивалентности?

6. Постройте умозаключение, доказывающее, что:

а) число 19 является простым;

б) число 22 является составным.

7. Докажите или опровергните следующие утверждения:

а) Если сумма двух слагаемых делится на некоторое число, то и каждое слагаемое делится на это число.

б) Если одно из слагаемых суммы не делится на некоторое число, то и сумма не делится на это число.

в) Если ни одно слагаемое не делится на некоторое число, то и сумма не делится на это число.

г) Если одно из слагаемых суммы делится на некоторое число, а другое не делится на это число, то и сумма не делится на это число.

8 . Верно ли, что:

а) а т и b п Þ аb тп;

в) аb п Þ а п или b п.

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

Рассмотренные в п. 88 свойства отношения делимости позволяю доказать известные признаки делимости чисел, записанных в десяти ной системе счисления, на 2, 3, 4, 5, 9.

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

Теорема 11 (признак делимости на 2). Для того чтобы число x делилось на 2, необходимо и достаточно, чтобы его десятичная за оканчивалась одной из цифр 0, 2, 4, 6, 8.

Доказательство. Пусть число х х = а n × 10 n + a n -1 10 n -1 + ... + а 1 ×10 + а 0 , где а п, а п -1 , ..., а 1 принимают значения 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, а п ¹ 0 и а 0 принимает значения 0, 2, 4, 6, 8. Докажем, что тогда х 2.

Так как 10 2, то 10 2 2, 10 3 2,..., 10 n 2 и, значит, (а n ×10 n + а n -1 × 10 n -1 + … + a 1 × 10) 2. По условию а 0 тоже делится на 2, и поэтому число х можно рассматривать как сумму двух слагаемых, каждое из которых делится на 2. Следовательно, согласно признаку делимости суммы, число х делится на 2.

Докажем обратное: если число х делится на 2, то его десятичная запись оканчивается одной из цифр 0, 2, 4, 6, 8.

Запишем равенство х = а n ×10 n + а п-1 × 10 n -1 +... + а 1 ×10 + а 0 таком виде: a 0 = х -(а n × 10 n -1 +а n -1 ×10 n -1 + ... + а 1 × 10). Но тогда, по теореме о делимости разности, а 0 2, поскольку х 2 и (а n ×10 n + а n -1 ×10 n -1 + ... +а 1 ×10) 2. Чтобы однозначное число а 0 делилось на 2, оно должно принимать значения 0, 2, 4, 6, 8.

Теорема 12 (признак делимости на 5). Для того чтобы число х делилось на 5, необходимо и достаточно, чтобы его десятичная запись оканчивалась цифрой 0 или 5.

Доказательство этого признака аналогично доказательству признака делимости на 2.

Теорема 13 (признак делимости на 4). Для того чтобы число х делилось на 4, необходимо и достаточно, чтобы на 4 делилось двузначное число, образованное последними двумя цифрами десятичной записи числа х.

Доказательство. Пусть число х записано в десятичной системе счисления, т.е. х = a n ×10 n + а n -1 ×10 n -1 +...+ а 1 × 10 + а 0 и две последние цифры в этой записи образуют число, которое делится на 4. Докажем, что тогда х 4.

Так как 100 4, то (а n ×10 n + а n -1 ×10" n -1 + ...+ а 2 ×10 2) 4. По условию, а 1 ×10 + а 0 (это и есть запись двузначного числа) также делится на 4. Поэтому число х можно рассматривать как сумму двух слагаемых, каждое из которых делится на 4. Следовательно, согласно признаку Делимости суммы, и само число х делится на 4.

Докажем обратное, т.е. если число х делится на 4, то двузначное число, образованное последними цифрами его десятичной записи, тоже длится на 4.

Запишем равенство х = а n × 10 n +а п -1 ×10 n -1 +...+а 1 ×10+а 0 в таком виде: a 1 ×10 + a 0 = x – (a n × 10 n + a n -1 × 10 n -1 + …+a 2 ×10 2). Так как х 4 и (a n × 10 n + a n -1 ×10 n -1 +...+а 2 ×10 2) 4, то по теореме о делимости разности (a 1 × 10 + a 0 ) 4. Но выражение а 1 ×10 +а 0 есть запись двузначного числа, образованного последними цифрами записи числа х.

Например, число 157872 делится на 4, так как последние две цифры в его записи образуют число 72, которое делится на 4. Число 987641 не делится на 4, так как последние две цифры в его записи образуют число 41, которое не делится на 4.

Теорема 14 (признак делимости на 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.

Пусть число х = а п ×10 n + а п -1 ×10 n -1 +...+а 1 × 10 +а 0 и (а п + а n -1 +…+ а 1 + а 0) 9. Докажем, что тогда x 9.

Преобразуем сумму а п × 10 n + а n -1 ×10 n -1 + ... + а 1 × 10 + а 0 , прибавив и вычтя из нее выражение а п + а п-1 +...+а 1 + а 0 и записав результат в таком виде: х = (а n ×10 n - а п) + (а n -1 ×10 n -1 - а п-1 ) + ... + (а 1 × 10 1 - а 1 ) + (а 0 -а 0 ) + (а п + а n -1 + ... + а 1 + а 0 ) = а n ×(10 n - 1) + а n -1 ×(10 n -1 - 1) +...+ а 1 ×(10-1) + (а n + a n -1 +...+ а 1 + а 0).

В последней сумме каждое слагаемое делится на 9:

а n ×(10 n – 1) 9,так как (10 n -1) 9,

а п -1 ×(10 n -1 - 1) 9, так как (10 n -1 - 1) 9 и т.д.

а 1 ×(10-1) 9,таккак(10-1) 9,

(а п + а n -1 +...+ a 1 + а 0) 9 по условию.

Следовательно, х 9.

Докажем обратное, т.е. если х 9, то сумма цифр его десятичной записи делится на 9.

Равенство х = a n ×10 n + a n -1 ×10 n -1 +...+ а 1 × 10 + а 0 запишем в таком виде: а п + а п-1 + ...+ а 1 + а 0 = х - (а n ×(10 n - 1) + a n -1 × 10 n -1 - 1)+...+ a 1 × (10 - 1)). Так как в правой части этого равенства и уменьшаемое, и вычитаемое кратны 9, то по теореме о делимости разности (а п + а п-1 +...+ а, + а 0 ) 9, т.е. сумма цифр десятичной записи числа х делится на 9, что и требовалось доказать.

Например, число 34578 делится на 9, так как сумма его цифр, равная 27, делится на 9. Число 130542 не делится 9, так как сумма его цифр, равная 15,не делится на 9.

Теорема 15 (признак делимости на 3). Для того чтобы число х делилось на 3, необходимо и достаточно, чтобы сумма цифр его десятичной записи делилось на 3.

Доказательство этого утверждения аналогично доказательству признака делимости на 9.

Мы рассмотрели признаки делимости чисел на 2, 3, 4, 5, 9. Из школьного курса математики известен еще ряд других, например, на10 и 25. Конечно, этого недостаточно, чтобы решать вопросы делимости. Существует общий признак делимости для чисел, записанных в любой позиционной системе счисления, открытый в XVII веке французским математиком Паскалем. Мы рассмотрим его для случая, когда основанием системы счисления является число 10.

Теорема 16 (признак делимости Паскаля). Число

х = а n × 10 n + а n -1 × 10 n -1 + ... + а 1 × 10 + а 0 (1)

делится на число b тогда и только тогда, когда на b делится сумма а n ×r п + а п-1 ×r п-1 + ... + а 1 ×r 1 + а 0 , где r 1 , r 2 , ..., r n - остатки от деления на b разрядных единиц 10, 10 2 ,..., 10 n .

Доказательство. Разделим на b каждую из разрядных единиц числах, получим: 10 = bq 1 + r 1 , 10 2 = bq 2 + r 2 , ..., 10 n -1 = bq n -1 + r п-1 , 10 n = bq п + r n , где q 1 , q 2 , ..., q n -1 , q п - частные, а r 1 , r 2 , ..., r n -1 , r п - остатки.

Подставим в равенство (1) вместо разрядных единиц соответствующие выражения и, используя свойства сложения и умножения, выполним преобразования: х = а п ×(b ×q n + r п ) +а п-1 ×(b ×q n -1 + r n -1 ) + ... + + а 1 (b×q 1 + r 1) + а 0 = (а п ×q п + а n -1 ×q п-1 + ... + а 1 ×q 1 ) ×b + (а n ×r п + а п-1 × r п-1 +...+ а 1 ×r 1 + а 0 ). Если сумму а n ×r n + а n -1 ×r п-1 + ... + а 1 ×r 1 + а 0 обозначить буквой s , то будем иметь: х = (а n ×q n + а n -1 ×q п-1 + ... + а 1 ×q 1 ) ×b + s . Разделим s на b : s = bq + r, где 0 £ r < b. Тогда х = (а n ×q n + а n -1 ×q n -1 + ...+ а 1 ×q 1 ) ×b + (b ×q + r) = (а n ×q п +а n -1 ×q n -1 +...+ а 1 ×q 1 + q ) ×b + r. Короче: х = b ×Q + r, где Q = а n ×q п + а n -1 ×q n -1 +...+а 1 ×q 1 + q и 0 £ r < b. Равенство х = b ×Q + r означает, что r является остатком при делении х на b, причем r - число единственное согласно теореме о единственности частного и остатка при делении натуральных чисел. Таким образом, установлено, что при делении натурального числа х = а n ×10 n + а n -1 10 n -1 + ... + а 1 ×10 + а 0 на натуральное число b получается такой же остаток r, как и при делении на число b суммы s . Теорема доказана.

Используя этот признак, выведем, например, известный признак Делимости на 3 в десятичной системе счисления.

Найдем остатки от деления разрядных единиц на 3:

10 = 3×3+1(r 1 = 1);

10 2 = 3×33 + 1(r 2 = 1);

10 3 = 10 2 × 10 = (3×33 + 1) × (3×3+ 1) = 3q 3 + 1(r 3 = 1).

На основании рассмотренных случаев можно предположить, что (" n Î N) 10 n = 3q n + 1. Убедиться в истинности этого утверждения можно, если воспользоваться методом математической индукции.

Подставив полученные остатки в сумму, обозначенную при доказательстве признака делимости Паскаля буквой s, получим: s = а п ×1 +а n -1 ×r ×1 +...+ а 1 ×1 + а 0 = а n + а n -1 +...+ а 1 + а 0 . Согласно этому признаку, если данная сумма делится на 3, то и число х делится на 3 Но а п + a n -1 +…+ а 1 + а 0 - это сумма цифр в записи числа х. Получаем утверждение: если сумма цифр в десятичной записи числа делится на 3, то и само число делится на 3.

Докажем теперь, что если число х делится на 3, то сумма цифр его десятичной записи делится на 3. Запишем равенство х = a n ×10 n + а п-1 ×10 n -1 + ... + а 1 ×10 + а 0 в таком виде: a n + а n -1 +…+ а 1 + a 0 = х - (а n × (10 n -1) + а n -1 × (10 n -1 -1) +...+а 1 × (10-1)). Так как в правой части этого равенства и уменьшаемое, и вычитаемое кратны 3 то на основании признака делимости разности (а п + а п-1 + ...+ а 1 + а 0 ) 3 т.е. сумма цифр десятичной записи числа х делится на 3. Таким образов доказано, что число делится на 3 тогда и только тогда, когда сумма цифр его десятичной записи делится на 3.

Используя признак делимости Паскаля, можно доказать следующий признак делимости чисел на 11: для того чтобы число делилось на 11, необходимо и достаточно, чтобы разность между суммой его цифр стоящих на нечетных местах, и суммой цифр, стоящих на четных местах, делилась на 11. Обычно при нахождении разности из большего числа вычитают меньшее. Например, число 540309 делится на 11 так как(4 + 3 + 9)-(5 + 0 + 0) = 11, а 11:11. Число 236 не делится на 11 поскольку (2 + 6) - 3 = 5, но 5 не кратно 11.

Упражнения

1 . Выпишите из ряда чисел 132, 1050, 1114, 364, 12000 те, которые:

а) делятся на 2;

б) делятся на 4;

в) делятся на 2 и не делятся на 4;

г) делятся и на 2 и на 4.

2 . Верно ли утверждение:

а) Для того чтобы число делилось на 2, необходимо и достаточно, чтобы оно делилось на 4?

б) Для того чтобы число делилось на 2, достаточно, чтобы оно делилось на 4?

3. Из ряда чисел 72, 312,522,483,1197 выпишите те, которые:

а) делятся на 3;

б) делятся на 9;

в) делятся на 3 и не делятся на 9;

г) делятся и на 3 и на 9.

Сделайте вывод о взаимосвязи делимости на 3 и на 9. Докажите его.

4. Докажите признаки делимости на 5 и на 3.

5. Сформулируйте признак делимости на 25 и докажите его.

6. Не выполняя сложения, установите, делится ли значение выражения на 4:

а) 284 + 1440 + 113; в) 284 + 1441 + 113;

б) 284 + 1440 + 792224; г) 284 + 1441 + 113+ 164.

7 . Не выполняя вычитания, установите, делится ли разность на 9.

а) 360- 144; б) 946-540; в) 30240-97.

8. Верно ли, что для делимости числа x на 8 в десятичной системе счисления необходимо и достаточно, чтобы на 8 делилось трехзначное число, образованное последними тремя цифрами десятичной записи числа х ?