Отношения делимости. Делимость суммы, разности, произведения целых неотрицательных чисел. Понятие отношения делимости

Лекция 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, что а = 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.

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

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

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

Теорема. Любое составное число можно единственным образом представить в виде произведения простых множителей.

Например , запись 110= 2×5×11 есть представление числа 110 в виде произведения простых множителей или разложение его на простые множители.

Два разложения числа на простые множители считают одинаковыми, если они отличаются друг от друга лишь порядком множителей. Поэтому представление числа 110 в виде произведения 2×5×11 или произведения 5×2×11 есть, по существу, одно и то же разложение числа 110 на простые множители.

Раскладывая числа на простые множители, используют признаки делимости на 2, 3, 5 и др. Напомним один из способов записи разложения чисел на простые множители. Разложим, например, на множители число 90. Число 90 делится на 2. Значит, 2 есть один из про­стых множителей в разложении числа 90. Разделим 90 на 2. Число 2 запишем справа от знака равенства, а частное 45 - под числом 90. Число 45 делим на простое число 3, получаем 15. Делим 15 на 3, получаем 5. Число 5 - простое, при делении его на 5 получаем 1. Разложение на множители закончено.

При разложении числа на простые множители произведение одинаковых множителей представляют в виде степени: 90=2×3 2 ×5; 60=2 2 × 3× 5; 72=2 3 ×3 2 . Такое разложение числа на простые множители называют каноническим.

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

Действительно, предположим, что множество простых чисел конечное и исчерпывается числами 2, 3, 5, 7, ...,р, где p - самое большое простое число. Перемножим все простые числа и их произведение обозначим через а. Прибавим к этому числу 1. Каким будет полученное число а + 1 - простым или составным?

Простым число а+1 быть не может, потому что оно больше само­го большого простого числа, а по предположению таких простых чисел не существует. Но составным оно тоже быть не может: если а+1 составное, то оно должно иметь хотя бы один простой делитель q. Так как число а = 2×3×5 ×...×р также делится на это простое число q, то и разность (а + 1) - а, т.е. число 1, делится на q, что невозможно.

Итак, число а не является ни простым, ни составным, но этого тоже не может быть - всякое число, отличное от 1, либо простое, либо составное. Следовательно, наше предположение о том, что множество простых чисел конечное и есть самое большое простое число, неверно, и значит, множество простых чисел бесконечное.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Докажем сначала, что числа вида 10 п -1 делятся на 9. Действительно,

10 п -1=(9×10 п-1 +10 п–1)-1=(9×10 п-1 +9×10 п-2 +10 п–2)-1=(9×10 п-1 +9×10 п-2 +...+10)-1=

9×10 п-1 +9×10 п-2 +...+9. Каждое слагаемое полученной суммы делится на 9, значит, и число 10 п -1 делится на 9.

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

Преобразуем сумму а п ×10 п +а п-1 ×10 п–1 +…+а 1 ×10+а 0 , прибавив и вычтя из нее выражение а п +а п-1 +…+а 1 +а 0 и записав результат в таком виде:

х=(а п ×10 п -а п)+(а п-1 ×10 п–1 -а п-1)+...+(а 1 ×10-а 1)+(а 0 -а 0)+(а п +а п-1 +…+а 1 +а 0)= =а п (10 п-1 -1)+а п-1 (10 п-1 -1)+...+а 1 × (10 п-1 -1)+(а п +а п-1 +…+а 1 +а 0).

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

а п (10 п-1 - 1)M9, так как (10 п-1 -1)M9,

а п-1 (10 п-1 -1)M9, так как (10 п-1 - 1)M9 и т.д.

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

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

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

Равенство х=а п ×10 п +а п-1 ×10 п–1 +…+а 1 ×10+а 0 запишем в таком виде:

а п +а п-1 +…+а 1 +а 0 =х-(а п (10 п -1)+а п-1 (10 п–1 -1)+...+а 1 (10-1)).

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

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

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

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

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

Теорема 16 (признак делимости Паскаля ). Число х = а п × 10 п + а п-1 × 10 п –1 + …+ а 1 × 10 + а 0 делится на число b тогда и только тогда, когда на b делится сумма а п × r п + а п-1 × r п –1 + …+ а 1 × r 1 + а 0 , где r 1 , r 2 ,…,r n - остатки от деле­ния на bразрядных единиц 10, 10 2 ,..., 10 n .

Используя этот признак, выведем, например, известный признак делимости на 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. Убедиться в истинности этого утверждения можно, если воспользоваться методом математической индукции.

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

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

Например, число 540309 делится на 11, так как (4 + 3 + 9) - (5 + 0 + 0) = 11, а 11: 11. Число 236 не делится на 11, поскольку (2 + 6) - 3 = 5, но 5 не кратно 11.

4. Наименьшее общее кратное и наибольший общий делитель

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

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

Наименьшее число из всех общих кратных чисел а и b называется наименьшим общим кратным этих чисел.

Наименьшее общее кратное чисел а и b условимся обозначать К(а, b). Например, два числа 12 и 18 общими кратными являются: 36, 72, 108, 144, 180 и т.д. Число 36 - наименьшее общее кратное чисел 12 и 18. Можно записать: К(12,18) = 36.

Для наименьшего общего кратного справедливы следующие утверждения:

1. Наименьшее общее кратное чисел а и b всегда существует и является единственным.

2. Наименьшее общее кратное чисел а и b не меньше большего из данных чисел, т.е. если а > b, то К(а, b) ³ а.

3. Любое общее кратное чисел а и b делится на их наименьшее общее кратное.

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

Наибольшее число из всех общих делителей чисел а и b называется наибольшим общим делителем данных чисел. Наибольший общий делитель чисел а и b условимся обозначать D(а, b).

Например , для чисел 12 и 18 общими делителями являются числа: 1,2,3,6. Число 6 - наибольший общий делитель чисел 12 и 18. Можно записать: D(12,8)=6.

Число 1 является общим делителем любых двух натуральных чисел а и b. Если у этих чисел нет иных общих делителей, то D(а, b) = 1, а числа а и b называются взаимно простыми.

Например, числа 14 и 15 - взаимно простые, так как D (14, 15) = 1.

Для наибольшего общего делителя справедливы следующие утверждения:

1. Наибольший общий делитель чисел а и b всегда существует и является единственным.

2. Наибольший общий делитель чисел а и b не превосходит меньшего из данных чисел, т.е. если а < b, то D (а, b) £ а.

3. Наибольший общий делитель чисел а и b делится на любой общий делитель этих чисел.

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

К(а, b)×D(а,b)=а×b.

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

а) Наименьшее общее кратное двух взаимно простых чисел равно произведению этих чисел, т. е. D(а,b) = 1 ÞК(а,b)=а× b.

Например, чтобы найти наименьшее общее кратное чисел 14 и 15, достаточно их перемножить, так как D (14, 15) = 1.

б) Для того чтобы натуральное число а делилось на произведение взаимно простых чисел m и n, необходимо и достаточно, чтобы оно делилось и на m, и на n.

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

Например, так как 6=2× 3 и D(2,3)=1, то получаем признак делимости на 6: для того чтобы натуральное число делилось на 6, необходимо и достаточно, чтобы оно делилось на 2 и на 3.

Заметим, что данный признак можно применять многократно. Сформулируем, например, признак делимости на 60: для того чтобы число делилось на 60, необходимо и достаточно, чтобы оно делилось и на 4, и на 15. В свою очередь, число будет делиться на 15 тогда и только тогда, когда оно делится и на 3, и на 5. Обобщая, получаем следующий признак делимости на 60: для того чтобы число делилось на 60, необходимо и достаточно, чтобы оно делилось на 4, на 3 и на 5.

ДЕЛИМОСТЬ ЧИСЕЛ. ПРИЗНАКИ ДЕЛИМОСТИ

Рассмотрим отношение делимости в кольце целых чисел. Говорят, что число a делится на b , существует такое целое число q , для которого a = qb.
Для отношения делимости справедливы следующие свойства.
Свойство 1. Если a делится на b и b делится на c , то a делится на c.
Свойство 2. Если a 1, … , a n делятся на b , то и a 1 + … + a n делится на b.

Свойство 3. Если a 1 делится на b 1, … , a n делится на b n , то и a 1…a n делится на b 1…b n .
Имеет место следующая теорема о делении с остатком.
Теорема. Для произвольных целого числа a и натурального числа b существуют единственные числа q и r такие, что a = qb + r и 0 r < b . Число q называется неполным частным, а число r – остатком.
Приведем два доказательства этой теоремы. Первое из книги .
Доказательство 1. Пусть сначала a 0. Будем выписывать одно за другим числа a, a – b, a - 2b, … до тех пор, пока не появится отрицательное число. Пусть последним из неотрицательных членов этой последовательности будет число a – qb. Обозначая его через r, мы имеем a = qb + r. Очевидно, что r < b (иначе число r – b = a – (q + 1)b было бы неотрицательным).
Пусть теперь a < 0. Рассуждая аналогично предыдущему, будем выписывать поледовательность чисел a, a + b, a + 2b, … до тех пор, пока не появится первое неотрицательное число r (легко проверить, что r < b ). Пусть r = a + q " b . Тогда, обозначая –q" через q , получаем a = qb + r. Что и требовалось доказать.
Докажем единственность, т. е., что из a = qb + r и a = q"b + r" следует q = q" и r = r" . В этом случае имеем равенство qb + r = q"b + r" , откуда r – r" = (q" – q )b, т. е. r – r" делится на b . Но |r – r" | < b , и равенство r – r" = (q" – q )b возможно только в случае r – r" = 0. Но тогда (q" – q )b = 0 и, следовательно, q" – q = 0.
Приведем другое доказательство с геометрической интерпретацией.
Доказательство 2. Заметим, что система промежутков [qb , (q + 1)b ), где q – целое, покрывает все множество целых чисел. Число a попадает в один и только один из этих промежутков, т. е. существует единственное q , для которого qb a < qb + b. Обозначим r = a – qb. Тогда будем иметь: a = qb + r и 0 r < b .
Теорему о делении с остатком можно использовать для нахождения наибольшего общего делителя НОД(a , b ) двух натуральных чисел a и b .

Напомним, что наибольшим общим делителем двух натуральных чисел a и b называется наибольшее из чисел, являющихся делителями a и b одновременно. Докажем, что такое число существует. Действительно, если c является делителем натурального числа a , то |c | a . Следовательно, у каждого натурального числа имеется конечное число делителей. Таким образом, число общих делителей двух натуральных чисел конечно и, значит, среди них есть наибольший элемент – наибольший общий делитель.

Заметим, что из равенства a = qb + r , где 0 r < b , следует, что каждый делитель чисел a и b является делителем чисел b и r и наоборот. Следовательно, НОД(a , b ) = НОД(b , r ). Если r отлично от нуля, то разделим b на r с остатком. Получим b = q 1r + r 1, где 0 r 1 < r , и НОД(b , r ) = НОД(r , r 1). Продолжая этот процесс деления, придем к ситуации, когда r k +1 = 0, т. е. r k – 1 делится на r k и, значит, НОД(a , b ) = НОД(b , r ) = НОД(r , r 1) = … = НОД(r k -1, r k ) = r k .
Этот метод нахождения наибольшего общего делителя содержится в "Началах" Евклида и называется алгоритмом Евклида.
Пример. Найти наибольший общий делитель чисел 168 и 70.
Имеем, 168 = 270 + 28, 70 = 228 + 14, 28 = 214. Таким образом, НОД(168, 70) = 14.
Числа a и b называются равноостаточными (при делении на c ), если равны их остатки.
Для отношения равноостаточности справедливы следующие свойства.

Свойство 1. a и b равноостаточны (при делении на c ) тогда и только тогда, когда a – b делится на c .

Доказательство очевидно.
Свойство 2. Если a 1, … , a n b 1, … , b n , то a 1 + … + a n и b 1 + … + b n также равноостаточны.

Доказательство очевидно.
Свойство 3. Если a 1, … , a n соответственно равноостаточны c b 1, … , b n , то a 1… a n и b 1… b n также равноостаточны.

Доказательство проведем индукцией по n . Для n =1 утверждение очевидно. Покажем его справедливость для двух сомножителей, т. е. для n =2. Имеем a 1a 2 – b 1b 2 = (a 1 – b 1)a 2 + b 1(a 2 – b 2). Поэтому, если a 1 – b 1 делится на c и a 2 – b 2 делится на c , то и a 1a 2 – b 1b 2 делится на c . Предположим, что утверждение верно для n – 1 и докажем, что оно верно для n . Представим произведения a 1… a n и b 1… b n в виде a 1… a n = (a 1… a n -1)an и b 1… b n = (b 1… b n -1)bn . По предположению индукции, a 1… a n -1 и b 1… b n -1 равноостаточны. Применяя доказанное утверждение для двух сомножителей, получаем, что числа (a 1… a n -1)an и (b 1… b n -1)bn равноостаточны.
Следствие. Если a и b равноостаточны, то a n и b n равноостаточны.

Заметим, что равноостаточность чисел a n и b n можно доказать и непосредственно, воспользовавшись формулой a n – b n = (a – b )(an - 1 + an -2b + … + abn -2 + bn -1).
Рассмотрим примеры решения задач на использование этих свойств.
Пример 1. Выяснить, делится ли на три число 1316–
Решение. Число 13 при делении на 3 равноостаточно с 1, следовательно, 1316 вравносостаточно с 116 = 1. Число 2 равноостаточно с –1, следовательно 225 с (-1)25 = -1. Число 5 равноостаточно с –1, следовательно, 515 равноостаточно с (-1)15 = -1. Таким образом, число 1316 – 225 515 равноостаточно с 1 – (-1)(-1) = 0, т. е. данное число делится на 3.
Пример 2. Доказать, что число 1110 – 1 делится на 100.
Решение. Имеем 1110 – 1 = 10(119 + 118+ … + 1). Число 11 при делении на 10 равноостаточно с 1. Поэтому сумма чисел, стоящих в скобке правой части равноостаточна с 1 + 1 + … + 1 = 10 и, следовательно, делится на 10. Таким образом, исходное число делится на 100.
Пример 3. Доказать, что при любом натуральном n число n 3 + 11n делится на 6.
Решение. 11n при делении на 6 равноостаточно с –n . Поэтому данное число равноостаточно с n 3 – n = n (n – 1) (n + 1). В правой части стоит произведение трех последовательных натуральных чисел (или 0). Одно из них обязательно четное, а другое делится на 3. Таким образом все произведение делится на 6.
Пример 4. Доказать, что число + делится на 7.
Решение. 2222 и –4 при делении на 7 равноостаточны, 5555 и 4 также равноостаточны. Поэтому + равноостаточно с -45555 + 42222 = -42222(43333 – 1) = -42222(641111 – 1) = (641110+…+1). Так как 63 делится на 7, то и данное число делится на 7.
Пример 5. Найти остаток от деления числа на 7.
Решение. Заметим, что 1000 при делении на 7 равноостаточно с –1. Поэтому равноостаточно с –10. Последующие слагаемые также равноостаточны с –10 и, значит, вся сумма равноостаточно с числом –100, которое, в свою очередь, равноостаточно с 5. Таким образом, искомый остаток равен 5.

Пример 6. Можно ли 2006 представить как разность квадратов двух натуральных чисел?

Ответ. Нет. Если бы 2006 = a 2 – b 2 = (a – b )(a + b ), то или a – b или a + b было бы четным числом. Но тогда и другое число было бы четным, а значит, a 2 – b 2 делилось бы на 4. Но 2006 не делится на 4.

Рассмотрим теперь некоторые признаки делимости.
1. Признак делимости на 2.
Число делится на 2, если число, образованное его последней цифрой в десятичной записи делится на 2.
2. Признак делимости на 4.
Число делится на 4, если число, образованное двумя последними цифрами в его десятичной записи, делится на 4.
Доказательство вытекает из того, что число 100 и его кратные делятся на 4.
3. Признак делимости на 5.
Число делится на 5, если его последняя цифра в десятичной записи 0 или 5.
4. Признак делимости на 3.
Число делится на 3, если сумма чисел, образованных его цифрами в десятичной записи делится на 3.
Доказательство. Число 10 равноостаточно с 1. Поэтому 100 равноостаточно с 1, 1000 равноостаточно с 1 и т. д. Таким образом, число a n …a 1a 0 = a 0 + a 110 +…+a n 10n равноостаточно с a 0+a 1+ … +a n .

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

5. Признак делимости на 9.
Число делится на 9, если сумма чисел, образованных его цифрами в десятичной записи делится на 9.
Доказательство аналогично предыдущему.
6. Признак делимости на 8.
Число делится на 8, если число, образованное последними тремя цифрами в десятичной записи делится на 8.
Доказательство вытекает из того, что число 1000 и его кратные делятся на 8.
7. Признак делимости на 11.
Число делится на 11, если алгебраическая сумма чисел, образованных его цифрами в десятичной записи с чередующимися знаками делится на 11.
Доказательство. Число 10 равноостаточно с –1. Поэтому 100 равноостаточно с (-1)(-1) = 1, 1000 равноостаточно с –1 и т. д. Таким образом, число a n …a 1a 0= a 0 + a 110 +…+a n 10n равноостаточно с a 0 – a 1 + … + (-1)n a n .
В качестве примера рассмотрим число 3516282. Алгебраическая сумма его цифр равна 2 – 8 + 2 – 6 + 1 – 5 + 3 = -11. Таким образом, данное число делится на 11.
8. Объединенный признак делимости на 7, 11 и 13.
Число делится на 7, 11 или 13, если алгебраическая сумма чисел, образованных тройками цифр данного числа в десятичной записи с чередующимися знаками делится соответственно на 7, 11 или 13.
Доказательство. Заметим, что произведение чисел 7, 11 и 13 равно 1001. Поэтому число 1000 при делении на 7, 11 или 13 равноостаточно с –1. Далее поступаем как и в признаке делимости на 11.
В качестве примера рассмотрим числоЧисло 295 – 623 + 42 = -286 делится на 11 и 13, но не делится на 7. Следовательно, и данное число делится на 11 и 13, но не делится на 7.
9. Признак делимости на 37.
Число делится на 37, если сумма чисел, образованных тройками цифр данного числа в десятичной записи делится соответственно на 37.
Доказательство вытекает из того, что число 1000 при делении на 37 равноостаточно с 1.
Заметим также, что трехзначные числа 111, 222, …, 999 делятся на 37.
Легко видеть, что числа, делятся на 37.

Воспользуемся свойствами делимости для решения следующей задачи, предлагавшейся на творческом конкурсе учителей математики г. Москвы в 2004 г.
Задача. На доске написано число.... Разобьем его десятичную запись произвольным образом на два числа и сложим их. С полученными числами проделаем аналогичную операцию и так до тех пор пока не получим однозначное число. Какие однозначные числа можно получить таким образом?
Решение. Пусть десятичная запись данного числа разбита на числа x и y. Тогда исходное число имеет вид x 10...0 + y , а число, полученное в результате указанной операции равно x + y . Рассмотрим разность этих чисел: (x 10...0 + y ) - (x + y ) = 9...9x. Так как эта разность делится на 9, то исходное и полученное число имеют одинаковые остатки при делении на 9. Следовательно, каждый раз, при выполнении указанной операции этот остаток не изменяется. Непосредственная проверка показывает, что остаток от деления на 9 исходного числа равен 2. Значит, в результате указанных операций можно получить только число 2.

Упражнения

1. На какую цифру оканчивается число: а) 99999; б) 3999; в) 71000; г) 3377 + 7733?

2. Докажите, что произведение любых трех последовательных натуральных чисел делится на 6.

3. Докажите, что произведение любых пяти последовательных натуральных чисел делится на 120.

4. Найдите все натуральные числа n > 1, для которых n 3 – 3 делится на n – 1.

5. Докажите, что для любого натурального n число n 3 + 2n делится на 3.

6. Докажите, что для любого натурального n число n 5 + 4n делится на 5.

7. Докажите, что для любого натурального n число n 2 + 1 не делится на 3.

8. Докажите, что для любого натурального n число n 3 + 2 не делится на 9.

9. Докажите, что для любого четного натурального n число n 3 – 4n делится на 48.

10. Докажите, что для любого нечетного натурального n число n 6 – n 4 – n 2 + 1 делится на 128.

11. Докажите, что при любых целых a и b число a 2 + 9ab + b 2 делится на 11.

12. Докажите, что если a 2 + 9ab + b 2 делится на 11, то число a 2 – b 2 делится на 11.

13. Докажите, что если 56a = 65b , то число a + b составное.

14. Докажите, что если число 3n + 2m делится на 23, то и число 17n + 19m делится на 23.

15. Докажите, что число 31974 + 51974 делится на 13.

16. Докажите, что число 2110 – 1 делится на 2200.

17. Докажите, что для любого натурального n число n 2 – 3n + 5 не делится на 121.

18. Пусть S (n ) – сумма цифр в десятичной записи числа n . Найдите все натуральные n , для которых выполняется равенство n + S (n ) + S (S (n )) = 1993.

Литература
1. Воробьев делимости. – М.: Наука, 1980.

2. Математические досуги. – М.: Мир, 1972.

3. , Фомин математические кружки. – Киров, 1994.
4. Горбачев олимпиадных задач по математике. – М.: МЦНМО, 2004.
5. Кордемский смекалка. – М.: Наука, 1991.
6. Московские математические олимпиады 1993 – 2005 г. Под редакцией. – М.: МЦНМО, 2006.

7. Приглашение в теорию чисел. – М.: Наука, 1980.
8. и др. Избранные задачи и теоремы элементарной математики. Часть 1, арифметика и алгебра. – М – Л.: Гос. изд. техн.-теор. литературы, 1950.

Говорят, что целое число 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 получается а:

Слово «нацело» обычно опускают – для краткости.

Если а делится на b, то говорят еще, что а кратно b. Например, число 48 кратно числу 24.

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

Например, 15 делится на 3, значит, и 15∙11 делится на 3, потому что 15∙11=(3∙5)∙11=3∙(5∙11).

Эти рассуждения подходят и для общего случая. Пусть число а делится на с, тогда найдется такое натуральное число n, что a = n∙c. Рассмотрим произведение числа а и произвольного натурального числа b. a∙b = n∙(c∙b) =
= n∙(b∙c) = (n∙b)∙c. Отсюда, по определению, вытекает, что произведение a∙b тоже делится на с. Что и требовалось доказать.

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

Например, 777 делится на 111, потому что 777=7∙111, а 111 делится на 3, потому что 111 = 3∙37. Из этого следует, что 777 делится на 3, так как 777 = 3∙(37∙7).

В общем случае эти рассуждения можно повторить почти дословно. Пусть число а делится на число b, а число b делится на число с. Это означает, что найдутся такие натуральные числа n и m, что a = n∙b и b = m∙c. Тогда число а можно представить в виде: а = n∙b = n∙(m∙c) = (n∙m)∙c. Равенство а = (n∙m)∙c означает, что число а тоже делится на с.

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

Например, 100 делится на 4, потому что 100=25∙4; 36 тоже делится на 4, потому что 36 = 9∙4. Из этого следует, что 136 делится на 4, потому что

136 = 100+ 36 = 25∙4+ 9∙4 = (25+ 9)∙4 = 34∙4.

Можно также заключить, что число 64 делится на 4, потому что

64 = 100 – 36 = 25∙4 – 9∙4 =(25 – 9)∙4= 16∙4.

Докажем теорему в общем случае. Пусть каждое из чисел а и b делится на число с. Тогда, по определению, найдутся такие натуральные числа n и m, что
а = n∙c и b = m∙c. Рассмотрим сумму чисел а и b.

a + b = n∙c + m∙c = (n + m)∙c.

Отсюда следует, что а + b делится на с.

Аналогично, а – b = n∙c – m∙c = (n – m)∙c. Следовательно, а – b делится на с.

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

Например, 148 делится на 37, потому что 148 = 4∙37, а 11 не делится на 37. Очевидно, что сумма 148 + 11 и разность 148 – 11 не делятся на 37, иначе это противоречило бы свойству 3.

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

Если число оканчивается цифрой 0, то оно делится на 10 .

Например, число 4560 оканчивается цифрой 0, его можно представить в виде произведения 456∙10, которое делится на 10 (по теореме 1).

Число 4561 не делится на 10, потому что 4561 = 4560+1 – сумма числа 4560, делящегося на 10, и числа 1, не делящегося на 10 (по теореме 4).

Если число оканчивается одной из цифр 0 или 5, то оно делится на 5 .

Например, число 2300 делится на 5, потому что это число делится на 10, а 10 делится на 5 (по теореме 2).

Число 2305 оканчивается цифрой 5, оно делится на 5, так как его можно записать в виде суммы чисел, делящихся на 5: 2300 + 5 (по теореме 3).

Число 52 не делится на 5, потому что 52 = 50 + 2 – сумма числа 50, делящегося на 5, и числа 2, не делящегося на 5 (по теореме 4).

Если число оканчивается одной из цифр 0, 2, 4, 6, 8, то оно делится на 2.

Например, число 130 оканчивается цифрой 0, оно делится на 10, а 10 делится на 2, следовательно, 130 делится на 2.

Число 136 оканчивается цифрой 6, оно делится на 2, так как его можно записать в виде суммы чисел, делящихся на 2: 130 + 6 (по теореме 3).

Число 137 не делится на 2, потому что 137 = 130 + 7 – сумма числа 130, делящегося на 2, и числа 7, не делящегося на 2 (по теореме 4).

Число, делящееся на 2, называют четным.

Число, не делящееся на 2, называют нечетным .

Например, числа 152 и 790 – четные, а числа 111 и 293 – нечетные.

Если сумма цифр числа делится на 9, то и само число делится на 9 .

Например, сумма цифр 7 + 2 + 4 + 5 = 18 числа 7245 делится на 9. Число 7245 делится на 9, потому что его можно представить в виде суммы 7∙1000 +
+ 2∙100 + 4∙10 + 5 = 7 (999 + 1) + 2∙(99 + 1) + + 4∙(9 + 1) + 5 = (7∙999 + 2∙99 +
+ 4∙9) + (7 + 2 + 4 + 5), где сумма в первых скобках делится на 9, а во вторых скобках – сумма цифр данного числа – также делится на 9 (по теореме 3).

Число 375 не делится на 9, так как сумма его цифр 3 + 7 + 5=15 не делится на 9 Это можно доказать следующим образом: 375 = 3∙(99 + 1) + 7∙(9+1) + 5 =
+ (3∙99 + 7∙9) + (3 + 7 + 5), где сумма в первых скобках делится на 9, а во вторых скобках – сумма цифр числа 375 – не делится на 9 (по теореме 4).

Если сумма цифр числа делится на 3, то и само число делится на 3 .

Например, у числа 375 сумма цифр 3 + 7 + 5=15 делится на 3, и оно само делится на 3 потому, что 375 = (3∙99 + 7∙9) + (3 + 7 + 5), где сумма в первых скобках делится на 3, а во вторых скобках – сумма цифр числа 375 – также делится на 3.

Сумма цифр числа 679, равная 6 + 7 + 9 = 22, не делится на 3, и само число не делится на 3, потому что 679 = (6∙99 + 7∙9) + (6 + 7 + 9), где сумма в первых скобках делится на 3, а во вторых скобках – сумма цифр числа 679 – не делится на 3.

Примечание . Когда говорят «число оканчивается цифрой...» имеют в виду «десятичная запись числа заканчивается цифрой...»

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

Каждое натуральное число р делится на 1 и само на себя:

р:1=р, р:р=1.

Простым числом называют такое натуральное число, которое больше единицы и делится только на 1 и само на себя .

Вот первые десять простых чисел:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

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

Вот все составные числа, меньшие 20:

4, 6, 8, 9, 10, 12, 14, 15, 16, 18.

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

Простых чисел бесконечно много, есть первое число – 2, но нет последнего простого числа.

Делители натурального числа

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

Например, делителями числа 13 являются числа 1 и 13, делителями числа 4 – числа 1, 2, 4, а делителями числа 12 – числа 1, 2, 3, 4, 6, 12.

Каждое простое число имеет только два делителя – единицу и само себя, а каждое составное число, кроме единицы и себя, имеет и другие делители.

Если делитель – простое число, то его называют простым делителем. Например, число 13 имеет простой делитель 13, число 4 – простой делитель 2, а число 12 – простые делители 2 и 3.

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

28 = 2∙2∙7 = 2 2 ∙7;

81 = 3∙3∙3∙3 = З 4 ;

100 = 2∙2∙5∙5 = 2 2 ∙5 2 .

Правые части полученных равенств называют разложением на простые множители чисел 28, 22, 81 и 100.

Разложить данное составное число на простые множители – значит представить его в виде произведения различных его простых делителей или их степеней.

Покажем, как можно разложить число 90 на простые множители.

1) 90 делится на 2, 90:2 = 45;

2) 45 не делится на 2, но делится на 3, 45:3= 15;

3) 15 делится на 3, 15:3 = 5;

4) 5 делится на 5, 5:5 = 1.

Таким образом, 90 = 2∙45 = 2∙3∙15 = 2∙3∙3∙5.

Наибольший общий делитель

Число 12 имеет делители 1, 2, 3, 4, 12. Число 54 имеет делители 1, 2, 3, 6, 9, 18, 27, 54. Мы видим, что числа 12 и 54 имеют общие делители 1, 2, 3, 6.

Наибольшим общим делителем чисел 12 и 54 является число 6.

Наибольший общий делитель чисел а и b обозначают: НОД (а, b).

Например, НОД (12, 54) = 6.

Наименьшее общее кратное

Число, делящееся на 12, называется кратным числу 12. Числу 12 кратны числа 12, 24, 36, 48, 60, 72, 84, 96, 108 и т.д. Числу 18 кратны числа 18, 36, 54, 72, 90, 108, 126 и т. д.

Мы видим, что имеются числа, кратные одновременно 12 и 18. Например, 36, 72, 108, ... . Эти числа называются общими кратными чисел 12 и 18.

Наименьшим общим кратным натуральных чисел а и b называют наименьшее натуральное число, делящееся нацело на а и b. Это число обозначают: НОК (а, b).

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

Найдем НОК(18, 24).

I способ. Будем выписывать числа, кратные 24 (большему из данных чисел), проверяя, делится ли каждое из них на 18: 24∙1=24 – не делится на 18, 24∙2 = 48 – не делится на 18, 24∙3 = 72 – делится на 18, поэтому НОК (24, 18) =
= 72.

II способ. Разложим числа 24 и 18 на простые множители: 24 = 2∙2∙2∙3,
18 = 2∙3∙3.

НОК(24, 18) должно делиться и на 24, и на 18. Поэтому искомое число содержит все простые делители большего числа 24 (т. е. числа 2, 2, 2, 3) и еще недостающие множители из разложения меньшего числа 18 (еще одно число 3). Поэтому НОК(18, 24) = 2∙2∙2∙3∙3 = 72.

Так как взаимно простые числа не имеют общих простых делителей, то их наименьшее общее кратное равно произведению этих чисел. Например, 24 и 25 – взаимно простые числа. Поэтому НОК (24, 25) = 24∙25 = 600.

Если одно из двух чисел делится нацело на другое, то наименьшее общее кратное этих чисел равно большему из них. Например, 120 делится нацело на 24, следовательно, НОК (120, 24)= 120.

Целые числа

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

В этой разделе будут введены новые числа – целые отрицательные .

Целые отрицательные числа

Базовый пример из жизни – термометр. Предположим, он показывает температуру 7° тепла. Если температура понизится на 4°, то термометр будет показывать 3° тепла. Уменьшению температуры соответствует действие вычитания: 7 – 4 = 3. Если температура понизится на 7°, то термометр покажет 0°: 7 – 7 = 0.

Если же температура понизится на 8°, то термометр покажет –1° (1° мороза). Но результат вычитания 7 – 8 нельзя записать с помощью натуральных чисел и нуля, хотя он имеет реальный смысл.

Отсчитать в ряду неотрицательных целых чисел от числа 7 влево 8 чисел нельзя. Чтобы действие 7 – 8 стало выполнимым, расширим ряд неотрицательных целых чисел. Для этого влево от нуля запишем (справа налево) по порядку все натуральные числа, добавляя к каждому из них знак «–», показывающий, что это число стоит слева от нуля.

Записи –1, –2, –3, ... читают «минус 1», «минус 2», «минус 3» и т. д.:

–5, –4, –3, –2, –1, 0, 1, 2, 3, 4, 5, ... .

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

Справа от числа 0 в этом ряду расположены числа, которые называют натуральными или целыми положительными.