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

Муниципальное общеобразовательное учреждение

«Ялгинская СОШ»

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

Выполнила: Синицына Н.,

ученица 7А класса

                                                       Руководитель: Квачадзе С.А.,

учитель математики

Саранск 2013

Содержание

Введение…………………………………………………………………...3 – 4

1. Обзор литературы……………………………………………....5 – 11

1.1 Целые числа и действия над ними …………………….5 – 6

1.2 Теорема о делимости ………………………………………...…..7

1.3 Сравнение ……………………………………………………………...8

1.4 Периодичность остатков при возведении в степень………………………………………………………………………....9

2. Методика исследования……………………………............12 – 17

3. Экспериментальная часть…………………………………...18 – 25

1.  Доказательство признаков делимости на 4, 13, 17, 19,

37,41,101…………………………………………………………………….…....18

2.  Выведение признаков делимости на 12, 18, 14……..…….....25

Заключение.…………………………………………………………...........26

Литература…………………………………………………………..…........28

Введение

Математика – самая древняя наука, она была и остается необходимой людям. Слово «математика» греческого происхождения. Оно означает «наука», «размышление». В древности полученные знания, открытия часто старались сохранить в тайне. Например, в школе Пифагора запрещено было делиться своими знаниями с непифагорейцами. За нарушения этого правила один из учеников, требовавший свободного обмена знаниями, - Гиппас был изгнан из школы. Сторонников Гиппаса стали называть математиками, то есть приверженцами науки. Теперь мы все математики.

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

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

Цель данной работы изучить основные понятия делимости чисел.

Делимость чисел рассматривается как отношение на множестве целых чисел, то есть как реализация общего и абстрактного понятия.

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

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

  В 6 классе мы изучили признаки делимости на 10, 2, 5, 3, и 9. У меня возник вопрос: «А существует ли признак делимости на 4, 6, 7, 8 и т. д.?» И целью настоящей работы стали изучения признаков делимости на числа: 4, 6, 7, 11, 12, 13, 14, 15, 18, 17, 19, 37, 41, 101. Для того чтобы вывести эти признаки делимости, мы изучили теоремы о делимости, что такое сравнения и их свойства, а также периодичность остатков при возведении в степень.

Обзор литературы

1.1. Целые числа и действия над ними

Множество целых чисел состоит из натуральных чисел 1, 2, 3, ..., нуля 0 и отрицательных целых чисел -1, -2, -3, .... В этом множестве всегда выполнимы операции сложения и вычитания. Иначе говоря, если т и п — целые числа, то их сумма т+п тоже является целым числом. Далее, для любых двух целых чисел т, п существует (и притом только одно) число х, удовлетворяющее уравнению п - х = т; это число называется разностью чисел т и n и обозначается через   т - п. Разность любых двух целых чисел тоже является целым числом.

В множестве целых чисел всегда выполнимо и умножение, т. е. если т и п — целые числа, то их произведение тп тоже является целым числом. Однако деление (действие, обратное умножению) выполнимо в множестве целых чисел не всегда. Результат деления числа а на число b≠0 (частное от деления а на b) обозначается через а:b (или ). Напомним, что частным от деления числа а на число b≠0 называется число х, удовлетворяющее уравнению

bx=а,

такое число существует, и притом только одно. Однако частное от деления одного целого числа на другое не всегда является целым числом. Например, частные 5:2,                    2 : 5, (- 40): 7, (-30): (-21) целыми числами не являются.

Это и означает, что деление не всегда выполнимо в множестве целых чисел: частное от деления целого числа а на целое число b≠0 может оказаться лежащим за пределами множества целых чисел, а в самом множестве целых чисел не найдется такого числа, которое мы могли бы назвать частным от деления а на b .

Встречаются, конечно, и такие случаи, когда частное от деления одного целого числа на другое опять является целым числом. Например; 6:(-2) = - 3, 36:12 = 3, (-5):5 = -1.

Определение. Если а и b (где b≠0) — такие целые числа, что частное а:b тоже является целым числом, то говорят, что число а делится на b.

Можно сказать и иначе: целое число а делится на целое число b≠0, если найдется такое целое число к, что а = кb. Этим определением делимости мы чаще всего и будем пользоваться в дальнейшем. Так как мы всюду будем говорить только о целых числах, то нередко для краткости будем писать просто «число», всегда подразумевая под этим целое число.

Подчеркнем, что о частном а : b мы можем говорить лишь при b # 0. При b = 0 частное a: b не определено, т. е. выражениям а : 0, не придается никакого смысла. Короче, на нуль делить нельзя.

Напротив, при а = 0 (и любом b≠0 ) частное а : b определено (и равно нулю):

 = 0 (при b≠0).

Так как в этом случае частное (т. е. нуль) является целым числом, то нуль делится на любое целое число, отличное от нуля (причем частное равно нулю).

1. 2. Теоремы о делимости

Теорема 1. Если оба числа а и b делятся на т, то и их сумма а+ b и их разность а - b делятся на т.

Действительно, так как а делится на т, то а= кт, где k- некоторое целое число. Точно так же b=lт, где l - некоторое целое число. Поэтому

а+ b = кт + lт = (k + l)т, а - b = кт -lт = (k - l)m,

откуда видно, что каждое из чисел а + b , а - b делится на т.

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

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

Докажем это, например, для случая трех слагаемых. Слагаемые обозначим через a, b , с, а их сумму - через s:

а + b + с = s.

Нам известно, что s делится на т и числа а и b делятся на т, т. е. s = qm,

а = кт, , b = lт

где q, т, l — некоторые целые числа. Надо доказать, что и слагаемое с делится на т. Мы имеем:

с= s - а - b = qm - кт - lт = (q - k- l )m,

откуда и следует, что с делится на т.

Теорема 2. Если а делится на т и b делится на п, то ab делится на тп. В самом деле, а = кт, b = lп, и потому аb=кт∙l п=(kl) тп, т. е. ab делится на тп.

Эта теорема легко обобщается на случай трех и большего числа множителей. Например, если а делится на т, b делится на п и с делится на р, то abc делится на тпр.

Следствие 2. Если а делится на т, то аn делится на тn (здесь п — любое натуральное число).

Следствие 3. Если хотя бы один из множителей делится на т, то и произведение делится на т.

В самом деле, пусть а делится на т и пусть b — любое целое число. Так как b, очевидно, делится на l, то (по теореме 2) ab делится на тl, т. е. ab делится на т.

Можно, конечно, доказать это следствие и иначе, без ссылки на теорему 2. Именно а = кт (так как а делится на т) и потому

ab= кт∙b = (кb ) т, откуда видно, что ab делится на m.

1. 3. Сравнения

Определение. Если два числа а и b имеют одинаковые остатки при делении на т, то говорят, что а и b сравнимы по модулю т, и пишут

a ≡ b(mod т)

Запись, а ≡ b (mod т) можно прочитать так: а сравнимо с b по модулю т. Использование этой записи делает формулировки и вычисления более удобными.

Рассмотрим несколько теорем о сравнениях.

Теорема 1. Сравнение а ≡ b (mod т) имеет место в том и только в том случае, если разность а − b делится на т.

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

Теорема 2. Сравнения можно почленно складывать и вычитать, т. е. если а ≡ b (mod m) и c ≡ d (mod т), то а + с ≡ b + d (mod m) и

 а− с≡ b − d (mod m).

Иначе говоря, если а и b имеют одинаковые остатки при делении на т и, кроме того, c и d имеют одинаковые остатки при делении на т, то числа а + с и b + d имеют одинаковые остатки при делении на m и также числа а − с и b − d имеют одинаковые остатки при делении на т. Как видите, с помощью сравнения эта теорема формулируется короче и удобнее.

Теорема 3. Сравнения можно почленно умножать, т. е. если

a ≡ b (mod m), с ≡d (mod т), то ас ≡ bd (mod m).

Конечно, теоремы 2 и 3 верны для любого числа слагаемых или множителей. Например, для трех сравнений: если а ≡ b (mod т), с ≡ d (mod т) и

e ≡ f (mod т), то a + c + e ≡ b + d + f (mod m).

Следствие 1. Сравнения можно возводить в степень,  т. е. если a ≡ b (mod m), an ≡ bn (mod m).

1. 4. Периодичность остатков при возведении в степень

Рассмотрим последовательные степени числа 2:

21, 22, 23, 24, 25, 26, 27,…

и найдем, какие остатки дают эти числа при делении на 5. Для нескольких первых чисел эти остатки легко найти:

         21=2,

                  22=4,

23 = 8 ≡ 3 (mod 5),

24 = 16 ≡ l (mod 5).

Чтобы находить остатки дальше, нужно было бы вычислить дальнейшие значения степеней двойки: 25, 26, 27 и т. д. Числа эти быстро возрастают, и считать становится труднее. Но можно находить остатки и не вычисляя степеней двойки. Для этого можно воспользоваться теоремой 3(стр.9). Именно, умножая сравнение 24 ≡ 1 (mod 5) на 2 получаем:

25 ≡ 2 (mod 5)

Умножая полученное сравнение опять на 2, находим:

26 ≡ 4 (mod 5). Еще раз умножив, получаем:

27 ≡ 4∙2 ≡ 3 (mod 5),

затем

28 ≡ 3∙2 ≡ 1 (mod 5)

и т. д. Таким способом можно быстро найти остатки от деления на 5 чисел вида 2n (не вычисляя самих степеней).

Запишем то, что получается, в две строки, подписывая под каждой степенью ее остаток от деления на 5.

Сразу же видно, что остатки периодически повторяются: после четырех остатков 2, 4, 3, 1 снова повторяются в том же порядке эти остатки, затем снова и т. д.

Рассмотрим еще один пример: остатки от деления степеней тройки на 7. Мы имеем:

31 = 3,

32 = 9 ≡ 2 (mod 7).

Умножая полученное сравнение 32 ≡ 2 (mod 7) на 3, затем еще на 3 и т. д., получаем:

33         ≡ 6 (mod 7),

34         ≡ 6 ∙ 3 ≡ 4 (mod 7),

35 ≡ 4 · 3 ≡5 (mod 7)

и т. д. Если мы продолжим эти вычисления, мы получим следующие две строки (где под каждым числом подписан его остаток от деления на 7):

И здесь наблюдается периодическое чередование остатков: после каждых шести остатков все повторяется сначала.

Естественно возникает предположение, что при любых натуральных а и т остатки от деления чисел а, а2, а3, а4, а5,... на т периодически повторяются (возможно, не с самого начала).

Методика исследования

          В некоторых случаях, не производя деления натурального числа m на натуральное число n, можно ответить на вопрос: выполнимо деление m на n без остатка или нет? Ответ на этот вопрос можно получить с помощью различных признаков делимости.

Вы, конечно, знаете, как определить, делится ли некоторое натуральное число на 10:

для того чтобы некоторое натуральное число делилось на 10, необходимо и достаточно, чтобы последняя цифра этого числа была равна нулю.

Это признак делимости на 10. Например, число 257630 делится на 10,

а число 38461 не делится. Хорошо известны также признаки

делимости на 2 и на 5:

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

чтобы последняя его цифра была четной;

для того чтобы число делилось на 5, необходимо и достаточно, чтобы

его последняя цифра была 0 или 5.

Известны признаки делимости на 3 и на 9;

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

для того чтобы число делилось на 9, необходимо и достаточно, чтобы сумма его цифр делилась на 9.

А можно ли придумать признак делимости на 11 или на 13 и как доказать сформулированные выше признаки делимости (например, признак делимости на 3)? Постараемся ответить на эти вопросы. Но прежде условимся о способе записи чисел. Если нас попросят написать шестизначное число, первая цифра которого 5, вторая 9, третья 8, четвертая 1, пятая 6 и шестая 2, то мы сразу напишем: 598162. Но как быть, если нам предложат написать шестизначное число, первая цифра которого а, вторая b, третья с, четвертая d, пятая е и шестая f. Написать abcdef нельзя — это будет обозначать произведение: abcdef =a∙b∙c∙d∙e∙f. Поэтому, чтобы записать число, цифры которого обозначены буквами, мы условимся проводить над этими буквами черту. Таким образом, будет обозначать число, имеющее f единиц, е десятков, d сотен и т. д.;

= a∙105 + b∙104 + с∙103 + d∙102 + e∙10 + f.

 Почему признак делимости на три именно такой, какой мы знаем?

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

10 ≡ 1 (mod 3).

Возводя это сравнение в квадрат, куб и т. д., получаем;

102 ≡ 1 (mod 3);

103 ≡ 1 (mod 3);

104 ≡ 1 (mod 3);

105 ≡ 1 (mod 3) .... Следовательно,

a∙105 ≡ a (mod 3); b∙10 4 = b(mod 3); с∙103 ≡ с (mod 3);

d∙102 ≡ d (mod 3);  е∙10 ≡ е (mod 3);  f ≡ f (mod 3). Складывая почленно

все эти сравнения, получаем:

a∙105 + b∙104 + c∙103 + d∙102 + e∙10 + f ≡ a + b + c + d + e + f (mod 3),

или иначе:

 ≡ a + b + c + d + e + f (mod 3).

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

598162 ≡ 5 + 9 + 8 + 1 + 6 + 2 ≡ 31 ≡ 3 + 1 ≡ 1 (mod 3),

т. е. число 598162 дает остаток 1 при делении на 3, так что это число на 3 не делится.

Совершенно так же доказывается признак делимости на 9: так как 10 ≡ 1 (mod 9), то, рассуждая таким же образом, получим;

 ≡ a + b + c + d + e + f (mod 9).

 Например,

754289 ≡ 7 + 5 + 4 + 2 + 8 + 9 ≡ 35 ≡ 3 + 5 ≡ 8 (mod 9),

 т. е. число 754289 дает при делении на 9 остаток 8.

А теперь попытаемся таким же способом получить признак делимости на 11.

Для этого заметим, что

10 ≡ −1 (mod 11). Возводя это сравнение в квадрат, куб и т. д., получим:

102 ≡ l (mod 11),

103 ≡ −l (mod 11),

104 ≡ l (mod 11),

105 ≡ − l (mod 11) и т.д.
Следовательно,

a ∙105 ≡ −a (mod 11);        b ·∙104 = b (mod 11);

c ∙103 ≡ − с (mod 11);        d· ∙102≡ d (mod 11);

e∙10≡ − e (mod 11);        f ≡ f (mod 11).

Складывая почленно все эти сравнения, получаем:

≡ −a+b−c+d−e+f ≡ (b+d+f) − (а+с+е) (mod 11).

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

Например,

542379 ≡ (4 + 3 + 9) − (5 + 2 + 7) ≡ 2 (mod 11),

 61391 ≡ (6 + 3+1) − (1+9) ≡ 0 (mod 11), значит, первое число не делится на 11 (оно дает остаток 2 при делении на 11), а второе делится на 11.

Таким же способом можно получить признак делимости на 7.

 10 ≡ 3 (mod 7);

102 ≡ 10∙3 ≡ 2 (mod 7);

103  ≡ 10∙2  ≡−1 (mod 7);

104 ≡ 10∙(− 1) ≡ 3 (mod 7);

105 ≡ 10∙(−3) ≡ −2 (mod 7);

106 ≡ 10∙(−2) ≡ 1 (mod 7).

Так как 106 ≡ 1 (mod 7), то дальше все будет повторяться. В результате мы получаем следующие две строки чисел, причем под каждой степенью десяти подписано число, сравнимое с ней по модулю 7 (т. е. дающее тот же остаток при делении на 7):

Отсюда мы получаем (взяв для примера шестизначное число ):

 ≡ a 105 + b∙104 + c∙103 + d∙102 + e∙10 + f ≡

≡ (-2)a + (-3)b + (−1)c + 2d + 3e + f (mod 7)

В результате мы получаем следующее правило: чтобы узнать остаток от деления натурального числа на 7, нужно справа налево подписать под цифрами этого числа коэффициенты:

…−1, 2, 3, 1, −2, −3, −1, 2, 3, 1,

затем умножить каждую цифру на стоящий под ней коэффициент и полученные произведения сложить; найденная сумма будет иметь тот же остаток от деления на 7, что и взятое число.

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

   4  1  3  6

 −1, 2, 3, 1

−4,  2, 9, 6

−4 + 2 + 9 + 6 = 13.

Таким образом, 4136 ≡ 13 ≡ 6 (mod 7).

   Еще один пример: возьмем число 8546216.

8     5     4     6  2    1   6

1. −2. −  3, −1,  2,  3,   1

8, −10,−12, −6, 4,  3,   6

Таким образом, 8546216 ≡− 7 ≡ 0 (mod 7), т. е. число 8546216 делится на 7.

Заметим еще, что иногда признак делимости можно получить проще. Пусть, например, нужно определить, делится ли некоторое число на 15. Конечно, можно, как указано выше, найти коэффициенты, подписать их и составить сумму произведений цифр на эти коэффициенты. Но можно поступить проще. Ведь если число делится на 15, то оно делится на 3 и на 5. Наоборот, если число делится на 3 и на 5, то по теореме 2(стр.7) оно делится на 15.    Значит, для того чтобы число делилось на 15, необходимо и достаточно, чтобы оно делилось на 5 и на 3, т. е. чтобы оно оканчивалось нулем или пятеркой и, кроме того, сумма его цифр делилась на 3. Аналогично

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

Таким же способом можно получить признаки делимости на 12, 14, 18, и другие числа.

Экспериментальная часть

Выведем признак делимости на 4. 10 ≡ 2 (mod 4),

102 ≡ 0 (mod 4),

103 ≡ 0 (mod 4),

104 ≡ 0 (mod 4),

105 ≡ 0 (mod 4) и т. д.

Доказательство проведем для пятизначного числа . Имеем  = a·10000 + b·1000 + c·100 + d·10 + e. Так как 100, 1000 и 10000 делятся на 4, то делится на 4 и сумма  10 000а + 1000b + 100с.  Значит, двузначное число d·10 + е делится на 4, то и  делится на 4; если же не делится на 4, то и не делится на 4.

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

Например, число 15 436 делится на 4, так как число 36 делится на 4. Число

372 514 не делится на 4, так как 14 не делится на 4.

Выведем признак делимости на 13.

10 ≡ −3 (mod 13),

102 ≡ 10∙ (−3) ≡ −4 (mod 13),

103 ≡ 10 (−4) ≡ −1 (mod 13),

104 ≡ 10 (−1) ≡ 3 (mod 13),

105 ≡ 10∙3 ≡ 4 (mod 13),
106 ≡ 10∙4 ≡ 1 (mod 13) и т. д.

Так как 106 ≡ 1 (mod 13), то дальше все будет повторяться. В результате мы получаем следующие две строки чисел, причем под каждой степенью десяти подписано число, сравнимое с ней по модулю 13 (т. е. дающее тот же остаток при делении на 13):

Отсюда мы получаем (взяв для примера шестизначное число ):

≡ a∙ 105 + b∙104 + c∙103 + d∙102 + e∙10 + f ≡

≡ 4a + 3b + (−1)c + (−4)d +(−3)e +f (mod 13)

В результате мы получаем следующее правило: чтобы узнать остаток от деления натурального числа на 13, нужно справа налево подписать под цифрами этого числа коэффициенты:

...−1, −4, −3, 1, 4, 3, −1, −4, −3, 1,

затем умножить каждую цифру на стоящий под ней коэффициент и полученные произведения сложить; найденная сумма будет иметь тот же остаток от деления на 13, что и взятое число.

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

9      4       1      3     6

3,   −1,    −4,   −3,    1

27, −4,    −4,   −9,    6

27 − 4 − 4 − 9 + 6 = 16

Таким образом, 94136 ≡ 16 ≡ 3 (mod 13), т. е. число 94136 не делится на 13. Еще один пример: возьмем число 4250636.

4  2  5    0     6     3  6

1, 4, 3, −1, −4,  −3,   1

4, 8, 15, 0, −24, −9,  6

4 +8 +15 +0 −24 −9 +6 = 0

Таким образом, 4250636 ≡ 0 (mod 13), т. е. число 4250636 делится на 13.

Выведем признак делимости на 17.

10 ≡ −7 (mod 17),                                      109 ≡ 10∙(−1) ≡ 7(mod 17),

102 ≡ 10∙ (−7) ≡ −2 (mod 17),                     1010 ≡ 10∙2 ≡ 3 (mod 17),

103 ≡ 10 (−2) ≡ −3 (mod 17),                     1011 ≡ 10∙3 ≡ −4 (mod 17),

104 ≡ 10 (−3) ≡ 4 (mod 17),                        1012 ≡  10∙(−4) ≡ −6 (mod 17),

105 ≡ 10∙4 ≡ 6 (mod 17),                             1013 ≡ 10∙(−6)  ≡  8 (mod 17),
106 ≡ 10∙6 ≡ −8 (mod 17),                           1014 ≡ 10∙8 ≡ −5 (mod 17),

107 ≡ 10∙(−8) ≡ 5 (mod 17),                        1015 ≡ 10∙(−5) ≡ 1(mod 17) и т. д.

108 ≡ 10∙5 ≡ −1 (mod 17),

Так как 1015 ≡ 1 (mod 17), то дальше все будет повторяться.

 В результате мы получаем следующее правило: чтобы узнать остаток от деления натурального числа на 17, нужно справа налево подписать под цифрами этого числа коэффициенты:

...−1, 5, −8, 6, 4, −3, −2, −7, 1,

затем умножить каждую цифру на стоящий под ней коэффициент и полученные произведения сложить; найденная сумма будет иметь тот же остаток от деления на 17, что и взятое число.

Выведем признак делимости на 19.

10 ≡ −9 (mod 19),                                      109 ≡ 10∙(−1) ≡ 9(mod 19),

102 ≡ 10∙ (−9) ≡ 5 (mod 19),                       1010 ≡ 10∙9 ≡ −5 (mod 19),

103 ≡ 10 5 ≡ −7 (mod 19),                          1011 ≡ 10∙(−5) ≡ 7 (mod 19),

104 ≡ 10 (−7) ≡ 6 (mod 19),                        1012 ≡  10∙7 ≡ −6 (mod 19),

105 ≡ 10∙6 ≡ 3 (mod 19),                            1013 ≡ 10∙(−6) ≡ −3 (mod 19),
106 ≡ 10∙3 ≡ −8 (mod 19),                          1014 ≡ 10∙(−3) ≡ 8 (mod 19),

107 ≡ 10∙(−8) ≡ −4 (mod 19),                     1015 ≡ 10∙8 ≡ 4(mod 19),

108 ≡ 10∙(−4) ≡ −2 (mod 19),                     1016 ≡ 10∙4 ≡ 2(mod 19),

109 ≡ 10∙(−2) ≡ −1(mod 19),                     1017 ≡ 10∙2 ≡ 1(mod 19) и т. д.

Так как 1017 ≡ 1 (mod 19), то дальше все будет повторяться.

 В результате мы получаем следующее правило: чтобы узнать остаток от деления натурального числа на 19, нужно справа налево подписать под цифрами этого числа коэффициенты:

...−1,−2, −4, −8, 3, 6, −7, 5, −9, 1,

затем умножить каждую цифру на стоящий под ней коэффициент и полученные произведения сложить; найденная сумма будет иметь тот же остаток от деления на 19, что и взятое число.

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

  4      8         7      0      0      5      0     1       3      2

−1,    −2,      −4,    −8,    3,     6,   −7,    5,    −9,     1

−4,    −16,   −28,      0,    0,   30,     0,   5,   −27,    2

−4 − 16 − 28 + 0 + 0 + 30 + 0 + 5 − 27 + 2 = −38

Таким образом, 4870050132 ≡ −38 ≡ 0 (mod 19), т. е. число 4870050132 делится на 19.

Выведем  признак делимости на 101.

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

10 ≡ −91 (mod 101),

102 ≡ 10∙ (−91) ≡ −1 (mod 101),

103 ≡ 10 ∙(−1) ≡ 91 (mod 101),

104 ≡ 10 ∙ 91 ≡ 1 (mod 101) и т. д.

Так как 104 ≡ 1 (mod 101), то дальше все будет повторяться.  В результате мы получаем следующие две строки чисел, причем под каждой степенью десяти подписано число, сравнимое с ней по модулю 101 (т. е. дающее тот же остаток при делении на 101):

Отсюда мы получаем (взяв для примера пятизначное число ):

≡ a∙ 104+ b∙103 + c∙102 + d∙10 + e  ≡

≡ a + 91b + (−1)c + (−91)d +e (mod 101)

В результате мы получаем следующее правило: чтобы узнать остаток от деления натурального числа на 101, нужно справа налево подписать под цифрами этого числа коэффициенты:

... 1, 91, −1, −91, 1,

затем умножить каждую цифру на стоящий под ней коэффициент и полученные произведения сложить; найденная сумма будет иметь тот же остаток от деления на 101, что и взятое число.

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

5        9        3       4         2      1         2      9

91,   −1,    −91,     1,       91,  −1,    −91     1

455, −9,    −273,   4,     273,   −1,  −182,   9

455 − 9 − 273 +  4 + 273 − 1 − 182 + 9 = 185

Таким образом, 59342129 ≡ 185 ≡ 84 (mod 101), т. е. число 59342129 не делится на 101. Еще один пример: возьмем число 36332124.

3       6        3      3       2       1     2       4

91,   −1,    −91,   1,     91,  −1,  −91,    1

273, −6,  −273,   3,    182, −1, −182,   4

273 − 6 − 273 + 3 + 182 − 1 − 182 +  4 =0

Таким образом, 36332124 ≡ 0 (mod 101), т. е. число 36332124 делится на 101.

  Выведем признак делимости на 37.

10 ≡ −27 (mod 37).

102 ≡ 10∙ (−27) ≡ −11 (mod 37),

103 ≡ 10 (−11) ≡ 1 (mod 37) и т. д.

Так как 103 ≡ 1 (mod 37), то дальше все будет повторяться.

В результате мы получаем следующее правило: чтобы узнать остаток от деления натурального числа на 37, нужно справа налево подписать под цифрами этого числа коэффициенты:

... 1, −11, −27, 1,

затем умножить каждую цифру на стоящий под ней коэффициент и полученные произведения сложить; найденная сумма будет иметь тот же остаток от деления на 37, что и взятое число.

Выведем признак делимости на 41.

10 ≡ −31 (mod 41),.

102 ≡ 10∙ (−31) ≡ 18 (mod 41),

103 ≡ 10 18 ≡ 16 (mod 41),

104 ≡ 10 16 ≡ −4 (mod 41),

105 ≡ 10 (−4) ≡ 1 (mod 41) и т. д.

Так как 105 ≡ 1 (mod 41), то дальше все будет повторяться.

В результате мы получаем следующее правило: чтобы узнать остаток от деления натурального числа на 41, нужно справа налево подписать под цифрами этого числа коэффициенты:

... 1, −4, 16, 18, −31, 1,

затем умножить каждую цифру на стоящий под ней коэффициент и полученные произведения сложить; найденная сумма будет иметь тот же остаток от деления на 41, что и взятое число.

Сформулируем признак делимости на 12.

для того чтобы число делилось на 12, необходимо и достаточно, чтобы оно

делилось на 4 и на 3, т. е. чтобы его последние две цифры делились на 4 и, кроме того, сумма его цифр делилась на 3.

Сформулируем признак делимости на 18.

для того чтобы число делилось на 18, необходимо и достаточно, чтобы оно

делилось на 2 и на 9, т. е. чтобы его последняя цифра была четной и, кроме

того, сумма его цифр делилась на 9.

Сформулируем признак делимости на 14.

для того чтобы число делилось на 14, необходимо и достаточно, чтобы оно

делилось на 2 и на 7, т. е. чтобы его последняя цифра была четной и, кроме

того, оно делилось на 7(см. признак делимости на 7).

Заключение

В данной работе были рассмотрены основные понятия делимости.

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

Суть этого метода состоит в том, что вместо числа рассматривается сумма, состоящая из цифр этого числа, умноженных на какие-то коэффициенты. Этими способами можно найти признак делимости на любое число т. Надо только найти, какие коэффициенты следует подписывать под цифрами взятого числа. А для этого нужно каждую степень десяти 10k заменить по возможности меньшим числом (положительным или отрицательным), имеющим тот же остаток при делении на т, что и число 10k. При т = 3 или т = 9 эти коэффициенты получились очень простые: все они равны единице. Поэтому и признак делимости на 3 или на 9 получился очень простой. При т=11 коэффициенты тоже были несложные: они попеременно равны +1 и −1. А при m =7, 13, 17,19 коэффициенты получились посложнее; поэтому и признак делимости на эти числа получились более сложными.

Отметим, что немного коэффициентов получается для признаков делимости на 101, 37,  41. Интересны признаки делимости на 12, 14, 18.

Таким образом, построены несколько признаков делимости на различные числа и проверены известные признаки делимости, например на 3 и 9.

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

Также можно применить признак делимости к сколь угодно большим числам.

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

  Дальнейшее развитие темы данной работы можно вести в двух направлениях:

1) более глубокое изучение теории чисел;

2) разработка анимационных методических пособий по математике.

Литература

1. Васильев Н.Б., Гутенмахер В.Л. Делимость целых чисел. Учебное     пособие для учащихся ОЛ ВЗМШ.  М.: Изд. ОЛ ВЗМШ, 2003

2. Воробьев Н.Н. Признаки делимости.- 4-е изд., испр. М.: «Наука». Гл.ред. физ-мат. Лит., 1988. (попул. лекции по мат.)

3. Виленкин Н.Я. Признаки делимости. М., «Наука», 1968

4. Гусев В.А. Арифметика остатков. М., «Просвещение», 1984

5.  Крельштейн Б.И. Необходимые и достаточные условия в математике. М., «Просвещение», 1976

6. Михелович Ш.Х. Теория чисел. М. Государственное издательство

«Высшая школа» , 1962.

7. О. Оре. Приглашение в теорию чисел. М.: «Наука». Главная редакция

     физико-математической литературы, 1980.

8. Шклярский.Д.О.  Избранные задачи и теоремы элементарной математики. Арифметика и алгебра. - М.:ФИЗМАТЛИТ, 2001

9. Энциклопедия для детей. Т.11. Математика - М.: Аванта+, 1998