Сравнения как метод исследования делимости натуральных чисел

Час, затраченный на понимание, экономит год жизни.

В. Босс.

Две стихии господствуют в математике – числа и фигуры с их бесконечным многообразием свойств и взаимосвязей. Числа играют важнейшую роль в жизни человека. Само возникновение понятие числа – одно из гениальнейших проявлений человеческого разума.

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

Внутренняя красота разнообразных свойств первых обитателей этого океана – вещественных чисел – очень привлекательна и интересна. Искомое тут почти всегда число или какое-нибудь свойство чисел определенного вида. Интерес к большим числам вполне созвучен космической эре цивилизации.

Одно из красивейших свойств чисел – делимость И можно даже сказать, даже в чем-то романтическое (делимость – делитель – разделять); источник и основа многих математических понятий теорем и формул.

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

Сравнения

Всем хорошо известны натуральные числа (N) – числа, которые используются при счете предметов. Их можно складывать, умножать, возводить в степень и при этом будут всегда получаться натуральные числа. А вот при вычитании может получиться уже целое число (-N, 0, N).

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

Деление – достаточно трудная операция. Для упрощения решения задач и вычислений можно использовать сравнения.

Определение. Если два числа a и b имеют одинаковые остатки при делении на m, то можно сказать, что a и b сравнимы по модулю m.

Запись можно прочитать так: a сравнимо с b по модулю m. Это означает, что a и b имеют одинаковые остатки при делении на m.

Существует несколько теорем о сравнениях:

Теорема 1: сравнение имеет место в том и только в том случае, если разность делится на m.

Теорема 2: Сравнения можно почленно складывать и вычитать, т. е. если и , то и.

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

Следствие 1: Сравнения можно возводить в степень, т. е. если , то.

Следствие 2: Рассмотрим некоторый многочлен с целыми коэффициентами:. Если , то значения, которые принимает этот многочлен при и при , также сравнимы между собой по модулю, т. е.

Решение задач с помощью сравнений

Задача 1: Доказать, что при любом натуральном m число делится на 133.

Решение:

Задача 2: Число a дает остаток при делении на , а число дает остаток при делении на. Можно ли утверждать, что число дает остаток при делении на , а число дает остаток при делении на. Как изменить формулировку, чтобы получить верное утверждение?

Решение: Это утверждение верно, но не совсем. Дело в том, что при сложении остатков от деления может получиться число, превосходящее делитель, а такое число уже не будет являться остатком от деления. Точно также и в случае с умножением остатков. Правильная формулировка будет такой: «число дает такой же остаток от деления на , что и , а число дает такой же остаток от деления на , что и ».

Задача 3: Докажите, что при любом целом число четно.

Решение: Допустим, что это число уже является четным, тогда сравнение будет верно всегда, т. к. перед стоит коэффициент 2, значит но при умножении нечетных чисел, никогда не получится четное, а при умножении четных чисел никогда не получится нечетное, значит сравнение также всегда верно. Это означает, что сравнение также всегда верно.

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

Пример последовательных степеней числа 2 и остатков от деления на 5:

Дальнейшее вычисление степеней может оказаться неудобным, довольно тяжело вычислить даже вручную. Избежать ненужных вычислений поможет Теорема 3, которая позволяет умножать сравнения. Для нахождения остатка степени n нужно найти остаток от деления предыдущего остатка, умноженного на основание степени (в данном случае 2), на делитель.

Продолжение ряда показывает, что остатки, начиная с четвертой степени, начинают повторяться:

Делимое 20 21 22 23 24 25 26 27 28 29 210 Остаток 1 2 4 3 1 2 4 3 1 2 4

Таким образом, степень n можно разложить как , где l - какой-то коэффициент, k - частное , r – остаток , причем.

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

Пример: Найти остаток от деления числа на 13.

Решение: Для вычисления остатка от деления всего выражения достаточно вычислить остатки от деления каждого слагаемого и сложить их. Рассмотрим ряд ближайших степеней числа 7 для выявления закономерности:

Делимое 70 71 72 73 74 75 76 77 78 79 710 711 712 713 714 715 716 717 Остаток 1 7 10 5 9 11 12 6 3 8 4 2 1 7 10 5 9 11

По таблице видно, что начиная со степени 12, начинается повторение степеней, значит, степень 100 можно разложить как , всегда даёт остаток 1 при делении на 13, а остаток от деления уже вычислен в таблице и равен 9.

Теперь рассмотрим такой же ряд для степеней 11:

Делимое 110 111 112 113 114 115 116 117 118 119 1110 1111 1112 1113 1114 Остаток 1 11 4 5 3 7 2 9 3 8 10 6 1 11 4

Опять же видно, что повторение остатков начинается со степени 12, значит, степень 100 можно разложить как , всегда даёт остаток 1 при делении на 13, а остаток от деления уже вычислен в таблице и равен 3.

Теперь можно вычислить и остаток от деления всего выражения на 13.

Он будет равен остатку от деления на 13, значит искомый остаток равен 12.

В качестве еще одного примера, подготовлена программа, которая вычисляет остатки от деления на m при помощи данного метода. Само делимое не вычисляется, с помощью Теоремы 3 вычисляется только остаток от деления. Полный исходный код программы размещен в приложении, а сама программа - на диске вместе с электронной версией документа. Здесь приведен основной алгоритм вычисления: procedure TForm1. Button1Click(Sender: TObject); var a, b, m, n, d, at, t1, t2, bt:int64; k:integer; begin if Edit5. Text='' then ShowMessage('Введите знак') else if (Edit1. Text='') or (Edit2. Text='') or (Edit3. Text='') or (Edit4. Text='') or (LabeledEdit1. Text='') then ShowMessage('Аргумент не задан!') else if (StrToInt(Edit1. Text)<=0) or (StrToInt(Edit2. Text)<=0) or (StrToInt(Edit3. Text)<=0) or (StrToInt(LabeledEdit1. Text)<=0) then ShowMessage('Нулевые значения не допустимы!') else begin d:=StrToInt(LabeledEdit1. Text); at:=StrToInt(Edit1. Text); a:=at; bt:=StrToInt(Edit2. Text); b:=bt; m:=StrToInt(Edit3. Text); n:=StrToInt(Edit4. Text); for k:=1 to m do begin t1:=a mod d; //Находим остаток от деления a:=t1*at; //Следующая степень end; for k:=1 to n do begin t2:=b mod d; //Находим остаток от деления b:=t2*bt; //Следующая степень end; if Edit5. Text='+' then LabeledEdit2. Text:=IntToStr((t1+t2) mod d) else if Edit5. Text='-' then LabeledEdit2. Text:=IntToStr((t1-t2) mod d) else end; end;

Запустить программу (Если не работает – смотреть Ostatok. exe в папке с документом)

Рекомендуется проверить на вирусы перед запуском!

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

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

Всем известны признаки делимости на 5, 10 и 2. Несколько менее известны признаки делимости на 3 и на 9. Сравнения позволяют вывести признак делимости практически на любое натуральное число. Существует несколько способов выведения признаков делимости. Рассмотрим один из них.

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

Число можно записать как.

Затем нужно вычислить остатки от деления 10 в разных степенях на делитель.

Например, при делителе 3:

Делимое 1012 1011 1010 109 108 107 106 105 104 103 102 101 100 Остаток 1 1 1 1 1 1 1 1 1 1 1 1 1

Это значит, что каждую цифру числа нужно умножить на 1 и сложить все произведения. Если полученная сумма делится на 3, то все число делится на 3.

Таким образом, можно вывести признаки делимости практически на любое число. При этом не обязательно находить остатки от деления только на степени 10, можно и на 100, 1000 и т. д. Если в качестве основания степени взято 100, то число нужно делить на группы по 2 цифры, если 100 – по 3. Дополнительные примеры признаков делимости размещены в приложении. В итоге общий принцип выведения признаков определяется следующим алгоритмом:

1. Выбрать основание степени (10, 100, 1000) и соответственно количество цифр в каждой группе.

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

3. Затем сформулировать признак делимости на основе полученной информации

Приведенная ниже программа реализует данный алгоритм и помогает выводить признаки делимости. Исходный код размещен в приложении странице 2.

Запустить программу (Если не работает – смотреть Delimost. exe в папке с документом)

Рекомендуется проверить на вирусы перед запуском!

Сравнения главным образом связаны с понятиями «деление» и «делимость» в целых числах. Если два числа имеют один и тот же остаток от деления на m, то можно сказать, что эти числа сравнимы по модулю m. Сравнения обладают рядом свойств, которые могут помочь, например, найти остаток от деления на 5 или вывести признак делимости практически на любое натуральное число, а также использовать электронные средства для решения задач.

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

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

Сравнения – это многогранное свойство чисел, которое можно использовать во многих областях математики.

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

Данная тема очень обширна и многогранна, поэтому работа над ней будет продолжена.