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

1) Если i нечетно, то Pi < α.

Qi

2) Если i четно, то Pi > α.

Qi

Доказательство. В дроби (2) или (3) отбросим выражение > 0, стоящее за q1.

Полученное число, т.е. P1 меньше α. Отбросим выражение, стоящее за q2.

Q1

1

При этом выражение q2 + q3 + ... уменьшится, а, поэтому, выражение

			1
			q1 +
						1
			q2 +
					q3 + ...
	увеличится. Поэтому	P2	> α. Точно также				P3	< α и т.д.
		Q2				Q3

Из этого свойства следует, что число α заключено между соседними дро-

бями	Pi−1	и	Pi	, причем расстояние от каждой дроби меньше	1	. Отсюда
					QiQi−1
	Qi−1		Qi

получается следующее свойство

СВОЙСТВО 6 Заменим число α подходящей дробью Pi . Тогда погреш-

Qi

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

ность замены оценивается неравенством

		P		<	1			(16)
	α − Qii				QiQi+1 .

Используя подходящие дроби получим удобную формулу для решения сравнения первой степени. Пусть дано сравнение

ax ≡ b (mod m), где (a, m) = 1.

(17)

Домножая, если нужно на −1, считаем a > 0.

ТЕОРЕМА 2 Сравнение (17) имеет единственное решение, которое имеет вид

x ≡ (−1)n−1Pn−1b (mod m),

(18)

где Pn−1 — числитель предпоследней подходящей дроби при разложении числа ma в непрерывную дробь.

Доказательство. Известно, что сравнение (17) имеет единственное решение. Поэтому достаточно проверить, что число x0 = (−1)n−1Pn−1b — решение сравнения, т.е.

a · [(−1)n−1Pn−1b] ≡ b (mod m).

(19)

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

.

Pn

По свойству 2

Pn · Qn−1 − Pn−1 · Qn = (−1)n. При этом

— последняя

Qn

m

Pn

m

Pn

m

дробь для

, т.е.

=

. Поскольку дроби

и

несократимы и Qn, a > 0,

Q

Q

a

n

a

a

n

то Pn = m и Qn = a. Получаем

m · Qn−1 − Pn−1 · a = (−1)n.

Отсюда −Pn−1·a ≡ (−1)n (mod m). Умножив на (−1)n−2b, получим сравнение (19).

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

Решение в целых числах уравнения ax + by = c. Рассмотрим уравнение

ax + by = c,

(20)

с переменными x, y и целыми коэффициентами a, b, c. Требуется найти целочисленные решения этого уравнения. Уравнение (20) называется неопределенным уравнением первой степени с двумя переменными. Примененим теорию сравнений к решению неопределенных уравнений.

Заметим вначале, что при (a, b) = d > 1 и b 6... d уравнение (20) неразрешимо.

Действительно, при наличии решения (x0, y0) имеем равенство ax0 + by0 = c.

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

В нем левая часть ax0 + by0 делится на d, а правая часть c не делится на d, противоречие.

Если (a, b) = d > 1 и b ... d, то a = a1d, b = b1d, c = c1d. Разделив на d уравнение (20), получим равносильное уравнение a1x + b1y = c1, где (a1, b1) = 1. Поэтому далее считаем, что (a, b) = 1.

Покажем способ для нахождения некоторого, первоначального решения (x0, y0), а затем получим формулу всех решений уравнения (20).

Перенесем by в уравнение (20) в правую часть. Получим ax = c − by. По-

этому

ax ≡ c (mod b).

(21)

Так как (a, b)

= 1, то сравнение имеет единственное решение. Рассмотрим

.

число x0, удовлетворяющее (21). Имеем ax0

.

≡ c (mod b), т.е. ax0 − c . b и

ax

0 −

c = by

0

для y

0

Z. Вычислим число y

0

=

ax0 − c

и получим решение

b

(x0, y0).

ТЕОРЕМА 3 Пусть (x0, y0) —одно из решений неопределеннного уравнения ax + by = c, где (a, b) = 1. Тогда все решения уравнения имеют вид

x = x0 + bt, y = y0 − at для t Z.

(22)

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

Доказательство. Пусть x, y —произвольное решение уравнения (20). Тогда ax + by = c, где x, y Z. Вычтем из равенства ax + by = c равенство ax0 + by0 = c. Получим a(x − x0) + b(y − y0) = 0. Отсюда

a(x − x0) = b(y0 − y),	(23)
.	.
.	.
где y0 − y Z, т.е. a(x − x0) . b. Так как (a, b) = 1, то x − x0	. b. Поэтому

x − x0 = bt для некоторого t Z. Получили x = x0 + bt. Подставив в (23), имеем abt = b(y0 − y), at = y0 − y, y = y0 − at. Получили, что пара (x, y) имеет вид (22).

Обратно, подставив x = x0 + bt и y = y0 − at в уравнение (22), имеем a(x0+bt)+b(y0−at) = ax0+by0 = c. Поэтому пара (x, y) — решение уравнения ax + by = c.

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

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

Лекция 12. Системы сравнений первой степени.

Рассмотрим решение системы сравнений первой степени.

a1x ≡ b1	(mod m1)
a2x ≡ b2	(mod m2)	(1)
· · ·
akx ≡ bk	(mod mk)

Число x является решением системы (1), если оно является решением каждого сравнений этой системы. Если какое-то из сравнение в системе не имеет решения, то, очевидно, что система несовместна.

Решение системы (1) удобнее рассмотреть на примере. Решить систему

12x ≡ 1	(mod 7)	(2)
24x ≡ −2	(mod 5)
2x ≡ 15	(mod 11)

Ясно, что в любом из сравнений коэффициенты можно заменить на сравнимые по соответствующему модулю. Получим равносильную, более простую

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

систему.
5x ≡ 1	(mod 7)	(3)
−x ≡ −2 (mod 5)
2x ≡ 4	(mod 11)

Рассмотрим первое сравнение 5x ≡ 1 (mod 7) и найдем его решение. Так как (5, 7) = 1, то сравнение имеет единственное решение. Найдем это решение

	¯
подбором, испытывая числа 0, 1, 2, 3, 4, 5, 6. Получим решение 3. Числа класса
¯	имеют вид x = 3 + 7t, где t — произвольное целое число.
3

Идея решения системы состоит в следующем: при любом целом t число x = 3 + 7t является решением первого сравнения. Подставляем x из во второе сравнение, подберем те значения t, при которых верно также и второе сравнение.

Получаем −3−7t ≡ −2 (mod 5), то есть −7t ≡ 1 (mod 5) и 3t ≡ 1 (mod 5). Подбором находим решение t0 = 2. Поэтому t = 2 + 5t1, где t1 Z.

Подставив вид t в равенство x = 3 + 7t, получим x = 17 + 35t1, где t1 — произвольное целое число

Для таких чисел выполнено первое и второе сравнения. Подберем те значения t1, при верно также и третье сравнение.

Подставим x = 17 + 35t1 в сравнение 2x ≡ 5 (mod 11). Получим 2(17 +

35t1) ≡ 5 (mod 11), т.е. 2(6 + 2t1) ≡ 5 (mod 11). Тогда 4t1 ≡ −8 (mod 11).

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

Сократив на число 4, взаимно простое с модулем, получим t1 ≡ −2 (mod 11), т.е. t1 ≡ 9 (mod 11). Имеем t1 = 9 + 11t2 для t2 Z. Тогда x = 17 + 35t1 = 17 + 35(9 + 11t2) = 332 + 385t2, где t2 Z.

Ответ. Решение системы имеет вид x ≡ 332 (mod 385).

Сравнения n-ой степени по простому модулю. Рассмотрим другой важный вид сравнений

f(x) ≡ 0 (mod m),

(4)

где f(x) = a0xn + a1xn−1 + · · · + an — произвольный многочлен с целыми коэффициентами. Решение сравнений по составному модулю m сводится к решению сравнения по простому модулю. Поэтому изучим вначале случай, когда m = p — простое число. Итак, необходимо решить сравнение

f(x) ≡ 0 (mod p).

(5)

Рассмотрим упрощающий прием для замены исходного сравнения (5) на равносильное сравнение степени не выше p − 1. Разделим f(x) на многочлен xp − x. Получим f(x) = (xp − x)q(x) + r(x), где остаток от деления имеет вид r(x) = b0xp−1 + · · · + bp. Подставив в (5), получим

(xp − x)q(x) + r(x) ≡ 0 (mod p).

(6)

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

По теореме Ферма xp ≡ x (mod p) для всех x Z. Тогда xp −x ≡ 0 (mod p) и сравнение (6) равносильно сравнению r(x) ≡ 0 (mod p), т.е. сравнению степени не выше p − 1

b0xp−1 + · · · + bp ≡ 0 (mod p).

ПРИМЕР. Решить сравнение

26x14 − 12x11 + 22x8 + x1 + 3 ≡ 0 (mod 7).

Решение. 1) Заменим коэффициенты многочлена на сравнимые числа из совокупности 0, 1, 2, 3, 4, 5, 6. Получим равносильное сравнение

5x14 + 2x11 + x7 + 3 ≡ 0 (mod 7).

(7)

2) Можно разделить многочлен из (7) на x7−x и получить сравнение степени не выше 6. Однако, это понижение степени можно осуществить проще.

По теореме Ферма x7 ≡ x (mod p). Возводя в квадрат, получим x14 ≡ x2 (mod p). Заменим в (7) выражение x14 на сравнимое выражение x2. Далее x11 ≡ x5 (mod p) и x7 ≡ x (mod p). Поэтому, заменим в сравнении(7) x11 на x5, а x7 на x. Вместо сравнения (7) решаем равносильное сравнение

2x5 + 5x2 + x + 3 ≡ 0 (mod 7).

(8)

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

Это сравнение не допускает дальнейших упрощений, решим его методом перебора все возможных решений. Рассмотрим полную систему вычетов 0, 1, 2, 3, 4, 5, 6 по модулю 7 и проверим, являются ли эти числа решениями. Удобнее проверять числа 0, 1, 2, 3, −3, −2, −1. В результате проверки получаем, что решением является только число −3.

Ответ. Сравнение имеет единственное решение x ≡ 4 (mod 7).

ПРЕДЛОЖЕНИЕ 1 Пусть f(x) = a0xn + a1xn−1 + · · · + an, где ai Z.

Предположим, что сравнение f(x) ≡ 0 (mod p), где p — простое число, имеет n+1 решений. Тогда все коэффициенты многочлена f(x) делятся на p.

Доказательство. Обозначим через x0, x1, . . . , xn данные n + 1 решений. Поскольку решения различны, то

xi ≡/ xj (mod p) при i 6= j.

(9)

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