Свойства сравнений

Основные свойства сравнений абсолютно совпадают со свойствами равенств: для любого n>1 и любых целых чисел a и b:Свойства сравнений

1. $a\equiv a$;

2. Если $a\equiv b$, то $b\equiv a$;

3. Если $a\equiv b$, $b\equiv c$, то $a\equiv c$;

4. Если $a\equiv b$, $c\equiv d$, то $a\pm c \equiv b\pm d, ac\equiv bd$.

Свойство 4 означает, что сравнение (естественно, по одному и тому же модулю n) можно складывать, вычитать и перемножать почленно. Ясно, что это свойство справедливо для любого количества чисел, в частности, перемножением k сравнений $a\equiv b$ можно получить сравнение $a^k \equiv b^k$, т.е. сравнения можно возводить в степень с любым натуральным показателем. Можно также любые слагаемые из одной части сравнения переносить в другую — естественно, с изменением знака.

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

Например, утверждение: «Если p — простое число и произведение ab делится на р, то хотя бы одно из чисел a,b делится на р» записывается следующим образом: «Если р — простое число и $ab\equiv 0$, то $a\equiv 0$или $b\equiv 0$» — ясно, что речь идет о сравнениях по модулю р. А утверждение: «Остаток от деления произведения чисел а и b на число с равен остатку от деления на с, который дает произведение остатков от деления на с, которые дают сами числа a и b», как вы видели, совершенно необходимое при решении задач на делимость и остатки, записывается так: «Если при делении на с числа а и b дают остатки г и s, то $ab\equiv rs (\mod{c})$».

При решении задач мы часто использовали утверждение, что разность одинаковых степеней целых чисел делится на разность оснований, ссылаясь на «углубленную» формулу разности степеней, но с помощью сравнений без нее вполне можно обойтись: так как a-b делится на a-b, т.е. $a\equiv b (\mod {a-b})$, то $a^k\equiv b^k (\mod {a-b})$, значит, $a^k-b^k$ делится на $a-b$.

Для иллюстрации краткости «языка сравнений» решим задачу: «Найти две последние цифры числа 876 39637». Будем рассматривать сравнения по модулю 100. Так как $876 396\equiv 96\equiv -4$, то $876 396^{37}\equiv -4^{37}$. Но $4^5\equiv 1024\equiv 24$, так что $4^{37}\equiv 4^{35}\times 4^2\equiv 24^7\times16$, а поскольку $24^2\equiv 576\equiv -24$, то $24^3\equiv -24^2\equiv 24$, $24^6\equiv 24^2\equiv -24^2, 24^7\equiv -24^2\equiv 24, 24\times16=384$, так что последние две цифры заданного числа — 84. Попробуйте записать это решение без использования понятия сравнения.

Доказательство всех указанных выше свойств сравнений, за исключением сложения и перемножения сравнений, не представляет труда, а в оставшемся случае доказательство проводится с помощью простой, хотя и не очевидной группировки: если числа а и b при делении на k дают остатки г и s соответственно, то

$(a+b)-(r+s)=(a-r)+(b-s)$,

$ab-rs=(a-r)b+r(b-s)$,

а в правой части этих равенств a-r делится на k, b-s делится на k поэтому обе написанных комбинации чисел делятся на k.

Материалы по теме:
Поделиться с друзьями:
Оцените материал:
1 Star2 Stars3 Stars4 Stars5 Stars (2 голосов, рейтинг: 5,00 с 5)
Загрузка...

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *