Применение арифметики остатков для представления целых чисел в различных

формах.

На делении с остатком основаны различные формы представления целых чисел.

Например, при делении целого числа

на 3 могут получиться остатки 0, 1, 2. Поэтому

всякое целое число может быть представлено в одном из следующих видов: 3k, 3k + 1, 3k

+ 2 (k – целое число).

Аналогично, исходя из остатков при делении на 5, всякое целое число может быть

представлено в одном из следующих видов:

5k, 5k + 1, 5k + 2, 5k + 3, 5k + 4 (k – целое число).

В первом случае множество целых чисел разбилось на 3 класса, во втором – на 5

классов. В общем случае в соответствии с остатками от деления на натуральное число n

множество целых чисел разбивается на n классов.

Разбиение множества целых чисел на классы находит применение в теории и в

особенности при решении задач.

Пример 1. Найти, какие остатки могут получиться при делении квадрата целого

числа на 3; на 5.

Всякое

число a

в

соответствии

с

остатками

деления

его

на

3

может

быть

представлено в одном из видов:

a = 3k, a = 3k + 1, a = 3k + 2 (k – целое число).

Соответственно получаем:

a

2

= 9k

2

= 3 (3k

2

),

a

2

= (3k + 1)

2

= 9k

2

+ 6k + 1 = 3 (3k

2

+ 2k) + 1,

a

2

= (3k + 2)

2

= 9k

2

+ 12k + 4 = 3 (3k

2

+ 4k + 1) + 1.

Мы видим, что число a

2

либо делится на 3, либо при делении на 3 дает остаток 1. Тем

самым мы показали, что квадрат целого числа при делении на 3 не может дать остаток 2, а

другого быть не может по представлению числа.

Исходя из остатков от деления на 5, любое число можно представить в одном из

видов:

a = 5k, a = 5k + 1, a = 5k + 2, a = 5k + 3, a = 5k + 4 (k – целое число).

Соответственно получаем:

a

2

= 25k

2

= 5(5k

2

),

a

2

= (5k + 1)

2

= 25k

2

+ 10k + 1 = 5(5k

2

+ 2k) + 1,

a

2

= (5k + 2)

2

= 25k

2

+ 20k + 4 = 5(5k

2

+ 4k) + 4,

a

2

= (5k + 3)

2

= 25k

2

+ 30k + 9 = 5(5k

2

+ 6k + 1) + 4,

a

2

= (5k + 4)

2

= 25k

2

+ 40k + 16 = 5(5k

2

+ 8k + 3) + 1.

Отсюда ясно, что число a

2

либо делится на 5, либо при делении на 5 дает остаток 1

или 4. Значит, квадрат целого числа не может дать при делении на 5 остаток 2 или 3.

Пример 2. Выписали подряд первые двести натуральных чисел. Сколько среди этих

чисел таких, которые при делении на 7 дают остаток 4?

Всякое число в соответствии с остатком 4 при делении на 7 может быть представлено

в виде 7k + 4, где k = 0,1,2,3,



, 28. Значит, таких чисел 29.

Пример 3. Одно целое число при делении на 5 дает остаток 4, а другое – остаток 3.

Чему равен остаток, который получится при делении на 5 произведения этих чисел?

Всякое целое число в соответствии с остатками 4 и 3 при делении на 5 может быть

представлено в виде:

5k + 4 и 5k + 3.

Найдем их произведение:

(5k + 4) (5k + 3) = 25k

2

+ 35k + 12 = 5 (5k

2

+ 7k + 2) + 2.

Значит, остаток при делении произведения этих чисел на 5 будет равен 2.

Пример 4. Известно, что число m дает при делении на 17 остаток 7. Какой остаток

получится при делении на 17 числа 12m

2

+ 4m + 7?

В соответствии с остатком 7 при делении числа m на 17 число можно представить в

виде: m = 17k + 7. Тогда имеем:

12m

2

+ 4m + 7 = 12(17k + 7)

2

+ 4(17k + 7) + 7 = 12( 289k

2

+ 238k + 49) + 68k + 28 + 7 =

3468k

2

+ 2856k + 588 + 68k + 35 = 3468k

2

+ 2924k + 623 = 17(204k

2

+ 172k + 36) + 11.

Значит, остаток при делении числа 12m

2

+ 4m + 7 на 7 равен 11.

Пример 5. Докажите, что:

а) если а не делится на 5, то а

4

– 1 делится на 5;

б) если а не делится на 7, то а

6

– 1 делится на 7.

Решение: а) Если а не делится на 5, то при делении на 5 оно может давать остатки

1,2,3,4 и, значит, может быть представлено в виде 5k +1, 5k + 2, 5k + 3, 5k + 4. Тогда а

4

– 1

= (а² - 1)(а² + 1) можно представить следующим образом:

((5k + 1)² - 1)((5k + 1)² + 1) = (25k² + 10k + 1 – 1)(25k² + 10k +1 +1) =

= 5(5k² + 2k)(25k² + 10k + 2). Видим, что данное выражение делится на 5, а, значит, и

(а

4

– 1) делится на 5.