«Целые остатки»

Решения задач на остатки с вычислительной точки зрения можно несколько упростить, если вместо обычных остатков от деления на натуральное число n — чисел от 0 до n-1 — рассматривать «целые остатки» — целые числа, меньшие или равные по модулю, чем $\frac n2$.«Целые остатки»

Например, всякое целое число можно единственным образом представить в одном из видов 7k, 7k±1,7k±2, 7k±3, или в одном из видов 8k, 8k±1, 8k±2, 8k±3, 8k+4, так что числа 0, ±1, ±2, ±3 также можно считать остатками от деления на 7, а числа 0, ±1, ±2, ±3, ±4— остатками от деления на 8. (Заметим, что число -4 в «целые остатки» не включается: число вида 8n-4 можно записать и в виде 8(n-1)+4, т.е. одно и то же число может быть представлено в двух различных видах, а такая неоднозначность противоречит всей идеологии деления с остатком.)

Для «целых остатков» остаются в силе все свойства обычных остатков, но при использовании целых остатков решение задач упрощается. Например, число 34745 при делении на 7 дает тот же остаток, что и (-1)745=-1, т.е. при переводе на язык обычных остатков — остаток 6.

Эффективно используются «целые остатки» при применении «языка сравнений»: ясно, что вычисления с ними проще, чем с обычными, потому что они меньше по модулю (в данном случае модуль — это абсолютная величина).

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

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

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

Ясно, что эти свойства обобщаются на любое число слагаемых и сомножителей, и поэтому отсюда можно получить утверждение, важное для степеней натуральных и целых чисел:

Если число а при делении на натуральное число k дает остаток r, то числа аn и rn при делении на k дают равные остатки.

Поэтому, например, 34745 при делении на 7 дает тот же остаток, что и 6745, что уже немного легче. А если заметить, что 62=36 при делении на 7 дает остаток 1, то, пользуясь свойствами степеней, легко найти остаток, который дает вся степень 34745 при делении на 7: $6^{745}=6^{744}\times 6=36^{372}\times 6$ и поскольку первый множитель дает остаток 1, а второй — остаток 6, то искомый остаток равен 6.

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

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

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

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