Решение сравнений методом подбора. Метод преобразования коэффициентов при решении линейных сравнений. 4 страница

51.Арифметические приложения теории сравнений. Вычисление остатков при делении на данное число.

Под системой счисления понимают «совокупность приемов обозначения (записи) чисел. позиционные системы счисления. Это такие системы счисления, в которых значение любой цифры числа определяется не только ее очертанием, но и положением. Количество различных цифр, используемых в позиционной системе счисления для изображения любого числа, называют основанием системы счисления. Различают позиционные и непозиционные системы счисления.Все позиционные системы объединяет общий принцип построения. Пусть - основание системы счисления, тогда записать число в -чной системе счисления это значит представить его либо в цифровой форме: , либо в многочленной форме: (если число - целое, то ),где – цифра системы счисления. Основание системы счисления в начальный период утверждения таких систем счисления истолковывалось как отношение единиц двух любых соседних разрядов в числе: каждая единица следующего разряда в «» раз больше единицы предшествующего разряда. Со временем, однако, такое толкование понятия «основание системы счисления» расширилось. Сегодня существуют так называемые обобщенные системы счисления.
Систематической записью натурального числа по основанию называется его представление в виде , где - цифры числа, причем и < . Теорема. Всякое натуральное число может быть единственным образом представлено в виде систематической записи по любому основанию >1.
Способ замены данного числа другим числом, чтобы вычисления остатка от деления на значительно упростилось был предложен французским математиком Б. Паскалем (1623-1662).
Пусть .Обозначим абсолютно наименьший вычет числа по модулю через , так что .
Тогда , где .Отсюда следует, что число при делении на даёт такой же остаток, как и .

52.Систематические числа, установление признаков делимости чисел.
Рассмотренный выше способ отыскания остатков при делении чисел может быть использован при выводе признаков делимости, так как число делится на , когда делится на .
Замечание. Рассмотренный в предыдущем пункте пример позволяет сформулировать аналогичный признак делимости на 8 в 10-чной системе счисления: число в 10-чной системе счисления делится на 8, если делится на 8 число, составленное из последних трёх цифр исходного числа.
Как видим, ряд признаков делимости, причём даже для различных систем счисления, имеют похожую формулировку. Сформулируем ряд более общих признаков делимости.

Теорема1. Пусть и число записано в виде (2) в десятичной системе счисления. Число делится на тогда и только тогда, когда на делится сумма чисел, которые получаются при разбиении справа налево цифровой записи числа на грани по цифр в каждой грани.
Доказательство.
Запишем число в системе счисления с основанием :
где для всех .
Из (3) видно, что - остаток от деления на , т.е. - число, которое в десятичной системе счисления имеет цифры одинаковые с последними цифрами числа .
Далее получаем, что - остаток от деления числа на , т.е. - число, которое в 10-чной системе счисления имеет цифры такие же, как в предпоследней грани из чисел у числа , и т.д.Таким образом, - числа, которые получаются при разбиении справа налево числа на грани по цифр в каждой грани. Так как , то , тогда . Следовательно, число делится на тогда и только тогда, когда на делится сумма чисел, которые получаются при разбиении справа налево числа на грани по цифр.
Замечание. Сформулированные признак делимости на всегда будет таков, что количество цифр в каждой грани не больше . Наименее удобен этот признак, когда максимальное. Например, так как 10 первообразный корень по , т.е. , то число для проверки делимости на 7 придётся разбивать на грани по 6 цифр. Очевидно, что применять такой признак имеет смысл, если исследуемое число очень велико
Рассмотрим признак делимости на и .
Теорема 2. Пусть записано в десятичной системе счисления в виде (2). Число делится на (на ) тогда и только тогда, когда на (на ) делится на число, имеющее те же цифры, что и последние цифр числа .
Доказательство.
Пусть , где , т.е. - число, имеющее те же цифры, что и последние цифр числа .
Если , то и .
Обобщением выведенного выше признака делимости на 11 является
Теорема 3. Пусть и записано в десятичной системе счисления. Число делится на тогда и только тогда, когда на делится сумма взятых попеременно со знаком плюс и минус чисел, которые получаются при разбиении справа налево цифровой записи числа на грани по цифр в каждой грани. Например, так как , то число делится на 7, если на 7 делится сумма взятых попеременно со знаком «плюс» и «минус» чисел, получающихся при разбиении справа налево числа на грани по 3 цифры.
Замечание. Приведённые теоремы можно сформулировать для системы счисления с любым основанием .

53.Определение длины периода, получающегося при обращении обыкновенной дроби в g-чную.
Применим свойства сравнения для определения длины периода, получающегося при обобщении обыкновенной дроби в - чную. Предварительно выведем формулу для нахождения цифры числа.Пусть , . Запишем это число в - чной системе счисления:
, (4)
где .
Найдём формулу для вычисления цифры . Умножим (4) на : (5)
Возьмем целую часть от обеих частей равенства (5): (6)
Аналогично
(7)
Умножим (7) на :
(8)
Вычитая из (6) равенство (8), получаем формулу для вычисления цифры , стоящей на - м месте после запятой в числе . (9)
Теорема (о длине периода - чной дроби). Если , то длина периода получающегося при обращении рационального числа в - чную дробь равна показателю числа по .
Доказательство.
Для доказательства теоремы покажем, что цифра стоящая на месте равна цифре на -м месте.
По формуле (9) .
Так как , то - наименьшее число, для которого ,т. е. , где .
Тогда

.

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

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

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

Способ «Проверки с помощью девятки». Каждое число, записанное в десятичной системе счисления, сравнимо с суммой его цифр по модулю 9. Для каждого числа вычисляют остаток от деления на 9 суммы цифр. Производя действия на числами, производят такие же действия над этими остатками. Результат рассматриваемых действий над этими остатками должен отличаться от суммы цифр искомого результата на число кратное 9. Если ошибка кратна 9, то она замечена не будет.
Способ «Проверки с помощью одиннадцати». По модулю каждое число, записанное в десятичной системе счисления, будет сравнимо с разностью суммы цифр, стоящих на нечётном месте, и суммы цифр, стоящих на нечётном месте. Для каждого числа вычисляют остаток от деления на 11 разности между суммами цифр, стоящих на чётном и нечётном местах. Результат рассматриваемых действий над этими остатками должен отличаться от разности сумм цифр на чётном и нечётном местах искомого результат на число кратное 11. Если ошибка кратна 11, то она не будет обнаружена.
Замечание. При сложных вычислениях имеет смысл производить две проверки с помощью и с помощью . Тогда необнаруженными могут быть только ошибки кратные 99.