Учебник по теории чисел Ильиных АП

Индексируя, имеем
ind 5	+ 7 ind x ≡ ind 1 (mod 12),
9	+ 7 ind x ≡ 0	(mod 12),
	7 ind x ≡ −9	(mod 12),
	7 ind x ≡ 3	(mod 12).

Обозначим y = ind x. Тогда 7y ≡ 3 (mod 12). Подбором находим y = 9. Получим ind x = 9, и x ≡ 5 (mod 13).

Ответ x ≡ 5 (mod 13).
ПРИМЕР 3. Решить сравнение
2 · 3x ≡ 7 (mod 13).			(8)
Индексируя, получим
ind 2 + xind 3	≡ 7	(mod 12),
1 + 4x	≡ 11	(mod 12),
4x	≡ 10	(mod 12).

Поскольку (4, 12) = 4 и 10 6... 4, то сравнение 4x ≡ 10 (mod 12), а, поэтому и исходное сравнение, неразрешимы.

Ответ: сравнение не имеет решений.

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

Лекция 16. Системы счисления.

Рассмотрим некоторые арифметические приложения теории сравнений Для записи натуральных чисел обычно применяется десятичная система счис-

ления. При этом используется десять цифр 0, 1, . . . , 9. Рассмотрим, например, число a = 23759. Тогда

a = 2 · 104 + 3 · 103 + 7 · 102 + 5 · 10 + 9.

Каждая цифра в зависимости от позиции указывает число единиц, десятков, сотен и т.д. Мы имеем позиционную систему счисления.

Вместо десятичной системы счисления можно рассматривать g-ичную систему счисления, где g N и g > 1. Случаи g = 2 — двоичная система счисления, g = 8 — восьмиричная, g = 16 — шестнадцатиричная наиболее употребительны в информатике

Рассмотрим запись числа в g-ичной системе счисления Нам потребуются g цифр. Например, при g = 16, цифрами будут символы 0, 1, . . . , 9, A, B, C, D, E, F .

При этом цифры A, B, C, D, E, F обозначают соответственно числа 10, 11, 12, 13, 14, 15

ПРИМЕР. Дано число a = 1A1 в системе счисления с основанием 16. Чтобы указать на шестнадцатиричную систему счисления, записываем a = 1A116.

Записать число a = 1A116 в десятичной системе счисления.

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

Решение. Имеем a = 1 · 162 + 11 · 16 + 1 = 43310.

ТЕОРЕМА 1 Всякое натуральное число a единственным способом записывается в g-ичной системе счисления.

Доказательство существования записи. Разделим число a > 0 на основание системы счисления g. Получим

a = g · a1 + r0,

(1)

где a1 — частное, r—остаток от деления a на g. По признаку остатка имеем 0 6 r0 6 g − 1. Поэтому рассматриваем r0 как g-ичную цифру.

Далее делим a1 на g, получаем a1 = g · a2 + r1. Подставим эту запись в (1). Тогда

a = g2 · a2 + g · r1 + r0.

(2)

Далее делим a2 на g, подставляем в (2) и т.д. Поскольку числа a1, a2, . . . убывают, то процесс оборвется на некотором rn, где 0 < rn < g. Получим

a = rn · gn + rn−1 · gn−1 + · · · + r1 · g + r0.

(3)

Это означает, что число a имеет следующую запись в g-ичной системе счисления

a = rnrn		1	. . . r1r0.	(4)
След Пред Стр Начало	Оглавление Обратно Меню Экран Выход
		−

Докажем единственность.

Пусть число a двумя способами записано в g-ичной системе счисления: наряду с записью (3), есть еще запись

a = sm · gm + · · · + s1 · g + s0

(5)

Нужно проверить, что r0 = s0, r1 = s1, . . .

Из (3) и (5) имеем a = g ·t1 +r0 и a = g ·t2 +s0, где 0 6 r0, s0 6 g −1 Поэтому как r0, так и s0 —можно считать остатком от деления a на g. Поскольку остаток определен однозначно, то r0 = s0. Приравняем записи (4) и (4), сократим на r0 = s0 и разделим на g и повторим рассуждение. Получим r1 = s1 и т.д.

Теорема доказана.

Признаки делимости. Из школьного курса хорошо известны следующие признаки делимости.

Число a делится на 2 тогда и только тогда, когда последняя цифра числа a делится на 2.

Число a делится на 3 (делится на 9) тогда и только тогда, когда сумма цифр числа a делится на 3 (делится на 9).

С помощью теории сравнений легко получить эти и другие признаки делимости. Пусть требуется найти признак делимости числа a на число m. Если число a делится на число m, то мы записываем a ... m и говорим

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

1) число a делится на число m

Однако этоже самое можно выразить на языке сравнений в виде

2)число a сравнимо с нулем по модулю m.

Спомощью такого перехода с языка делимости на язык сравнений легко получаются признаки делимости. Выведем признак делимости на 9.

ТЕОРЕМА 2 Число a делится на 9 тогда и только тогда, когда сумма цифр числа a делится на 9.

Доказательство. Имеем a = (an . . . a1a0)10, т.е. a = an · 10n + · · · + a1 · 10 + a0. То, что нужно доказать на языке делимости записывается в виде

.	.
.	.	(6)
a . 9	(an + · · · + a1 + a0) . 9.

То же самое на языке сравнений имеет вид

a ≡ 0 (mod 9) (an + · · · + a1 + a0) ≡ 0 (mod 9).

(7)

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

Проверим (7). Рассмотрим очевидные сравнения

1	≡ 1		(mod 3)
10	≡ 1		(mod 3)
102	≡	1	(mod 3)
	≡	. . .
10n		1	(mod 3)

Умножаем первое сравнение на a0, второе на a1 и т.д. Просуммировав получим

.	a ≡ an + · · · + a1 + a0	(mod 3).
.	a ≡ 0 (mod 3) an + · · · + a1	+ a0 ≡ 0 (mod 3) (an + · · · +
Отсюда a . 3
.
.
a1 + a0) . 3, что и нужно.

Аналогично получим признак делимости на m = 11. Рассмотрим число a =

(an . . . a1a0)10 и просматриваем его цифры от a0 к an. Тогда S = a0 +a2 +a4 +. . .

сумма цифр стоящих на нечетных места числа a, S1 = a1 + a3 + a5 + . . . сумма цифр стоящих на четных места.

ТЕОРЕМА 3 Число a делится на 11 тогда и только тогда, когда S − S1 делится на 11, т.е.

a ... 11 (a0 + a2 + a4 + . . . ) − (a1 + a3 + . . . ) ... 11.

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

Доказательство. Имеем

a = an · 10n + an−1 · 10n−1 + · · · + a3 · 103a2 · 102a1 · 10 + a0 и

1	≡	1	(mod 11)
10	≡	−1	(mod 11)
102	≡	1	(mod 11)
103	≡	−1	(mod 11)
104	≡	1	(mod 11)

. . . . . . . . .

Умножим первое сравнение в на a0, второе — на a1 и т.д. Суммируя получаем

a ≡ (a0 + a2 + a4 + . . . ) − (a1 + a3 + . . . ) (mod 11).

Тогда a ... 11 a ≡ 0 (mod 11) S ≡ 0 (mod 11) S ... 11, что и нужно. Теорема доказана.

Рассмотрим более сложный признак делимости на 37. Рассмотрим следующие сравнения

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

1	≡ 1	(mod 37)
10	≡ 10	(mod 37)
102	≡ 26	(mod 37)
103	≡ 1	(mod 37)
104	≡ 10	(mod 37)
105	≡ 26	(mod 37)
	. . .
Умножим сравнения на числа a0, a1,		a2, a0, a1, a2 и т.д. Получим, что для

S = a0 + 10 · a1 + 26 · a2 + a3 + 10 · a4 + 26 · a5 + . . . имеем a ≡ S (mod 3)7.

ТЕОРЕМА 4 Число a делится на 37 тогда и только тогда, когда сумма S делится на 37.

Доказательство. Так как a ≡ S (mod 37), то a ... 37 a ≡ 0 (mod 37) S ≡ 0 (mod 37) S ... 37, что и нужно.

Теорема доказана.

Рассмотренный метод получения признаков делимости предложен французским математиком Б. Паскалем.

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

Лекция 17. Запись рациональных чисел в виде десятичной дроби.

В курсе «Числовые системы» доказываются основные свойства действительных чисел. В частности, каждому действительному α числу ставится в соответствие бесконечная десятичная дробь без 9 в периоде.

Далее считаем, что α > 0. Если действительное число β отрицательно, т.е. β = −α, где α > 0, то десятичную дробь для β получается из десятичной дроби для α приписыванием к ней знака минус.

Рассмотрим случай, когда α—рациональное число. Напомним, что рациональным числом называется число вида ab , где a и b — целые числа и b 6= 0. При этом можно считать, что b > 0. Производя процесс деления числа a на b получаем десятичную дробь. Рассмотрим примеры такого деления.

ПРИМЕР 1. Пусть a = 3, b = 4. Процесс получения десятичной дроби известен из школьного курса как «способ деления уголком».

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

34

30 0, 75

28

20

20

0

В результате получим 34 = 0, 75

ПРИМЕР 2. Записать в виде десятичной дроби 23 .

23

20 0, 66

18

20

18

2

Поскольку 2 повторилась, то далее бесконечно повторяется цифра 6. Получили 23 = 0, 66 . . . .

След Пред Стр Начало Оглавление Обратно Меню Экран Выход