Делимость - одно из основных понятий, изучаемых в теории чисел (см. Чисел теория). Говорят, что целое число а делится на целое b ≠ 0, если частное a/b является целым, т. е. существует такое целое число c, что a = bc. Например, 54 делится на 6, так как 54 = 6 9; 273 делится на 21, так как 273 = 21 13. Из определения делимости следует, что число 0 делится на любое число, отличное от нуля.

Часто утверждение о делимости числа а на число b выражают другими равнозначными словами: a кратно b, b - делитель а или же b делит a.

Всякое целое число а делится по крайней мере на четыре числа a, -a, 1, -1. Натуральное число а называется простым, если никаких других делителей оно не имеет.

Приведем несколько свойств делимости:

а) если числа a и b делятся на с, то и числа a + b, a - b делятся на c;

б) если a делится на b и c - произвольное целое число, то ac делится на bc;

в) если a делится на b и b - на c, то а делится на c.

Зная разложения чисел a и b на простые множители, можно легко выяснить, делится ли a на b. Для того чтобы число a делилось на число b, необходимо и достаточно, чтобы каждый простой множитель, входящий в разложение числа b, входил и в разложение числа a; причем если простой множитель встречается k раз в разложении числа b, то он должен встретиться не менее k раз и в разложении числа a.

Если целые числа a и b заданы своими записями в десятичной системе счисления, то, разделив «в столбик» первое число на второе, мы найдем их частное, а значит, сможем ответить на вопрос, делится ли a на b.

Уже давно были найдены признаки делимости чисел, которые позволяют в некоторых случаях быстро установить делимость одного числа на другое, не прибегая к непосредственному делению «в столбик». Среди этих признаков практически наиболее удобны следующие (связанные с записью числа в десятичной системе):

а) для делимости на 2 нужно, чтобы последняя цифра числа делилась на 2;

б) для делимости на 3 нужно, чтобы сумма цифр числа делилась на 3;

в) для делимости на 4 нужно, чтобы число, записанное двумя последними цифрами, делилось на 4;

г) для делимости на 5 нужно, чтобы последняя цифра была 0 или 5;

д) для делимости на 8 нужно, чтобы число, записанное тремя последними цифрами, делилось на 8;

е) для делимости на 9 нужно, чтобы сумма цифр делилась на 9;

ж) для делимости на 10 нужно, чтобы последняя цифра была 0;

з) для делимости на 11 нужно, чтобы разность между суммой цифр, стоящих на четных местах, и суммой цифр, стоящих на нечетных местах, делилась на 11.

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

Отношение делимости и его свойства

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

Как известно, вычитание и деление на множестве натуральных чисел выполнимо не всегда. Вопрос о существовании разности натуральных чисел а и b решается просто - достаточно установить (по записи чисел), что b < а. Для деления такого общего и простого признака нет. Поэтому в математической науке с давних пор пытались найти такие правила, которые позволили бы по записи числа а узнавать, делится оно на число b или нет, не выполняя непосредственного деления а на b. В результате этих поисков были открыты не только некоторые признаки делимости, но и другие важные свойства чисел; познакомимся с некоторыми из них.

В начальных курсах математики делимость натуральных чисел, как правило, не изучается, но многие факты из этого раздела математики неявно используются. Например, признак делимости суммы, разности и произведения на число тесно связаны с правилами деления суммы, разности и произведения на число, изучаемыми в начальных классах. В ряде курсов изучаются признаки делимости чисел на 2, 3, 5 и другие.

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

Отношение делимости и его свойства

Определение. Пусть даны натуральные числа а и b. Говорят, что число а делится на число b, если существует такое натуральное число q, что a - bq.

В этом случае число b называют делителем числа а, а число а - кратным числа b.

Например, 24 делится на 8, так как существует такое q = 3, что 24 = 8·3. Можно сказать иначе: 8 - это делитель числа 24, а 24 есть кратное числа 8.

В том случае, когда а делится на b, пишут: а b. Эту запись часто читают и так: «а кратно b».

Заметим, что понятие «делитель данного числа» следует отличать от понятия «делитель», обозначающего то число, на которое делят. Например, если 18 делят на 5, то число 5-делитель, но 5 не является делителем числа 18. Если 18 делят на 6, то в этом случае понятия «делитель» и «делитель данного числа» совпадают.

Из определения отношения делимости и равенства а = 1·а, справедливого для любого натурального а, вытекает, что 1 является делителем любого натурального числа.

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

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

Доказательство. Так как а b, то существует такое q N, что a=bq и, значит, a-b = bq-b = b· (q- 1). Поскольку а N, то q≥l. Тогда b· (q- 1) ≥0 и, следовательно, b≤a.

Из данной теоремы следует, что множество делителей данного числа конечно . Назовем, например, все делители числа 36. Они образуют конечное множество {1, 2, 3,4, 6,9, 12, 18, 36}.

В зависимости от числа делителей среди натуральных чисел различают простые и составные числа.

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

Например, число 13 - простое, поскольку у него только два делителя: 1 и 13.

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

Так число 4 составное, у него три делителя: 1, 2 и 4.

Число 1 не является ни простым, ни составным числом в связи с тем, что оно имеет только один делитель.

Чисел, кратных данному числу, можно назвать как угодно много, - их бесконечное множество. Так, числа, кратные 4, образуют бесконечный ряд: 4, 8, 12, 16, 20, 24, ..., и все они могут быть получены по формуле а = 4q, где q принимает значения 1, 2, 3,....

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

Теорема 2. Отношение делимости рефлексивно, т.е. любое натуральное число делится само на себя.

Доказательство . Для любого натурального а справедливо равенство а = а·1. Так как 1 N, то, по определению отношения делимости, а а.

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

если a b и а≠b, то .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Доказательство . Пусть число х записано в десятичной системе счисления, т.е. х = а n ·10 n + a n-1 ·10 n-1 + ... + а 1 ·10 + а 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 2, 10 3 2, ..., 10 n 2 и, значит, (а n ·10 n + a n-1 ·10 n-1 + ... + а 1 ·10) 2. По условию а 0 тоже делится на 2, и поэтому число х можно рассматривать как сумму двух слагаемых, каждое из которых делится на 2. Следовательно, согласно признаку делимости суммы, число х делится на 2.

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

Запишем равенство х = а n ·10 n + a n-1 ·10 n-1 + ... + а 1 ·10+а в таком виде:

а о = х-(а n ·10 n + a n-1 ·10 n-1 + ... + а 1 ·10). Но тогда, по теореме о делимости разности, а о 2, поскольку х 2 и (а n ·10 n + a 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 делилось двузначное число, образованное последними двумя цифрами десятичной записи числа х.

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

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

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

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

Отношение делимости и его свойства Определение Пусть а и b N. Число а делится на число b, если существует такое натуральное число q, что а = bq а b q N , что а = bq В этом случае число b называют делителем числа а, а число а – кратным числа b 24 8, т. к. 3 N , что 24 = 8 3

Различают понятия «b делитель числа а» и «b – делитель» В выражении « 25: 8» число 8 делитель (как компонент деления), а в выражении « 24: 8» число 8 делитель числа 24 Теорема 1 1 является делителем любого натурального числа т. к. для а N а = 1· а Теорема 2 Если а b, то b а

Доказательство Так как а b, то q N, что а = bq а – b = bq – b = b · (q – 1). Поскольку а N, то q 1. Тогда b · (q – 1) 0, т. е. разность а – b 0 b а Из Теоремы 2 следует: Множество делителей данного числа а конечно – все делители меньше числа b Все делители числа 36 образуют конечное множество {1, 2, 3, 4, 6, 9, 12, 18, 36}

Свойства отношения делимости Теорема 3 (а N) а а, т. е. отношение делимости рефлексивно Доказательство (а N) а = а · 1. Так как 1 N делимости, а а

Теорема 4 (а b и а b) b а, т. е. отношение делимости антисимметрично Доказательство (от противного) Пусть неверно, что b а а b (по теореме 2) По условию а b и а b b а (по теореме 2) Неравенства а b и b а будут справедливы лишь тогда, когда а = b, что противоречит условию теоремы. Следовательно, наше предположение неверно

Теорема 5 а b и b с а с, т. е. отношение делимости транзитивно Доказательство Так как а b q N, что а = bq Так как b с р N, что b = ср а = bq = (ср)q = c(pq). Число pq N. Значит, по определению отношения делимости, а с

Теорема 6 (признак делимости суммы) Если каждое из натуральных чисел а 1, а 2, . . . , аn делится на натуральное число b, то и их сумма а 1 + а 2 +. . . + аn делится на это число Доказательство Так как а 1 b, то q 1 N, что а 1= b q 1 Так как а 2 b, то q 2 N, что а 2= b q 2 ……………………. Так как аn b, то qn N, что аn= b qn

а 1 + а 2 +. . . + аn = b (q 1 + q 2 +. . . + qn) = bq q = q 1 + q 2 +. . . + qn , т. е. q N т. е. сумма а 1 + а 2 +. . . + аn есть произведение числа b и натурального числа q. Следовательно, сумма а 1 + а 2 +. . . + аn делится на b Пример Сумма (175 + 360 + 915) 5, т. к. 175 5 и 360 5 и 915 5

Теорема 7 (признак делимости разности) Если а 1 b, а 2 b и а 1 > а 2, то (а 1 – а 2) b Доказательство аналогично доказательству теоремы 6

Теорема 8 (признак делимости произведения) Если а b, то ах b, где х N Доказательство Так как а b, то q N, что а = bq на х ах = (bq)x = b(qx), т. е. ах = b(qx), где qx N по определению отношения делимости ax b

Из теоремы 8 следует, что если один из множителей произведения делится на натуральное число b, то и все произведение делится на b Пример Произведение (24 · 976 · 305) 12, так как 24 12 Теорема 9 Если в сумме одно слагаемое не делится на число b, а все остальные слагаемые делятся на число b, то вся сумма на число b не делится

Пример Сумма (34 + 125 + 376 + 1024) 2, так как 34 2, 376 2, 124 2, но 125 2 Теорема 10 Если в произведении ab множитель а делится на натуральное число m, а множитель b делится на натуральное число n, то ab делится на mn Доказательство основано на теореме 8

Теорема 11 Если ас bс и с N, то а b Доказательство Так как ас bс, то q N такое, что ас = (bc)q ас = (bq)c, следовательно, а = bq, т. е. a b

Признаки делимости Теорема 12 (признак делимости на 2) Для того чтобы число х делилось на 2, необходимо и достаточно, чтобы его десятичная запись оканчивалась одной из цифр 0, 2, 4, 6, 8 Доказательство 1) Пусть число х записано в десятичной системе счисления: х = аn · 10 n + аn-1 · 10 n – 1 +. . . + а 1 · 10 + а 0 , где аn, аn-1, . . . а 1 принимают значения 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, аn 0 и а 0 принимает значения 0, 2, 4, 6, 8

х = аn· 10 n+аn-1· 10 n -1+. . . + а 1· 10 + а 0 = = (аn· 10 n-1 + аn-1· 10 n -2+. . . + а 1) · 10 + а 0 делится на 2, т. к. 10 2 а 0 тоже делится на 2, т. к. по условию заканчивается на 0, 2, 4, 6 или 8

2) Докажем, что, если число х 2, то а 0 приминимает значения 0, 2, 4, 6 или 8 х = аn· 10 n + аn-1· 10 n -1 +. . . + а 1· 10 + а 0 = х – (аn· 10 n + аn-1· 10 n -1+. . . + а 1· 10) делится на 2, т. к. 10 2 Число х 2 по условию а 0 2

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

Теорема 14 (признак делимости на 4) Для того чтобы число х делилось на 4, необходимо и достаточно, чтобы на 4 делилось двузначное число, образованное последними двумя цифрами десятичной записи числа х Доказательство 1) х = аn· 10 n+аn-1· 10 n -1+. . . а 2 102 + а 1· 10 + а 0 = = (аn· 10 n-2 + аn-1· 10 n -3+. . . + а 2) · 102 + а 1 10 + а 0 делится на 4, т. к. 102 4 делится на 4 по условию

2) Докажем, что, если число х 4, то (а 1 10 + а 0) образует двузначное число, которое делится на 4 х = аn· 10 n + аn-1· 10 n -1+. . . + а 2 10 2 + а 1· 10 + а 0 = х – (аn· 10 n + аn-1· 10 n -1+. . . + а 2 10 2) делится на 4, т. к. 102 4 Число х 4 по условию (а 1· 10 + а 0) 4

Пример 1) Число 1 5 7 8 7 2 4 72 4 2) Число 9 8 7 6 4 1 4 41 4

Теорема 15 (признак делимости на 9) Для того чтобы число х делилось на 9, необходимо и достаточно, чтобы сумма цифр его десятичной записи делилось на 9 Доказательство 1) Докажем, что (10 n – 1) 9

10 n – 1 = 10 10 n-1 – 1 = (9 + 1) 10 n-1 – 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 + 10 n-2 +. . . + 9 = 9 · (10 n-1 + 10 n-2 + 10 n-2 +. . . + 1) делится на 9 (10 n – 1) 9

2) К десятичной записи числа х: х = аn · 10 n + аn-1 · 10 n – 1 +. . . + а 1 · 10 + а 0 прибавим и вычтем выражение (аn+ аn-1+. . . + а 0) Получим: х = (аn· 10 n – аn) + (аn-1 · 10 n-1– аn-1) +. . . + (а 1· 10 – а 1) + (а 0 – а 0) + (аn +аn-1 +. . . + а 1 + а 0) = делится на 9, т. к. каждое слагаемое содержит множитель (10 n – 1) = аn· (10 n – 1) + аn-1· (10 n-1 – 1)+. . . + а 1· (10 – 1) + + (аn + аn-1 +. . . + а 1 + а 0) делится на 9 по условию

3) Докажем, что, если число х 9, то (аn+ аn-1+. . . + а 0) 9 Равенство запишем в виде: х = (аn· 10 n – аn) + (аn-1 · 10 n-1– аn-1) +. . . + (а 1· 10 – а 1) + + (а 0 – а 0) + (аn +аn-1 +. . . + а 1 + а 0) аn +аn-1 +. . . + а 1 + а 0 = = х – (аn· (10 n – 1) + аn-1 ·(10 n-1 – 1) +. . . + а 1· (10 – 1)) В правой части этого равенства уменьшаемое и вычитаемое кратны 9, то по теореме о делимости разности (аn +аn-1 +. . . + а 1 + а 0) 9

Пример Число 34578 9, так как 3 + 4 + 5 + 7 + 8 = 27, 27 9 Число 130542 не делится 9, так как 1 + 3 + 0 + 5 + 4 + 2 = 15, 15 не делится на 9

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

Наименьшее общее кратное и общий делитель наибольший Определение Общим кратным натуральных чисел а и b называется число, которое кратно каждому из данных чисел Наименьшее число из всех общих кратных чисел а и b называется наименьшим общим кратным этих чисел Наименьшее общее кратное чисел а обозначают К(а, b) и b

Общими кратными чисел 12 и 18 являются: 36, 72, 108, 144, 180 … Число 36 – наименьшее общее кратное чисел 12 и 18 Пишут: К(12, 18) = 36 Свойства К(а, b) 1. Наименьшее общее кратное чисел а и b всегда существует и является единственным 2. Наименьшее общее кратное чисел а и b не меньше большего из данных чисел, т. е. если а > b, то К(а, b) > а 3. Любое общее кратное чисел а и b делится на их наименьшее общее кратное

Определение Общим делителем натуральных чисел а и b называется число, которое является делителем каждого из данных чисел Наибольшее число из всех общих делителей чисел а и b называется наибольшим общим делителем данных чисел. Наибольший общий делитель чисел а и b обозначают D(a, b) Общими делителями чисел 12 и 18 являются числа: 1, 2, 3, 6 Число 6 – наибольший общий делитель чисел 12 и 18 Пишут: D(12, 18) = 6

Число 1 является общим делителем любых двух натуральных чисел а и b Определение D(a, b) = 1, то числа а и b называются взаимно простыми Пример Числа 14 и 15 – взаимно простые, так как D(14, 15) = 1

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

Произведение наименьшего общего кратного и наибольшего общего делителя чисел а и b равно произведению этих чисел, т. е. К(a, b) · D(a, b) = а · b Следствия 1) Наименьшее общее кратное двух взаимно простых чисел равно произведению этих чисел, т. е. D(a, b) = 1 K(a, b) = a · b Например, К(14, 15) = 14 15, так как D (14, 15) = 1

2) Признак делимости на составное число: Для того чтобы натуральное число а делилось на произведение взаимно простых чисел m и n, необходимо и достаточно, чтобы оно делилось и на m, и на n Пример 6 = 2 · 3 и D(2, 3) = 1, то получаем признак делимости на 6: для того, чтобы натуральное число делилось на 6, необходимо и достаточно, чтобы оно делилось на 2 и на 3 Данный признак можно применять многократно

Задача Сформулируйте признак делимости на 60 Для того, чтобы число делилось на 60, необходимо и достаточно, чтобы оно делилось и на 4, и на 15, где D(4, 15) = 1. В свою очередь, число будет делиться на 15 тогда и только тогда, когда оно делится и на 3, и на 5, где D(3, 5) = 1 Таким образом признак делимости на 60: Для того, чтобы число делилось на 60, необходимо и достаточно, чтобы оно делилось на 4, на 3 и на 5

3) Частные, получаемые при делении двух данных чисел на их наибольший общий делитель, являются взаимно простыми числами Например, проверим, является ли число 12 наибольшим общим делителем чисел 24 и 36. Для этого разделим 24 и 36 на 12. Получим соответственно числа 2 и 3, где D (2, 3) = 1, т. е. 2 и 3 являются взаимно простыми. Следовательно, D(24, 36) = 12

Простые и составные числа Определение Простыми называются числа, которые делятся только на себя и на единицу Определение Составными называются числа, которые имеют более двух делителей Единица не относится ни к простым, ни к составным числам Числа 2, 5, 17, 61 и т. д. – простые, числа 4, 25, 102 и т. д. – составные

Свойства простых чисел 1. Если простое число p делится на некоторое натуральное число n, где n ≠ 1, то оно совпадает с n Действительно, если p ≠ n, то число р имеет три делителя: 1, n и p, а тогда оно не простое 2. Если p и q – простые числа и р ≠ q, то p не делится на q Если p – простое число, то оно имеет только два делителя: 1 и р. По условию q тоже простое, значит q ≠ 1 и q ≠ р Следовательно, q не является делителем числа p Числа 17 и 11 – простые, значит 17 не делится на 11

3. Если натуральное число a не делится на простое число p, то а и p взаимно просты, т. е. D (а, р) = 1 Например, 25 не делится на 7, значит 25 и 7 – взаимно просты 4. Если произведение двух натуральных чисел а и b делится на простое число p, то хотя бы одно из них делится на p Например, 25 39 = 975. Число 975 делится на 3, т. к. 9 + 7 + 5 = 21. Но число 25 не делится на 3, следовательно, 39 делится на 3

5. Если натуральное число больше 1, то оно имеет хотя бы один простой делитель Действительно, все простые числа имеют простые делители – сами эти числа, составные числа можно раскладывать на множители до тех пор, пока они не станут простыми числами Например, 240 > 1, значит имеет хотя бы один простой делитель, это число 2 (или 5)

6. Наименьший простой делитель составного числа а не превосходит Доказательство Пусть а – составное число, а р – его наименьший простой делитель. Тогда а = рb. При этом р b, т. к. иначе простой делитель числа b был бы меньше, чем р, а тогда а имело бы простые делители, меньшие чем р. Умножим обе части неравенства на р. Получим, р2 рb рb = а. Поэтому, р2 а, т. е. р

Теорема – Основная теорема арифметики Любое составное число можно единственным образом представить в виде произведения простых множителей где а 1, а 2, а 3, …, аk – простые числа, n 1, n 2, n 3, … , nk – показатели, с которыми входят простые числа в разложение числа х Такое разложение числа на простые множители называют каноническим

Пример 110 = 2 · 5 · 11 – произведение простых множителей есть разложение числа 110 на простые множители Два разложения числа на простые множители считают одинаковыми, если они отличаются друг от друга лишь порядком множителей 110 = 2 · 5 · 11 = 5 · 11 · 2 - одно и то же разложение

Способ разложения числа на простые множители 90 2 45 3 15 3 5 5 только простые числа 1 Таким образом, 90 = 2 · 3 · 5 · 1 = 2 · 32 · 5 60 = 22 · 3· 5; 72 = 23 · 32

Решето Эратосфена Эратосфеном (III в. до н. э.) был придуман способ получения простых чисел, не превышающих натурального числа а (решето Эратосфена) Найдем все простые числа до 50

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

Бесконечность множества простых чисел Теорема, доказанная Евклидом Множество простых чисел бесконечно Доказательство Пусть множество простых чисел конечно и состоит из чисел: 2, 3, 5, 7, . . . , p, где р – наибольшее простое число. Найдем произведение всех простых чисел 2 3 5 7 . . . p = а. Прибавим к а единицу. Число а + 1 простым не является, т. к. а + 1 > р наибольшего простого числа (по предположению)

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

Способы нахождения наибольшего общего делителя и наименьшего общего кратного чисел 1 способ Чтобы найти НОД двух чисел, можно перечислить все их общие делители и выбрать из них наибольший Пример Даны числа 120 и 486 Делители числа 120: 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120 Делители числа 486: 1, 2, 3, 6, 9, 27, 54, 81, 162, 243, 486 Общие делители: 1, 2, 3, 6 Наибольшим общим делителем является число 6

Чтобы найти НОК двух чисел, можно перечислить некоторые их общие кратные и выбрать из них наименьший Пример Даны числа 60 и 48 Кратные числа 60: 60, 120, 180, 240, 300, 360, 420, 480, 540, . . . Кратные числа 48: 48, 96, 144, 192, 240, 288, 336, 384, 432, 480, . . . Общие кратные чисел 60 и 48: 240, 480, . . . Наименьшим общим кратным является число 240

2 способ – основан на разложении данных чисел на простые множители Алгоритм нахождения наибольшего общего делителя данных чисел: 1) представить каждое данное число в каноническом виде; 2) образовать произведение общих для всех данных чисел простых множителей, каждый с наименьшим показателем, с каким он входит во все разложения данных чисел; 3) найти значение этого произведения – оно и будет наибольшим общим делителем данных чисел

Пример Даны два числа 3600 и 288 Каноническое разложение этих чисел: 3600 = 24 32 52; D(3600, 288) = 24 32 = 144 288 = 25 32

Алгоритм нахождения наименьшего общего кратного данных чисел: 1) представить каждое данное число в каноническом виде; 2) образовать произведение всех простых множителей, находящихся в разложениях данных чисел, каждый с наибольшим показателем, с каким он входит во все разложения данных чисел; 3) найти значение этого произведения – оно и будет наименьшим общим кратным данных чисел

Пример Даны два числа 3600 и 288 Каноническое разложение этих чисел: 3600 = 24 32 52; 288 = 25 32 K(3600, 288) = 25 32 52 = 7200

3 способ – алгоритм Евклида Алгоритм Евклида основан на следующих утверждениях: 1. Если а делится на b, то D(a, b) = b 2. Если a = bq + r и r

Src="https://present5.com/presentation/3/71306524_41475257.pdf-img/71306524_41475257.pdf-55.jpg" alt="Пусть а > b Если а делится на b, то D(a, b) = b"> Пусть а > b Если а делится на b, то D(a, b) = b Если при делении а на b, получается остаток r, то а = bq + r и D(a, b) = D(b, r) Найдем D(b, r) Если b делится на r, то D(b, r) = r и тогда D(a, b) = r Если при делении b на r получается остаток r 1, то b = rq 1 + r 1, и тогда D(r, r 1) = D(b, r) = D(a, b) Найдем D(r, r 1)

Продолжая описанный процесс, получаем все меньшие и меньшие остатки. В результате получим остаток, на который будет делиться предыдущий остаток. Этот наименьший, отличный от нуля, остаток и будет наибольшим общим делителем чисел а и b Найти НОК и НОД чисел можно по формуле: К(a, b) · D(a, b) = а · b К(а, b) = а · b: D(a, b) = а · b: К(а, b)

Пример Найдите по алгоритму Евклида наибольший общий делитель чисел 2585 и 7975 = 2585 3 + 220 2585 = 220 11 + 165 220 = 165 1 + 55 165 = 55 3 + 0 Значит, D(7975, 2585) = 55, К(7975, 2585) = = (7975 2585) : 55 = = 20615375: 55 = 374825

7975 7555 2585 220 385 220 165 165 0 55 3 165 1 220 11 2585 3

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

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

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

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

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