При необходимости более глубокого знакомства с материалом можно воспользоваться любым из университетских учебников алгебры и теории чисел. Кроме того, имеются пособия по криптографии, содержащие необходимый минимум теоретических сведений в указанных областях. В частности, отметим пособие [1], особенно полезными мы считаем главы 2 и 3 этой книги. Мы приводим краткие сведения из теории и примеры решения некоторых задач по теории чисел.
Будем считать известными свойства операций над целыми числами (сложения, вычитания, умножения), понятие модуля целого числа и свойства модуля.
Рассмотрим свойства отношения делимости во множестве целых чисел, это множество обозначается $$\mathbb{Z}$$.
Определение 1.1 Целое число $$a$$ делится на целое число $$b$$, если существует такое целое число $$c$$, что $$a=b\cdot c$$. Число $$a$$ называется делимым, $$b$$ - делителем, $$c$$ - частным.
Если число $$a$$ делится на $$b$$, то пишут $$a\, \vdots \,b$$ ($$a$$ кратно $$b$$).
Отношение делимости $$a\, \vdots \,b$$ в $$\mathbb{Z}$$ обладает следующими свойствами:
Если $$a \, \vdots \,c$$ и $$b \in \mathbb{Z}$$, то $$(ab)\, \vdots \,c$$.
Отметим, что утверждения, обратные 4 и 5, ложны: из делимости суммы не вытекает делимость слагаемых, а из делимости произведения не вытекает делимость сомножителей.Например, $$35+13=48$$ делится на 12, но ни 35, ни 13 не делятся на 12; $$3\cdot 8=24$$ делится на 12, но ни 3, ни 8 на 12 не делятся.
Определение 1.2 Разделить целое число $$a$$ на целое число $$b \neq 0$$ с остатком - это значит найти два таких целых числа $$q$$ и $$r$$, чтобы выполнялись условия:
Число $$q$$ называется неполным частным, а число $$r$$ - остатком от деления $$a$$ на $$b$$.
Заметим, что остаток - всегда есть число неотрицательное, а вот неполное частное может быть каким угодно целым числом. Поэтому на вопрос: "Сколько будет минус пять поделить на три с остатком?", правильный ответ: "Неполное частное минус два, остаток - один".
Теорема 1.1 Каковы бы ни были целое число a и целое число $$b \neq 0$$, всегда возможно, и притом единственным способом, разделить $$a$$ на $$b$$ с остатком.
Определение 1.3 Целое число $$\delta \neq 0$$ называется общим делителем целых чисел $$a_1, a_2, \dots, a_n$$, если каждое из этих чисел делится на $$\delta$$.
Определение 1.4 Целое число $$d$$ называется наибольшим общим делителем чисел $$a_1, a_2, \dots, a_n$$, если:
Теорема 1.2 Наибольший общий делитель чисел $$a_1, a_2, \dots, a_n$$ определён однозначно с точностью до знака (т.е. если $$d_1$$ и $$d_2$$ наибольшие общие делители чисел $$a_1, a_2, \dots, a_n$$, то либо $$d_1=d_2$$, либо $$d_1=-d_2$$).
Условимся всегда рассматривать положительное значение наибольшего общего делителя чисел $$a_1, a_2, \dots, a_n$$. Обозначение: $$d=НОД(a_1, \dots, a_n )$$.
Пример 1.1 $$НОД(135,-180)=45.$$
Действительно, множество положительных делителей числа $$135$$ есть $$A={1,3,5,9,15,27,45,135}$$, а для числа $$-180$$ такое множество имеет вид $$B={1,2,3,4,5,6,9,10,12,15,18,20,30,$ $36,45,60,90,180}$$. Пересечение этих множеств $$A \cap B = {1,3,5,9,15,45}$$. Число $$45$$ является общим делителем чисел $$135$$ и $$-180$$ и делится на все остальные общие делители этих чисел. Значит, $$НОД(135,-180)=45$$. Заметим, что $$45$$ - наибольший по величине положительный общий делитель чисел $$135$$ и $$-180$$.
Для любых целых чисел $$a_1, a_2, \dots, a_n$$ их наибольший общий делитель является наибольшим по величине положительным общим делителем.
Однако данное здесь определение является более удобным, так как распространяется на достаточно большой класс объектов, в частности, на многочлены. Определение же, включающее слова "наибольший по величине", не применимо к многочленам.
Опишем способ нахождения наибольшего общего делителя, предложенный древнегреческим математиком Евклидом. Алгоритм Евклида применяется при решении многих задач, как теоретических, так и прикладных.
Алгоритм Евклида состоит в следующем. Сначала $$a$$ делят на $$b$$ ($$a>b>0$$). Если $$a \, \vdots \, b$$, то $$НОД(a,b)=b$$. В противном случае $$a=b \cdot q_0 +r_1$$. Делим $$b$$ на $$r_1$$. Если $$b \, \vdots \, r_1$$, то $$НОД(b,r_1)=r_1$$, но тогда и $$НОД(a,b)=НОД(b,r_1)=r_1$$. Если $$b$$ не делится на $$r_1$$, то получится остаток $$r_2$$. Делим $$r_1$$ на $$r_2$$ и т.д.
Остатки, получаемые в процессе деления, убывают и являются натуральными числами, значит, на некотором шаге получим деление без остатка.
Последний не равный нулю остаток является наибольшим общим делителем чисел $$a$$ и $$b$$. Сформулируем это утверждение в виде теоремы.
Теорема 1.3 Если
| $$a=b\cdot q_0 + r_1$, $0 \leq r_1 < b,$$ |
| $$b=r_1 \cdot q_1 + r_2$, $0 \leq r_2 < r_1,$$ |
| $$r_1=r_2 \cdot q_2 + r_3$, $0 \leq r_3 < r_2,$$ |
| $$\dots$$ |
| $$r_{n-2}=r_{n-1} \cdot q_{n-1} + r_n$$, $$0 \leq r_n < r_{n-1},$$ |
| $$r_{n-1}=r_n \cdot q_n,$$ |
то $$НОД(a,b)=r_n$$
Пример 1.2 Найдём $$НОД(1547,560)$$
| $$1547 = 560 \cdot 2 + 427$$ |
| $$560 = 427 \cdot 1 + 133$$ |
| $$427 = 133 \cdot 3 + 28$$ |
| $$133 = 28 \cdot 4 + 21$$ |
| $$28 = 21 \cdot 1 + 7$$ |
| $$21 = 7 \cdot 3$$. |
| Отсюда $$НОД(1547, 560) = 7$$. |
Следствие 1.1 (Следствие из теоремы 1.3) Пусть $$d=НОД(a,b)$$, $$a>b>0$$, тогда существуют такие целые числа $$u$$ и $$v$$, что $$d=ua+bv$$. Другими словами, наибольший общий делитель двух чисел можно представить в виде линейной комбинации этих чисел с целыми коэффициентами.
Продолжение примера 1.2.
| $$7=28-1\cdot21=28-1\cdot(133-4\cdot28)=5\cdot28-1\cdot133=$$ |
| $$=5\cdot(427-133\cdot3)-1\cdot133=5\cdot427-16\cdot133=$$ |
| $$=5\cdot427-16\cdot(560-427\cdot1)=21\cdot427-16\cdot560=$$ |
| $$21\cdot(1547-2\cdot560)-16\cdot560=21\cdot1547-58\cdot560$$ |
Из алгоритма Евклида вытекает существование наибольшего общего делителя для любых двух целых чисел $$a$$ и $$b$$, кроме пары $$(0,0)$$, для которой НОД не существует.
Теорема 1.4 Если $$\delta = НОД(a_1, \dots, a_{n-1})$$ и $$d=НОД(\delta,a_n)$$, то $$d=НОД( a_1, a_2, \dots, a_n)$$.
Отметим еще одно свойство НОД. Если каждое из чисел $$a$$ и $$b$$ умножить на одно и то же число $$k \neq 0$$, то их наибольший общий делитель умножится на $$k$$.
Определение 1.5 Если $$НОД(a_1, a_2, \dots, a_n)=1$$, то числа $$a_1, a_2, \dots, a_n$$ называются взаимно простыми.
Например, числа 30 и 77 взаимно просты, а числа 30 и 72 не являются взаимно простыми, так как $$НОД(30,72)=6$$.
Теорема 1.5 Для того, чтобы числа $$a$$ и $$b$$ были взаимно простыми, необходимо и достаточно, чтобы существовали такие целые числа $$x$$ и $$y$$, что $$ax+by=1$$.
Следствие 1.2 Если числа $$a$$ и $$b$$ взаимно просты и $$a \, \vdots \,a_1$$, $$b \, \vdots \, b_1$$, то числа $$a_1$$ и $$b_1$$ взаимно просты.
И еще одно свойство: частные от деления чисел $$a$$ и $$b$$ на $$НОД(a,b)$$ взаимно просты.
Определение 1.6 Пусть $$a_1, a_2, \dots, a_n$$ - целые числа, отличные от нуля. Целое число $$M$$ называется общим кратным этих чисел, если оно делится на каждое из данных чисел.
Например, произведение $$a_1 \cdot a_2 \cdot \cdots \cdot a_n$$ - общее кратное всех своих сомножителей.
Определение 1.7 Целое число $$m$$ называется наименьшим общим кратным чисел $$a_1, a_2, \dots, a_n$$,если оно является их общим кратным и при этом любое общее кратное этих чисел делится на $$m$$.
Если наименьшее общее кратное существует, то оно определено с точностью до знака. Мы будем выбирать положительное значение наименьшего общего кратного и обозначать его так:
$$m=\LCM(a_1, a_2, \dots, a_n).$$Имеет место важная теорема.
Теорема 1.6 Число $$\dfrac{a\cdot b}{НОД(a,b)}$$, где $$НОД(a, b)$$ - наибольший общий делитель двух натуральных чисел $$a$$ и $$b$$, является наименьшим общим кратным этих чисел.
Рассмотрим основные свойства наименьшего общего кратного.
Пример 1.3 Найдем $$\LCM(5640, 2500)$$.
Разделим каждое из данных чисел на $$10$$ (очевидный делитель) и найдём $$\LCM(564, 250)$$. Имеем:
$$\LCM(564, 250)= \frac{564\cdot 250}{(564,250)}=\frac{564\cdot 250}{2}=564\cdot 125=70500.$$Тогда $$\LCM(5640, 2500)=70500\cdot10=705000$$.
Для нахождения НОК нескольких чисел имеет правило, аналогичное рассмотренному выше правилу нахождения НОД нескольких чисел.
Теорема 1.7 Если
$$\LCM(a_1, a_2)=m_1, \LCM(m_1, a_3)=m_2, \dots, \LCM(m_{n-2}, a_n) = m_{n-1},$$то $$\LCM(a_1, \dots, a_n) = m_{n-1}$$.
Иными словами, для нахождения НОК чисел $$a_1, \dots, a_n$$ надо сначала найти $$m_1=\LCM(a_1, a_2)$$, потом $$m_2=\LCM(m_1, a_3)$$, и т.д. вплоть до $$m_{n-1}=\LCM(m_{n-2}, a_n)$$. На каждом шаге нам придется находить НОК двух чисел, а это мы уже умеем делать.
Пример 1.4 Найдем $$\LCM(35, 77, 1141)$$.
$$\LCM(35, 77)= \dfrac{35\cdot 77}{НОД(35,77)}=\dfrac{35\cdot 77}{7}=35\cdot 11=385,$$ $$\LCM(385, 1141)= \dfrac{385\cdot 1141}{НОД(385,1141)}=\frac{385\cdot 1141}{7}=385\cdot 163=62755.$$Ответ. $$\LCM(35, 77, 1141)=62755$$.
Теорема 1.8 НОК попарно взаимно простых чисел равно их произведению.
Пример 1.5 Найдём $$\LCM(37, 43, 95)$$.
Имеем $$НОД(37, 43)=1$$, $$НОД(37, 95)=1$$, $$НОД(43, 95)=1$$. Следовательно, $$\LCM(37, 43, 95)=37\cdot43\cdot95=151145$$.
Определение 1.8 Натуральное число $$p$$ называется простым, если оно больше $$1$$ и не имеет положительных делителей, отличных от $$1$$ и $$p$$.
Определение 1.9 Натуральное число $$n$$ называется составным, если оно больше $$1$$ и имеет по крайней мере один положительный делитель, отличный от $$1$$ и $$n$$.
Согласно определению 1.2, если $$n$$ - составное, то существует такой делитель $$\delta$$, что $$n=n_1\delta$$, где $$1<n_1<n$$, $$1<\delta<n$$.
Число 1 не относят ни к простым, ни к составным числам.
Первыми простыми числами в натуральном ряду чисел являются 2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 37, 41...
Среди простых чисел имеется лишь одно четное число 2.
Итак, множество всех натуральных чисел разбивается на три подмножества: 1) простые числа, 2) составные числа, 3) число 1.
Теорема 1.9 (основная теорема арифметики) Всякое натуральное число $$n>1$$ либо просто, либо может быть представлено, и притом единственным образом (с точностью до перестановки множителей), в виде произведения простых чисел.
Отметим, что среди простых множителей числа могут встречаться одинаковые. Пусть, например, $$p_1$$ встречается $$\alpha_1$$ раз, $$p_2$$ встречается $$\alpha_2$$ раз, ..., $$p_k$$ встречается $$\alpha_k$$ раз; тогда разложение числа $$n$$ на простые множители можно записать следующим образом:
$$n={p}_{1}^{\alpha_1 }\cdot {p}_{2}^{\alpha_2 }\dots {p}_{k}^{\alpha_k }.$$Множители $$p_1, p_2,\dots, p_k$$ обычно располагают в порядке возрастания.
Определение 1.10 Представление натурального числа $$n$$ в форме 1.1 называется каноническим; это представление единственно, его называют также факторизацией числа $$n$$.
Пример 1.6 $$1176=2^{3}\cdot3\cdot7^{2}$; $136125=5^{3}\cdot11^{2}$$.
Из канонического представления числа вытекают следующие предложения.
Следствие 1.3 Если $$a=p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdots p_k^{\alpha_k}$$ - каноническое разложение числа $$a$$, то все делители этого числа имеют вид:
$$c=p_1^{\beta_1} \cdot p_2^{\beta_2} \cdots p_k^{\beta_k},$$где $$0\leq\beta_i\leq \alpha_i$$ $$(i=1, 2, {\ldots}, k)$$.
Пусть даны натуральные числа $$a$$ и $$b$$. Их каноническое разложение всегда можно записать в виде:
$$a=p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdots p_k^{\alpha_k}, \qquad b=p_1^{\gamma_1} \cdot p_2^{\gamma_2} \cdots p_k^{\gamma_k}.$$Мы предполагаем здесь, что $$\alpha_i$$ и $$\gamma_i$$ могут принимать и нулевые значения. Это позволит писать в обоих разложениях одни и те же простые числа $$p_1, p_2, \dots, p_s$$, а именно простые числа, которые входят в разложение хотя бы одного из чисел $$a$$ и $$b$$. Справедливы следующие утверждения.
Следствие 1.4 Наибольший общий делитель чисел $$a$$ и $$b$$ имеет вид:
$$НОД(a,b) = p_1^{\lambda_1}\cdot p_2^{\lambda_2}\cdots p_s^{\lambda_s},$$где $$\lambda_i=\min(\alpha_i,\gamma_i).$$
Следствие 1.5 Наименьшее общее кратное чисел $$a$$ и $$b$$ имеет вид:
$$\LCM(a,b)=p_1^{\mu_1}\cdot p_2^{\mu_2}\cdots p_s^{\mu_s},$$где $$\mu_i = \max(\alpha_i,\gamma_i)$$.
Из этих свойств непосредственно следует тождество $$(a, b) \cdot [a, b] =a \cdot b$$. Эти утверждения переносятся и на случай более чем двух чисел.
Теорема 1.10 (Евклида) Множество простых чисел бесконечно.
Поучительно сравнить эту теорему и следующую.
Теорема 1.11 (об интервалах) В натуральном ряде существуют сколько угодно длинные интервалы, не содержащие ни одного простого числа.
Сопоставление фактов, вытекающих из теоремы Евклида и теоремы об интервалах, свидетельствует о сложном характере распределения простых чисел в натуральном ряде. Вопрос этот является одним из труднейших в математике.
Рассмотрим некоторые функции, заданные на множестве натуральных чисел и связанные с арифметической природой этих чисел. Их называют числовыми функциями. Примерами таких функций могут служить:
Теорема 1.12 Если каноническая запись числа $$n$$ имеет вид:
$$n= {p}_{1}^{k_1} {p}_{2}^{k_2} {\dots} {p}_{m}^{k_m},$$то число натуральных делителей числа $$n$$ равно:
$$\tau(n)=(k_1+1)(k_2+1)\cdots (k_m+1).$$Пример 1.7 Поскольку $$60=2^{2}\cdot3\cdot5$$, то
$$\tau (60)=(2+1)(1+1)(1+1)=3\cdot2\cdot2=12.$$Делителями числа $$60$$ являются $$1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60$$. Их число действительно равно $$12$$. Приведём формулу для $$\sigma (n)$$.
Теорема 1.13 Если каноническая запись числа $$n$$ имеет вид $$n= {p}_{1}^{k_1} \dots {p}_{m}^{k_m}$$, то
$$\sigma (n)= \frac{{p}_{1}^{{k}_{1}+1}-1}{{p}_{1}-1}\cdot \frac{{p}_{2}^{{k}_{2}+1}-1}{{p}_{2}-1}{\dots}\frac{{p}_{m}^{{k}_{m}+1}-1}{{p}_{m}-1}.$$Пример 1.8 Найдём сумму натуральных делителей числа $$360$$.
Так как $$360=2^3\cdot3^2\cdot5$$, то
$$\sigma (360)= \frac{{2}^{4}-1}{2-1}\cdot \frac{{3}^{3}-1}{3-1}\cdot \frac{{5}^{2}-1}{5-1}=15\cdot 13\cdot 6=1170.$$Определение 1.11 Числа, дающие при делении на m одинаковые остатки, называются сравнимыми по модулю $$m$$. Обозначение: $$a \equiv b ~(mod \ m)$$.
Теорема 1.14 (признак сравнимости по модулю) Два целых числа сравнимы по модулю $$m$$ тогда и только тогда, когда их разность делится на $$m$$.
Итак, если два целых числа $$a$$ и $$b$$ сравнимы по модулю $$m$$, то этот факт можно записать разными способами: $$a \equiv b (mod \ m)$$ или $$a=b+mk$$, где $$k$$ - целое число, или $$a-b=mk$$ или $$(a-b)\, \vdots \,m$$.
Далее, если $$a=mq+r$$, то есть $$a$$ при делении на $$m$$ дает остаток $$r$$, то $$a-r=mq$$ или $$a \equiv r (mod \ m)$$. Таким образом, любое целое число $$a$$ всегда сравнимо с остатком $$r$$, получающимся при делении его на $$m$$.
Отношение сравнимости удовлетворяет условиям:
Отношение, заданное на множестве и обладающее перечисленными свойствами, задает разбиение этого множества на непересекающиеся классы. Применительно к отношению сравнимости по модулю $$m$$ это означает: все множество целых чисел разбивается на классы чисел, эти классы не пересекаются. Так, есть класс нуля: это все числа, сравнимые с нулем по модулю $$m$$,то есть делящиеся на $$m$$ без остатка(включая и само число 0), класс единицы - все числа, дающие остаток 1 при делении на $$m$$, класс 2, ...,класс $$m-1$$. Например, пусть $$m=5$$. Получаем следующие классы:
$$ \begin{array}{lcl} \bar{0}=\{\dots,-10, -5, 0, 5, 10, 15, 20,\dots\} \\[1ex] \bar{1}=\{\dots,-9, -4, 1, 6, 11, 16, 21,{\dots}\} \\[1ex] \bar{2}=\{\dots,-8, -3, 2, 7, 12, 17, 22,{\dots}\} \\[1ex] \bar{3}=\{{\dots},-7, -2, 3, 8, 13, 18, 23,{\dots}\} \\[1ex] \bar{4}=\{{\dots},-6, -1, 4, 9, 14, 19, 24,{\dots}\}. \end{array} $$Определение 1.12 Классы (1.2) называются классами вычетов.
Сравнения по одному и тому же модулю можно почленно складывать.
Два сравнения по одному и тому же модулю можно почленно вычитать одно из другого.
К обеим частям сравнения можно прибавлять одно и то же целое число.
Следствие 1.6 Члены сравнения можно переносить из одной части сравнения в другую с противоположным знаком.
Сравнения по одному и тому же модулю можно почленно перемножать.
Следствие 1.7 Обе части сравнения можно возводить в одну и ту же целую неотрицательную степень: если $$a \equiv b (mod \ m)$$ и $$k$$ - целое неотрицательное число, то $$a^k \equiv b^k (mod \ m)$$.
Если $$a \equiv b ~(mod \ m)$$ и $$m \, \vdots \, n$$, то $$a \equiv b ~(mod \ n)$$.
Обе части сравнения и модуль можно умножить на одно и то же целое положительное число.
Если $$ak \equiv bk \ mod \ m$$ и $$(k, m)=d$$, то $$a \equiv b \ mod \ {\frac{m}{d}}$$.
Приведем следствия из свойства 9.
Следствие 1.8 Если $$d=k$$, т. е. если $$m \, \vdots \, k$$, то из $$ak \equiv bk \ mod \ m$$ следует $$a \equiv b \ mod \frac{m}{k}$$, а это означает, что обе части сравнения и модуль можно разделить на любой их общий делитель.
Большое значение имеет
Следствие 1.9 Если $$d=1$$, т. е. если $$(k, m)=1$$, то из $$ak \equiv bk \ mod \ m$$ следует $$a \equiv b \ mod \ m$$, а это означает, что обе части сравнения можно разделить на их общий делитель, если он взаимно прост с модулем.
Пример 1.9 $$60 \equiv 9 (mod \ 17)$$.
После деления обеих частей сравнения на $$3$$ получим $$20 \equiv 3 ~(mod \ 17)$$.Делить обе части сравнения на число, не взаимно простое с модулем, вообще говоря, нельзя, так как после деления могут получиться числа, несравнимые по данному модулю.
Пример 1.10 $$8 \equiv 4~(mod \ 4)$$, но $$2 \not\equiv 1~(mod \ 4)$$.
Из рассмотренных свойств сравнений вытекает следующее общее свойство.
Пусть $$P(x)$$ - многочлен с целыми коэффициентами, $$a$$ и $$b$$ - переменные, принимающие целые значения. Тогда если $$a\equiv b ~(mod \ m)$$, то $$P(a) \equiv P(b) ~(mod \ m)$$.
Если $$a\equiv b~(mod \ m)$$ и $$c_i\equiv d_i ~(mod \ m)$$, то
$$c_na^n+c_{n-1}a^{n-1}+\ldots+c_1a + c_0 = d_nb^n + d_{n-1}b^{n-1}+\ldots+d_1b + d_0 ~(mod \ m).$$Таким образом, в сравнении по модулю $$m$$ отдельные слагаемые и множители можно заменять числами, сравнимыми по тому же модулю $$m$$. В частности, все числа, кратные модулю, можно заменять нулями (так как если $$a \, \vdots \, m$$, то $$a \equiv 0~(mod \ m)$$).
Вместе с тем следует обратить внимание на то, что встречающиеся в сравнениях показатели степеней заменять таким образом нельзя: из $$a^{n} \equiv c~(mod \ m)$$ и $$n \equiv k~(mod \ m)$$ не следует, что $$a^{k} \equiv c~(mod \ m)$$.Свойство 11 имеет ряд важных применений. В частности, с его помощью можно дать теоретическое обоснование признаков делимости.
Пример 1.11 Доказать, что при любом натуральном $$n$$ число $$37^{n+2} + 16^{n+1} +23^{n }$$ делится на $$7$$.
Решение. Очевидно, что $$37 \equiv 2~(mod \ 7)$$, $$16 \equiv 2~(mod \ 7)$$, $$23 \equiv 2~(mod \ 7)$$.
Возведем первое сравнение в степень $$n+2$$, второе - в степень $$n+1$$, третье - в степень $$n$$. Полученные сравнения: $$37^{n+2} \equiv 2^{n+2}~(mod \ 7)$$, $$16^{n+1} \equiv 2^{n+1}~(mod \ 7)$$, $$23^{n} \equiv 2^{n}~(mod \ 7)$$, сложим:
$$37^{n+2} +16^{n+1} +23^{n } \equiv 2^{n} \cdot (2^{2}+2^{1}+1) ~(mod \ 7) \equiv 2^{n}\cdot 7~(mod \ 7)$$, то есть $$37^{n+2} +16^{n+1} +23^{n}$$ делится на $$7$$.
Пример 1.12 Найти остаток от деления числа $$(9674^{6} +28)^{15}$$ на $$39$$.
Решение. Так как $$9674 \equiv 2~(mod \ 39)$$, то $$9674^{6} \equiv 2^{6}~(mod \ 39)=64 \equiv 25~(mod \ 39)$$. Далее, $$25+28=53 \equiv 14~(mod \ 39)$$. Следовательно, $$(9674^{6} +28)^{15}\equiv 14^{15}$$. И задача теперь сведена к следующей: найти остаток от деления $$14^{15}$$ на $$39$$. Воспользуемся сравнениями: $$14\equiv -1~(mod \ 3)$$ и $$14\equiv 1 ~(mod \13)$$. Из $$14\equiv -1~(mod \ 3)$$ следует: $$14^{14}\equiv 1~(mod \ 3)$$. А из сравнения $$14\equiv 1 ~(mod \13)$$ следует: $$14^{14}\equiv 1~(mod \ 13)$$. И так как сравнение имеет место по модулям $$3$$ и $$13$$, то оно имеет место и по модулю $$39$$, являющемуся НОК чисел $$3$$ и $$13$$. Итак, $$14^{14}\equiv 1~(mod \ 39)$$. Но в таком случае $$14^{15}\equiv 14~(mod \ 39)$$.
Пусть $$a,b,m\in \mathbb{N}$$, нам необходимо вычислить $$c = a^b ~(mod \ m)$$. В дальнейшем перед нами часто будет стоять такая задача с очень большими числами $$a$$, $$b$$, $$m$$. Очевиднейший способ вычислить $$c$$ - вычислить произведение $$\underbrace{a\cdot a\cdots a}_{n\ \text{раз}}$$ и взять остаток от деления на $$m$$. Для этого потребуется $$b$$ умножений и взятие остатка от деления огромного числа (не всегда даже его хранение в памяти может быть простым) по модулю $$m$$. Приведём оптимизации для этой задачи.
Из свойства
$$((a\cdot b)~(mod \ m) \cdot c)~(mod \ m) = (a\cdot b \cdot c)~(mod \ m)$$следует, что промежуточные результаты вычислений можно перед хранением брать по модулю $$m$$.
Сгруппируем сомножители в произведении особым образом. Пусть $$b=b_0 + 2b_1 + \ldots + 2^n b_n$$, $$b_i\in\{0,1\}$$. Имеем:
$$a^b ~(mod \ m) = a^{b_0} \cdot (a^2)^{b_1} \cdot (a^4)^{b_2} \cdots \left(a^{(2^n)}\right)^{b_n} ~(mod \ m).$$Используя пункт 1, будем все промежуточные результаты хранить по модулю $$m$$. Также для деления на 2 мы будем использовать операцию сдвига бит вправо:
$$2^n b_n + 2^{n-1} b_{n-1} + \ldots + 2 \cdot b_1 + b_0 ~~\rightarrow~~ 2^{n-1} b_{n} + \ldots + 2 \cdot b_2 + b_1.$$Микропроцессоры имеют специальные инструкции, а языки программирования - специальные операторы для оптимизированного выполнения битового сдвига, которые и следует использовать при реализации данного алгоритма.
Пункт 2 даёт следующий алгоритм возведения в степень по модулю.
Вход: $$a$$, $$b$$, $$m$$ - целые неотрицательные числа.
| 1) Положить $$r=1$$, $$b'=b$$, $$x=a$$. |
| 2) Повторять, пока $$b' > 0$$: |
| 2.1) Если $$b' \equiv 1 ~(mod \ 2)$$, положить $$r:=r\cdot x ~(mod \ m)$$. |
| 2.2) Положить $$x := x^2 ~(mod \ m)$$. |
| 2.3) Сдвинуть биты числа $$b'$$ на один вправо (что эквивалентно вычислению $$b' = \lfloor b'/2 \rfloor $$). |
Выход: $$r$$ - результат возведения $$a$$ в степень $$b$$ по модулю $$m$$.
Также отметим, что на шаге 1 копирование $$b'=b$$, $$x=a$$ выполняются для того, чтобы не испортить значения $$a$$, $$b$$, которые могут передаваться в наш алгоритм по указателю или ссылке.
Определение 1.13 Функция Эйлера $$\varphi(m)$$ - количество положительных чисел, не превосходящих $$m$$ и взаимно простых с $$m$$.
Пример 1.13 Пусть $$m=9$$. Взаимно простыми с $$9$$ являются числа: $$1$$, $$2$$, $$4$$, $$5$$, $$7$$, $$8$$. Так как количество этих чисел равно $$6$$, то $$\varphi(9)=6$$.
Пример 1.14 Пусть $$m=10$$. Взаимно простые с $$10$$ числа, меньшие $$10$$ - это $$1$$,$$3$$,$$7$$, $$9$$. Поэтому $$\varphi(10)=4$$.
Рассмотрим простое число $$p$$. Все числа, меньшие $$p$$, взаимно просты с ним. Итак, $$\varphi(p)=p-1$$ для простого $$p$$.
Для чисел 9, 10 можно было вычислить значение функции Эйлера непосредственным перечислением чисел, взаимно простых с данным числом. Для числа 100 сделать это уже труднее, а для 10000 еще труднее. Оказывается, есть формула, позволяющая вычислять значение функции Эйлера достаточно просто.
Пусть задано каноническое разложение числа $$m$$:
$$m= {p}_{1}^{{\alpha }_{1}}\cdot{\dots}\cdot {p}_{k}^{{\alpha }_{k}}$$.
Тогда $$\varphi(m)=m\cdot \left(1-\frac{1}{{p}_{1}}\right){\dots}\left(1-\frac{1}{{p}_{k}}\right)$$.
Теорема 1.15 (Эйлер) Если a - такое число, что $$(a, m)=1$$, то $${a}^{\varphi (m)}\equiv 1~(mod \ m)$$.
Пример 1.16 Пусть $$a=2$$, $$m=9$$. Тогда $$\varphi(m)=6$$, и по теореме Эйлера получаем: $${2}^{6}\equiv 1~(mod \ 9)$$. В справедливости этого равенства легко убедиться, если учесть, что $${2}^{6}=64$$.
Пример 1.17 Пусть $$a=17$$, $$m=32$$. Тогда $$\varphi(32)=16$$, то по теореме Эйлера получаем: $${17}^{16}\equiv 1~(mod 32)$$. Убедиться в справедливости этого равенства непосредственным подсчётом было бы затруднительно.
Особенно простой вид теорема Эйлера принимает, если $$m=p$$ - простое число. В этом случае $$\varphi(p)=p-1$$, а потому получаем следующее утверждение:
Теорема 1.16 (малая теорема Ферма) Если $$p$$ - простое число и $$a$$ - целое число, такое, что $$(a, p)=1$$, то $${a}^{p-1}\equiv 1~(mod \ p)$$.
Часто используется следствие малой теоремы Ферма, если $$p$$ - простое число, то для любого целого числа a имеет место сравнение: $${a}^{p} \equiv a~(mod \ p)$$.
Рассмотрим примеры на применение теорем Эйлера и Ферма.
Пример 1.18 Найдём остаток отделения $${3}^{28}$$ на $$7$$.
Согласно теореме Ферма $${3}^{6}\equiv 1~(mod \ 7)$$, тогда $${3}^{24}\equiv 1~(mod \ 7)$$. Кроме того, $${3}^{4}\equiv 81\equiv 4~(mod \ 7)$$. Тогда $${3}^{28}\equiv {3}^{24\cdot }{3}^{4} ~(mod \ 7)\equiv 4$$. Следовательно, искомый остаток $$r=4$$.
Пример 1.19 Найдём остаток от деления $${243}^{132}$$ на $$34$$.
Имеем: $$243\equiv 5~(mod \ 34)$$. Тогда $${243}^{132}\equiv {5}^{132}~(mod \ 34)$$. Согласно теореме Эйлера $${5}^{\varphi (34)}\equiv 1~(mod \ 34)$$, или $${5}^{16}\equiv 1~(mod \ 34)$$. Далее делим $$132$$ на $$16$$, получим: $$132=16\cdot8+4$$. Поэтому $${5}^{132}={\left({5}^{16}\right)}^{8}\cdot {5}^{4}\equiv {5}^{4}\equiv 625\equiv 13$$. Таким образом, $${243}^{132}\equiv 13~(mod \ 34)$$.
Следовательно, $$r=13$$.
Пример 1.20 Найдем остаток от деления числа $$a=2^{18}+3^{18}+4^{18}+5^{18}+6^{18}+2$$ на $$7$$.
Решение. Числа $$1,2,3,4,5,6$$ взаимно просты с числом 7. По теореме Ферма, $$1^{6}\equiv 1~(mod 7)$$, $$2^{6}\equiv 1~(mod \ 7)$$, $$3^{6}\equiv 1~(mod \ 7)$$, $$4^{6}\equiv 1~(mod \ 7)$$, $$5^{6}\equiv 1~(mod \ 7)$$, $$6^{6}\equiv 1~(mod \ 7)$$. Возведем эти сравнения в третью степень и сложим, получим: $$1^{18}+2^{18}+3^{18}+4^{18}+5^{18}+6^{18}\equiv 6~(mod \ 7)\equiv -1~(mod \ 7)$$. Следовательно, $$1+1^{18}+2^{18}+3^{18}+4^{18}+5^{18}+6^{18}\equiv 0$$, то есть число $$a$$ делится на 7 без остатка.
Пример 1.21 Найти остаток от деления $$7^{402}$$ на $$101$$.
Решение. Число 101 простое, $$(7,101)=1$$, $$\varphi(101)=100$$. По теореме Ферма, $$7^{100}\equiv 1~(mod \ 101)$$. Возведем это сравнение в четвертую степень, получим: $$7^{400}\equiv 1~(mod \ 101)$$. Умножим полученное сравнение на сравнение $$7^{2}\equiv 49~(mod \101)$$. Итак, $$7^{402}\equiv 49~(mod \101)$$, то есть остаток равен 49.
Пример 1.22 Доказать, что $$73^{12}-1$$ делится на $$105$$.
Решение. Разложим на множители: $$105=3\cdot5\cdot7$$. Далее, $$(73,3)=(73,5)=(73,7)=1$$. По теореме Ферма, $$73^{2}\equiv 1~(mod \ 3)$$, $$73^{4}\equiv 1~(mod \ 5)$$, $$73^{6}\equiv 1~(mod \ 7)$$. Возведем первое сравнение в шестую степень, второе в третью степень, третье во вторую, получим: $$73^{12}\equiv 1~(mod \ 3)$$, $$73^{12}\equiv 1~(mod \ 5)$$, $$73^{12}\equiv 1~(mod \ 7)$$. А отсюда следует, что $$73^{12}\equiv 1~(mod \ 105)$$, так как 105- наименьшее общее кратное чисел 3, 5, 7.
Определение 1.14 Число $$b$$ называется обратным к $$a$$ по модулю $$m$$, если $$a\cdot b\equiv 1(mod \ m)$$. Пишут: $$b= a^{-1} ~(mod \ m)$$.
Например, 3 обратно к 2 по модулю 5, так как $$2\cdot3\equiv 1~(mod \ 5)$$. Заметим, что обратное к $$a$$ по модулю $$m$$ можно найти лишь в случае $$(a,m)=1$$. Если $$(a,m)=d>1$$, то обратный к $$a$$ по модулю $$m$$ не существует. Например, обратного к 2 по модулю 10 не существует: при умножении любого числа $$b$$ на 2 мы не получим 1 по модулю 10. Если модуль сравнения $$m$$- простое число, то обратный элемент есть для каждого числа.
Пример 1.23 Найдем число, обратное к $$26$$ по модулю $$49$$.
Числа 26 и 49 взаимно просты, поэтому искомое число существует. Реализуем расширенный алгоритм Евклида для чисел 26 и 49.
| Имеем: $$49=1 \cdot 26+23$$, |
| $$26=1 \cdot 23+3$$, |
| $$23=7 \cdot 3+2$$, |
| $$3=1 \cdot 2+1$$. |
И теперь $$1=3 - 1 \cdot 2=3-1 \cdot (23-7 \cdot 3)=%-1 \cdot 23+8 \cdot 3=-1 \cdot 23+8 \cdot (26-1 \cdot 23)=%8 \cdot 26-9 \cdot 23=8 \cdot 26-9 \cdot (49-1 \cdot 26)=%-9 \cdot 49+17 \cdot 26$$. Итак, $$49 \cdot (-9)+17 \cdot 26=1$$. То есть $$26 \cdot 17\equiv 1~(mod \ 49)$$. Таким образом, число 17 является обратным к 26 по модулю 49.
Сравнение с одним неизвестным $$x$$ имеет вид
$${a}_{n}{x}^{n}+{a}_{n-1}{x}^{n-1}+{\dots}+{a}_{1}x+{a}_{0} \equiv 0~(mod \ m),$$где $$m \in \mathbb{N}$$, $$m>1$$. Если $${a}_{n}$$ не делится на $$m$$, то $$n$$ называется степенью сравнения (1.3).
Определение 1.15 Решением сравнения (1.3) называется всякое целое число $${x}_{0}$$, для которого $${a}_{n}{x}_{0}^{n}+{a}_{n-1}{x}_{0}^{n-1}+{\dots}+{a}_{0} \equiv 0 ~(mod \ m)$$.
Если $${x}_{0}$$ удовлетворяет сравнению (1.3), то, согласно свойству 11 сравнений, этому сравнению будут удовлетворять все целые числа, сравнимые с $${x}_{0}$$ по модулю $$m$$. Поэтому все числа, сравнимые по модулю $$m$$ с $${x}_{0}$$, будем рассматривать как одно решение. Другими словами, решениями сравнения (1.3) будут классы чисел. Например, $$\bar{1}$$ - это класс единицы, то есть все числа, сравнимые с 1, $$\bar{2}$$ - класс числа 2, то есть все числа, сравнимые с 2, т.д. И фразу "данное сравнение имеет 2 решения" надо понимать так: данному сравнению удовлетворяют два класса чисел. Как отмечалось выше, эти классы не имеют общих элементов. В дальнейшем мы записываем какое-либо число - представитель класса без черты сверху, называя это число решением.
Сравнения, множества решений которых совпадают, называются равносильными.
Любое сравнение первой степени с одним неизвестным $$x$$ можно привести к виду
$$ax \equiv b~(mod \ m),$$где $$a \not\equiv 0 ~(mod \ m)$$.
Выясним условия, при которых сравнение (1.4) имеет:
Теорема 1.17 Для того, чтобы сравнение (1.4) имело хотя бы одно решение, необходимо и достаточно, чтобы число $$b$$ делилось на $$НОД(a,m)$$.
Пример 1.24 Сравнение $$9x\equiv 6~(mod \12)$$ имеет решение, так как $$6$$ делится на $$3=НОД(9,12)$$.
Пример 1.25 Сравнение $$6x\equiv 9 ~(mod \12)$$ не имеет решений, так как $$НОД(6,12)=6$$, а $$9$$ не делится на $$6$$.
Теорема 1.18 Пусть сравнение (1.4) разрешимо и $$d=НОД(a,m)$$. Тогда множество решений сравнения (1.4) состоит из $$d$$ классов по модулю $$m$$, а именно, если $${x}_{0}$$ - одно из решений, то все другие решения - это $${x}_{0}+m_1, {x}_{0}+2m_1,{\dots}, {x}_{0}+(d-1)m_1$$, где $$m_1= \frac{m}{d}$$.
Пример 1.26 Сравнение $$9x\equiv 6~(mod \ 12)$$ имеет ровно три решения, так как $$НОД(9,12)=3$$. Эти решения: $${x}_{0}=2$$, $${x}_{0}+4=6$$, $${x}_{0}+2 \cdot 4=10$$.
Пример 1.27 Сравнение $$11x\equiv 2~(mod \ 15)$$ имеет единственное решение $${x}_{0}=7$$, т.к. $$НОД(11,15)=1$$.
Покажем, как решать сравнение первой степени. Рассмотрим случай $$НОД(a,m)=1$$. Тогда решение сравнения (1.4) можно искать, например, по алгоритму Евклида. Действительно, используя расширенный алгоритм Евклида, представим число 1 в виде линейной комбинации чисел $$a$$ и $$m$$: $$1=aq+mr$$.
Умножим обе части этого равенства на $$b$$, получим: $$b=abq+mrb$$, откуда $$abq-b=-mrb$$, то есть $$a \cdot (bq) \equiv b~(mod \ m)$$ и $$bq$$ - решение сравнения (1.4).
Другой способ: использовать теорему Эйлера. Пусть, снова, $$НОД(a,m)=1$$. Применяем теорему Эйлера: $${a}^{\varphi (m)}\equiv 1~(mod \ m)$$. Умножим обе части сравнения на $$b$$: $${a}^{\varphi (m)}b \equiv b~(mod \ m)$$. Переписывая последнее выражение в виде $$a( {a}^{\varphi (m)-1}b) \equiv b~(mod \ m)$$, получаем, что $${a}^{\varphi (m)-1}b$$ - решение сравнения (1.4).
Допустим теперь, что $$НОД(a,m)=d>1$$. Тогда $$a=a_1 d$$, $$m=m_1 d$$, где $$НОД(a_1,m_1)=1$$. Кроме того, необходимо $$b=b_1 d$$ для того, чтобы сравнение было разрешимо. Если $${x}_{0}$$ - решение сравнения $$a_1 x\equiv b_1 ~(mod \ m_1)$$, причем единственное, поскольку $$НОД(a_1,m_1)=1$$, то $${x}_{0}$$ будет решением и сравнения $$a_1 dx\equiv b_1 d ~(mod \ m_1) d$$, то есть исходного сравнения (1.4). Остальные решения (их $$d-1$$) находим по теореме.
Итак, если $$НОД(a,m)=1$$, то сравнение (1.4) имеет единственное решение, и решением сравнения является класс $$x=ba^{\varphi(m)-1}~(mod \ m)$$. Если $$НОД(a,m)=d>1$$, $$b$$ не делится на $$d$$, то сравнение решений не имеет. Если $$b$$ делится на $$d$$, то сравнение имеет $$d$$ различных решений. Все эти решения образуют один класс по модулю $$\frac{m}{d}$$.
Пример 1.28 Решим сравнение: $$12x\equiv 9~(mod \ 21)$$$.
Вычисляем $$НОД(12,21)=3$$. Число 9 делится на 3, поэтому сравнение разрешимо, и у него три решения. Поделим обе части сравнения и модуль на их наибольший общий делитель: $$4x\equiv 3 ~(mod \ 7)$$. Поскольку $$НОД(4, 7)=1$$, можем воспользоваться теоремой Эйлера: $${x}_{0}={4}^{\varphi \left(7\right)-1} \cdot 3 \equiv {4}^{5} \cdot 3 \equiv 6 ~(mod \ 7)$$.
Поясним:$$\varphi(7)=6$$, $$4^{2}=16\equiv 2~(mod \ 7)$$, поэтому $${4}^{5}\equiv 4^{2} \cdot 4^{2} \cdot 4\equiv 2 \cdot 2 \cdot 4\equiv 2$$, и $$2 \cdot 3\equiv 6$$.
Таким образом, 6 - это одно из решений сравнения $$12x\equiv 9 ~(mod \ 21)$$. Находим остальные решения:
$$6+ \frac{21}{3} =6+7=13, 6+2 \cdot \frac{21}{3} =6+14=20.$$Проверка: $$12 \cdot 6-9=63=21 \cdot 3$$; $$12 \cdot 13-9=147=21 \cdot 7$$; $$12 \cdot 20-9=231=21 \cdot 11$$.
Пример 1.29 $$45 x \equiv 31~(mod \ 100)$$.
Так как $$НОД(45,100)=5$$, а 31 не делится на 5, то решений сравнение $$45 x \equiv 31~(mod \ 100)$$ не имеет.
Пример 1.30 $$51 x \equiv 141~(mod \ 234)$$.
Поскольку $$НОД(51,234)=3$$, $$141 \, \vdots \, 3$$, то сравнение имеет 3 решения. После деления обеих частей и модуля на 3 получим сравнение: $$17 x \equiv 47~(mod \ 78)$$. Решение этого сравнения: $$x \equiv 67~(mod \ 78)$$.
Решения исходного сравнения найдём по теореме 1.18: $$x \equiv 67~(mod \ 234)$$, $$x \equiv 67+78 \equiv 145~(mod \ 234)$$, $$x \equiv 67+2\cdot 78 \equiv 223~(mod \ 234)$$.
Пусть $$t=\dfrac{a}{b}$$, $$b>0$$, $$a$$, $$b$$ - целые. Число $$t$$ можно представить в виде дроби особого вида. Это представление получается из алгоритма Евклида. Применим алгоритм Евклида к числам $$a$$ и $$b$$. Получим:
$$ \begin{array}{lll} a=b\cdot q_0+r_1, \vphantom{\rule{0em}{2 em}} \hphantom{\rule{4em}{1em}} \dfrac{a}{b}=q_0+\dfrac{r_1}{b},\\ b=r_1\cdot q_1+r_2, \vphantom{\rule{0em}{2 em}} \hphantom{\rule{4em}{1em}} \dfrac{b}{r_1}=q_1+\dfrac{r_2}{r_1},\\ r_1=r_2\cdot q_2+r_3,\vphantom{\rule{0em}{2 em}} \hphantom{\rule{4em}{1em}} \dfrac{r_1}{r_2}=q_2+\dfrac{r_3}{r_2},\\ \cdots \vphantom{\rule{0em}{2 em}} \hphantom{\rule{4em}{1em}} \cdots \\ r_{n-2}=r_{n-1}\cdot q_{n-1}+r_n, \vphantom{\rule{0em}{2em}} \hphantom{\rule{4em}{1em}} \dfrac{r_{n-2}}{r_{n-1}}=q_{n-1}+\dfrac{r_n}{r_{n-1}},\\ r_{n-1}=r_n\cdot q_n,\vphantom{\rule{0em}{2 em}} \hphantom{\rule{4em}{1em}} \dfrac{r_{n-1}}{r_n}=q_n \end{array} $$Из второго равенства получаем:
$$\dfrac{r_1}{b}=\dfrac{1}{q_1+\dfrac{r_2}{r_1}}.$$Подставим это выражение в первое из равенств (1.5), получим:
$$\frac{a}{b}=q_0+\dfrac{1}{q_1+\dfrac{r_2}{r_1}}.$$Третье из равенств (1.5) даёт:
$$\frac{r_2}{r_1}=\dfrac{1}{q_2+\dfrac{r_3}{r_2}}.$$Подставим это выражение в (1.7), получим:
$$\frac{a}{b}=q_0+\dfrac{1}{q_1+\dfrac{1}{q_2+\dfrac{r_3}{r_2}}}.$$Продолжая действовать аналогично, за конечное число шагов получим:
$$\frac{a}{b}=q_0+\dfrac{1}{q_1+\dfrac{1}{q_2+\dfrac{1}{q_3+\dots+\dfrac{1}{q_n}}}}.$$Определение 1.16 Дробь вида (1.8) называется конечной цепной (другое название: непрерывной) дробью.
Сокращенная (и, конечно, более удобная) запись: $$[q_0; q_1,q_2,q_3,\dots,q_n]$$.
Числа $$q_0 \, \vdots \, q_1,q_2,q_3,\dots,q_n$$ называются неполными частными, все они - целые, а начиная с $$q_1$$ - натуральные.
Равенство вида (1.8) называется представлением рационального числа конечной цепной дробью.
Теорема 1.19 Всякое рациональное число может быть представлено в виде конечной цепной дроби.
Пример 1.31
Если допустить, что последнее неполное частное может равняться 1, то для всякого рационального числа можно получить два представления в виде конечной цепной дроби.
Пример 1.32 $$2+\dfrac{1}{5+\dfrac{1}{3}}=2+\dfrac{1}{5+\dfrac{1}{2+\dfrac{1}{1}}}$$
Теорема 1.20 Представление рационального числа в виде конечной цепной дроби, такой, что последнее неполное частное отлично от $$1$$, единственно.
Имеет место простая, но важная
Теорема 1.21 Всякая конечная цепная дробь есть рациональное число.
Определение 1.17 Дроби $$\delta_0 = \dfrac{{P}_{0}}{{Q}_{0}}= \dfrac{{q}_{0}}{1}$$, $$\delta_1 = \dfrac{{P}_{1}}{{Q}_{1}}= {q}_{0}+ \dfrac{1}{{q}_{1}}$$, $$\delta_2 = \dfrac{{P}_{2}}{{Q}_{2}}=q_0+\dfrac{1}{q_1+\dfrac{1}{q_2}}$$ и т.д. называются подходящими дробями цепной дроби (1.8) или соответствующего ей числа $$\dfrac{a}{b}$$.
Очевидно, что последняя подходящая дробь $$\delta_n = \dfrac{{P}_{n}}{{Q}_{n}}$$ есть число $$\dfrac{a}{b}$$. Каждая подходящая дробь есть некоторое рациональное число. Заметим, что $$s$$-я подходящая дробь $$\delta_s$$ получается заменой $${q}_{s-1}$$ на $${q}_{s-1}+\frac{1}{{q}_{s}}$$.
Подходящие дроби последовательно можно представить в виде:
$$\delta_0 = \frac{{q}_{0}}{1}=\frac{{P}_{0}}{{Q}_{0}}, \quad \delta_1 = {q}_{0}+ \frac{1}{{q}_{1}}= \frac{{P}_{1}}{{Q}_{1}}$$ $${\delta }_{2}={q}_{0}+\dfrac{1}{{q}_{1}+\dfrac{1}{{q}_{2}}}={q}_{0}+\dfrac{{q}_{2}}{{q}_{1}{q}_{2}+1}=\dfrac{{q}_{0}{q}_{1}{q}_{2}+{q}_{0}+{q}_{2}}{{q}_{1}{q}_{2}+1}=\dfrac{\left({q}_{0}{q}_{1}+1\right){q}_{2}+{q}_{0}}{{q}_{1}{q}_{2}+1}=\\\dfrac{{P}_{1}{q}_{2}+{P}_{0}}{{Q}_{1}{q}_{2}+{Q}_{0}}=\dfrac{{P}_{1}}{{Q}_{2}}.$$Общая формула имеет вид:
$${\delta }_{s}=\frac{{P}_{s}}{{Q}_{s}}=\frac{{P}_{s-1}{q}_{s}+{P}_{s-2}}{{Q}_{s-1}{q}_{s}+{Q}_{s-2}}.$$Напомним кратко основные свойства цепных дробей.
Одно уравнение с несколькими неизвестными имеет, как правило, бесконечное множество решений. Поэтому такие уравнения называют неопределенными. В теории чисел рассматривают задачу отыскания целочисленных решений неопределенных уравнений (их еще называют диофантовыми по имени древнегреческого математика Диофанта). Связь сравнений и диофантовых уравнений дается следующей теоремой.
Теорема 1.22 Если $$({x}_{0}, {y}_{0})$$ - целочисленное решение неопределенного уравнения $$ax+by=c$$, где $$a$$, $$b$$, $$c$$ - целые числа, $$a \neq 0$, $b \neq 0$$, то $$x_0$$ - решение сравнения $$ax_0=c ~(mod \ b)$$.
Обратно, если $$x_0$$ - решение сравнения $$ax=c ~(mod \ b)$$, то существует такое целое число $$y_0$$, что $$(x_0, y_0)$$ - решение неопределенного уравнения $$ax+by=c$$.
Эта теорема позволяет свести решение неопределенных уравнений вида $$$ax+by=c$$ к решению сравнений первой степени, и обратно. В частности, из приведенных выше утверждений о сравнениях первой степени легко получается
Теорема 1.23 Если $$НОД(a,b)=d$$, то неопределенное уравнение $$ax+by=c$$ имеет целочисленное решение в том и только в том случае, когда $$c$$ делится на $$d$$.
В частности, если $$НОД(a,b)=1$$, то урвнение $$ax+by=c$$ при любом целом c имеет целочисленное решение.
Процесс нахождения целочисленных решений уравнений вида $$ax+by=c$$ состоит из даух этапов: нахождение хотя бы одного такого решения и нахождение общего вида таких решений. Рассмотрим сначала второй этап.
Теорема 1.24 Если известно частное целочисленное решение $$({x}_{0}, {y}_{0})$$ неопределенного уравнения $$ax+by=c$$ и $$НОД(a,b)=d$$, то общее решение этого уравнения имеет вид $$x= {x}_{0}-\dfrac{b}{d}t$$, $$y= {y}_{0}+\dfrac{a}{d}t$$, где $$t$$ пробегает множество целых чисел.
Для нахождения частных решений применяют те же способы, что и для решения сравнений (например, можно использовать теорему Эйлера). Покажем, как искать решения неопределенных уравнений (а тем самым и сравнений) с помощью цепных дробей.
Из предыдущего следует, что общее решение уравнения имеет вид:
$$x= {(-1)}^{n-1} c {Q}_{n-1}-bt, y= {(-1)}^{n} c {P}_{n-1}+at,$$где $${P}_{n-1}$ и ${Q}_{n-1}$$ - числитель и знаменатель предпоследней подходящей дроби разложения $$\frac{a}{b}$$ в цепную дробь, а $$t$$ - любое целое число.
Пример 1.33 Решим в целых числах уравнение $$142x+82y=6$$.
Решение. Так как $$НОД(142,82)=2$$ и $$6\, \vdots \,2$$, то уравнение имеет решение. Данное уравнение равносильно уравнению $$71x+41y=3$$.
Разложим $$\dfrac{71}{41}$$ в цепную дробь : $$\dfrac{71}{41}=[1; 1,2,1,2,1,2]$$.
Составим все подходящие дроби:
$$\frac{{P}_{0}}{{Q}_{0}}= \frac{1}{1},~~ \frac{{P}_{1}}{{Q}_{1}}=\frac{2}{1},~~\frac{{P}_{2}}{{Q}_{2}}= \frac{5}{3},~~ \frac{{P}_{3}}{{Q}_{3}}=\frac{7}{4},~~\frac{{P}_{4}}{{Q}_{4}}=\frac{19}{11},~~ \frac{{P}_{5}}{{Q}_{5}}=\frac{26}{15},~~\frac{{P}_{6}}{{Q}_{6}}=\frac{71}{41}.$$На основании свойства подходящих дробей $${P}_{k-1}{Q}_{k}- {P}_{k}{Q}_{k-1}= {(-1)}^{k}$$ Получим: $$26\cdot41-71\cdot15= {(-1)}^{6}$$, или $$71\cdot(-15)+41\cdot26=1$$.
Умножив обе части равенства на 3, находим: $$71\cdot(-45)+41\cdot78=3$$, т.е. $${x}_{0}=-45$$, $${y}_{0}=78$$ - частное решение данного уравнения.
Все решения могут быть найдены по формулам: $$x=-45+41t$$, $$y=78-71t$$, или $$x=-4+41t$$, $$y=7-71t$$, где $$t$$ принимает любые целые значения.
Рассмотрим систему сравнений первой степени:
$$x\equiv {a}_{1} (mod \ {m}_{1}), x\equiv {a}_{2} (mod \ {m}_{2}), {\dots}, x\equiv {a}_{r} (mod \ {m}_{r}),$$где числа $${m}_{1},{m}_{2},...,{m}_{r}$$ попарно взаимно простые, и найдём значение $${x}_{0} \in \mathbb{Z}$$, удовлетворяющее всем $$r$$ сравнениям.
Теорема 1.25 (китайская теорема об остатках) Пусть $${m}_{1},{m}_{2},...,{m}_{r}$$ - попарно взаимно простые, и числа $${a}_{1},{a}_{2},...,{a}_{r}$$ - произвольные целые. Тогда существует единственное такое целое число $${x}_{0}$$, что $$0 \leq x_{0} < {m}_{1} \cdot {m}_{2} \cdot \dots \cdot {m}_{r}$$ и $${x}_{0}\equiv{a}_{1}~(mod \ {m}_{1})$$, $${x}_{0}\equiv {a}_{2}~(mod \ {m}_{2}), {\dots}, {x}_{0}\equiv {a}_{r}~(mod \ {m}_{r})$$.
$${x}_{0}\equiv \sum _{i=1}^{r}{{a}_{1}}{M}_{i}{N}_{i}~(mod \ m_1) \cdot {m}_{2} \cdot ... \cdot {m}_{r},$$где $${M}_{i}={m}_{1} \cdot {\dots}{ \cdot m}_{i-1} \cdot {m}_{i+1} \cdot {\dots}{ \cdot m}_{r}$$ и $${N}_{i}{ \equiv M}_{i}^{-1}~(mod \ m_i)$$.
Пример 1.34 Решим систему сравнений $$x\equiv 2 ~(mod \ 5)$$, $$x\equiv 3 ~(mod \ 6)$$, $$x\equiv 4 ~(mod \ 7)$$.
Вычисляем: $${M}_{1}=6 \cdot 7=42$$, $${M}_{2}=5 \cdot 7=35$$, $${M}_{3}=5 \cdot 6=30$$. Находим обратные числа:
$${N}_{1} \equiv {42}^{-1} \equiv {2}^{-1} \equiv 3mod5; $$ $${N}_{2} \equiv {35}^{-1} \equiv {5}^{-1} \equiv 5mod6; $$ $${N}_{3} \equiv {30}^{-1} \equiv {2}^{-1} \equiv 4mod7.$$Подставляем значения в формулу (1.10):
$${x}_{0}\equiv 2 \cdot 42 \cdot 3+3 \cdot 35 \cdot 5+4 \cdot 30 \cdot 4=252+525+480=1257\equiv 207 ~(mod \ 210).$$Проверка: $$207-2=205=5 \cdot 41$$, то есть $$207\equiv 2 ~(mod \ 5)$$; $$207-3=204=6 \cdot 34$$, то есть $$207\equiv 3 ~(mod \ 6)$$; $$207-4=203=7 \cdot 29$$, то есть $$207\equiv 4 ~(mod \ 7)$$.
Теорема 1.26 Система сравнений $$x={a}_{i} ~(mod \ n_i),i=1,{\dots},k$$, имеет решение $$x_0$$ тогда и только тогда, когда $${a}_{i}={a}_{j}~(mod НОД(n_i,n_j))$$, причем такое $$x_0$$ с условием $$0\leq x_0<\LCM({n}_{1},{\dots},{n}_{k})$$ - единственное.
Для решения системы найдём $$N=\LCM\left({n}_{1},{\dots},{n}_{k}\right)={p}_{1}^{{j}_{1}}{p}_{2}^{{j}_{2}}{\dots}{p}_{r}^{{j}_{r}}$$, где $${p}_{i}$$ - попарно различные простые числа. Для каждого делителя $${p}_{i}^{{j}_{i}}$$ найдём номер $${l}_{i}$$ такой, что $${n}_{{l}_{i}}$$ делится на него, и число $${b}_{i}={a}_{{l}_{i}}~(mod p_{i}^{{j}_{i}})$$. Полученная система $$x={b}_{i}~(mod p_{i}^{{j}_{i}})$$ будет иметь взаимно простые модули, и единственное её решение $$x_0$$ с условием $$0\leq x_0<\LCM({n}_{1},{\dots},{n}_{k})$$ даёт Китайская теорема об остатках.
Пример 1.35 Решим систему уравнений: $$x=12mod14$$, $$x=4mod18$$, $$x=4mod12$$.
Решение. Нетрудно убедиться, что наша система удовлетворяет условию теоремы. Решим её. Найдём $$\LCM\left(14,18,12\right)=4 \cdot 9 \cdot 7=252.$$ На 4, 7 и 9 делятся, соответственно, 12, 14 и 18. Следовательно, исходная система эквивалентна системе: $$x=0mod4$$, $$x=4mod9$$ и $$x=5mod7$$. Решение $$x=40mod252$$ последней системы находим по китайской теореме об остатках.
Определение. Число $$a$$ называется квадратичным вычетом по модулю $$m$$, если сравнение $$x^2 \equiv a (mod \ m)$$ имеет решение при некотором целом $$x$$, если сравнение $$x^2 \equiv a (mod \ m)$$ не имеет решений, то $$a$$ называют квадратичным невычетом.
Определение. Символ Лежандра определяется следующим образом:
$$\left(\frac{a}{p}\right)=\left\{\begin{array}{rl}0, \text{если $a$ делится на $p$};\\1, \text{если $a$ - квадратичный вычет}~(mod \ p);\\-1, \text{если $a$ - квадратичный невычет}~(mod \ p).\end{array}\right$$Следующие свойства используются для вычисления символа Лежандра:
Пример 1.36 Найти случайный квадратичный невычет по модулю $$449$$.
Решение. Будем выбирать числа случайно, и тестировать их с помощью символа Лежандра.
Пусть выбранное нами случайное число оказалось 51:
$$\left(\frac{51}{449}\right)=\left[\text{по свойству 3}\right]=\left(\frac{3}{449}\right)\left(\frac{17}{449}\right)=\left[\text{по свойству 5}\right]=\\{\left(-1\right)}^{\frac{448 \cdot 2}{4}}\left(\frac{449}{3}\right){\left(-1\right)}^{\frac{448 \cdot 16}{4}}\left(\frac{449}{17}\right)=\left[\text{по свойству 2}\right]=\left(\frac{2}{3}\right)\left(\frac{7}{17}\right).$$По свойству 1,
$$\left(\frac{2}{3}\right)={2}^{\frac{3-1}{2}}=-1mod3.$$Далее,
$$\left(\frac{7}{17}\right)={\left(-1\right)}^{\frac{16 \cdot 6}{4}}\left(\frac{17}{7}\right)=\left(\frac{3}{7}\right)={\left(-1\right)}^{\frac{6 \cdot 2}{4}}\left(\frac{7}{3}\right)=-\left(\frac{1}{3}\right)=-1.$$Итак, 51 - квадратичный вычет по модулю 449. Выберем другое число. Пусть выпало число 34.
$$\left(\frac{34}{449}\right)=\left(\frac{2}{449}\right)\left(\frac{17}{449}\right)={\left(-1\right)}^{\frac{{449}^{2}-1}{8}}\left(\frac{17}{449}\right)=\left(\frac{17}{449}\right)=\left(\frac{449}{17}\right)=\\ \left(\frac{7}{17}\right)=-1.$$Следовательно, число 34 является квадратичным вычетом по модулю 449.
Очевидным недостатком символа Лежандра является необходимость иногда применять свойство 3, требующее факторизации числа. Обобщение числа Лежандра, символ Якоби, который определяется для произвольного числа $$a$$ и нечетного числа $$n={p}_{1}{p}_{2}{\dots}{p}_{k}$$, где числа $${p}_{i}$$ - простые не обязательно различные числа, лишен этого недостатка.
По определению,
$$\left(\frac{a}{n}\right)=\left(\frac{a}{{p}_{1}}\right) \cdot \left(\frac{a}{{p}_{2}}\right){\dots}\left(\frac{a}{{p}_{k}}\right).$$Поскольку при простом $$n$$ символ Якоби равен символу Лежандра, одинаковое обозначение не введёт нас в заблуждение. Отметим, что символ Якоби не является полным аналогом символа Лежандра, т.е. равенство
$$\left(\frac{a}{n}\right)=\left\{\begin{array}{rl}0, \text{если $a$ не взаимно просто с } n;\\1, \text{если $a$ - квадратичный вычет}~(mod n);\\-1, \text{если $a$ - квадратичный невычет}~(mod n)\end{array}\right.$$в общем случае не выполняется.
Свойства символа Якоби:
Повторим наши вычисления из примера с помощью символа Якоби:
$$\left(\frac{51}{449}\right)={\left(-1\right)}^{\frac{448 \cdot 50}{4}}\left(\frac{449}{51}\right)=\left(\frac{41}{51}\right)={\left(-1\right)}^{\frac{50 \cdot 40}{4}}\left(\frac{51}{41}\right)=\left(\frac{10}{41}\right)=\\\left(\frac{2}{41}\right)\left(\frac{5}{41}\right)={\left(-1\right)}^{\frac{{41}^{2}-1}{8}}{\left(-1\right)}^{\frac{40 \cdot 4}{2}}\left(\frac{41}{5}\right)=1 \cdot 1 \cdot \left(\frac{1}{5}\right)=1.$$В некоторых криптографических алгоритмах требуется извлечение квадратного корня в кольце вычетов.
Задача нахождения квадратного корня по произвольному составному модулю сводится к задаче нахождения квадратного корня по простому модулю с помощью китайской теоремы об остатках. Для последней задачи существует много различных подходов. Один из них, алгоритм Тонелли-Шенкса, мы рассмотрим ниже.
Пусть $$p={2}^{s}q+1$$, где $$q$$ - нечетное число, $$z$$ - произвольный квадратичный невычет. Положим $$c={z}^{q}$$ и будем искать корень $$x=\sqrt{a}~(mod \ p)$$ в виде:
$$x={a}^{\frac{q+1}{2}} \cdot {c}^{{\alpha }_{0}+2{\alpha }_{1}+4{\alpha }_{2}+{\dots}}.$$Подставив в равенство $${x}^{{2}^{s-1}}={a}^{{2}^{s-2}}~(mod \ p)$$ выражение для $$x$$. Поскольку
$${\left({c}^{2{\alpha }_{1}+4{\alpha }_{2}+{\dots}}\right)}^{{2}^{s-1}}={z}^{q \cdot {2}^{s}({\alpha }_{1}+2{\alpha }_{2}+{\dots})}={z}^{(p-1)({\alpha }_{1}+2{\alpha }_{2}+{\dots})}=1~(mod \ p),$$то получим:
$${a}^{\frac{p-1}{4}} \cdot {a}^{{2}^{s-2}} \cdot {z}^{\frac{p-1}{2} \cdot {\alpha }_{0}}={a}^{{2}^{s-2}}~(mod \ p).$$Далее, заметим, что $${z}^{\frac{p-1}{2}}=\left(\dfrac{z}{p}\right)~(mod \ p)=-1$$, так как $$z$$ - квадратичный невычет, а $${a}^{\frac{p-1}{2}}=1~(mod \ p)$$, так как $$a$$ - квадратичный вычет. Поэтому $${a}^{\frac{p-1}{4}}$$ есть корень из единицы, и может быть либо 1, либо $$-1$$. В первом случае берём $${\alpha }_{0}=0$$, во втором $${\alpha }_{0}=1$$. В результате мы получаем:
$${a}^{\frac{p-1}{4}}{c}^{{{2}^{s-2}\alpha }_{0}}=1 \ mod \ p$$Теперь в равенство $${x}^{{2}^{s-2}}={a}^{{2}^{s-3}}~(mod \ p)$$ подставим выражение для $$x$$ и получим:
$${a}^{\frac{p-1}{8}}{a}^{{2}^{s-3}}{z}^{\frac{p-1}{4}{\alpha }_{0}+\frac{p-1}{2}{\alpha }_{1}}={a}^{{2}^{s-3}}~(mod \ p).$$Аналогично предыдущему, $${z}^{\frac{p-1}{2}{\alpha }_{1}}=-1~(mod \ p)$$, а $${a}^{\frac{p-1}{8}}{z}^{\frac{p-1}{4}{\alpha }_{0}}$$ является корнем из единицы и может быть либо 1, либо $$-1$$. В первом случае берём $${\alpha }_{1}=0$$, во втором $${\alpha }_{1}=1$$. Рассматривая аналогично равенства $${x}^{{2}^{s-3}}={a}^{{2}^{s-4}}~(mod \ p)$$, $${x}^{{2}^{s-4}}={a}^{{2}^{s-5}}~(mod \ p)$$, $$\dots$$, $${x}^{2}=a~(mod \ p)$$, мы найдём все коэффициенты $${\alpha }_{i}$$.
Данная идея реализуется алгоритмом Тонелли-Шенкса [2]:
Вход: $$p$$ - простое число, $$a$$ - квадратичный вычет по модулю $$p$$.
Выход: число $$x$$ такое, что $${x}^{2}=a~(mod \ p)$$.
Отметим, что на каждом шаге числа и $${b}_{i}$$ и $${t}_{i}$$ имеют мультипликативный порядок степень двойки, причем на каждом шаге он понижается, поэтому алгоритм задан корректно. Для нахождения порядка $$t_i$$ на шаге 5 нужно последовательно возводить его в степень.
Алгоритм Тонелли-Шенкса не позволяет находить корень по $$p$$-примарному модулю. Для решения этой задачи нам потребуется следующая идея. Если $$a$$ не делится на $$p$$, и мы вычислили $${x}_{0}$$ - корень из $$a$$ по модулю $$p$$, то корень $${x}_{1}$$ из $$a$$ по модулю $${p}^{n}$$ можно искать в виде $$x={x}_{0}+p{t}_{1}$$. Тогда мы получим:
$${x}^{2}={x}_{0}^{2}+2p{t}_{1}{x}_{0}+{p}^{2}{t}_{1}^{2}=a ~(mod {p}^{2}).$$Поскольку $${x}_{0}^{2}-a$$ делится на $$p$$, то имеем:
$$\frac{{x}_{0}^{2}-a}{p}+2{t}_{1}{x}_{0}=0~(mod \ p^{2}).$$Отсюда находим
$${t}_{1}={t'}_{1}+p{t}_{2},\ {t'}_{1}=\frac{-{{x}_{0}^{2}-a}}{p} \cdot \left({\left(2{x}_{0}\right)}^{-1}~(mod \ p)\right),\ {x}_{1}={x}_{0}+p{t'}_{1}.$$Отметим, что $${x}_{1}^{2}=a~(mod {p}^{2})$$, $$x={x}_{1}+{p}^{2}{t}_{2}$$. Тогда имеем:
$${x}^{2}={x}_{1}^{2}+2{p}^{2}{t}_{2}{x}_{1}+{p}^{4}{t}_{2}^{2}=a~(mod {p}^{2}).$$Поскольку $${x}_{1}^{2}-a$$ делится на $${p}^{2}$$, то имеем:
$$\frac{{x}_{1}^{2}-a}{{p}^{2}}+2{t}_{2}{x}_{1}=0~(mod {p}^{2}).$$Отсюда находим
$${t}_{2}={t'}_{2}+{p}^{2}{t}_{3},\ {t'}_{2}=\frac{-{{x}_{1}^{2}-a}}{{p}^{2}} \cdot \left({\left(2{x}_{1}\right)}^{-1}~(mod \ p)\right),\ {x}_{2}={x}_{1}+{p}^{2}{t'}_{2}.$$Продолжая последовательность $${x}_{i}$$ по описанному принципу, мы найдём $${x}_{n-1}^{2}=a~(mod \ p^{n}).$$
Если $$a$$ делится на $$p$$, имеем:
$${x}^{2}={a'}{p}^{v}+r{p}^{m},$$и $$x$$ делится на $$p$$. Следовательно, решение есть тогда и только тогда, когда $$a$$ делится на четную степень $$p$$, поэтому далее можем писать:
$${x}^{2}={a'}{p}^{2k}+r{p}^{m},\ x={p}^{k}\widetilde{x}.$$В этом случае два решения $$\pm \widetilde{x}$$ находим из уравнения $${\widetilde{x}}^{2}={a'}~(mod {p}^{m-2k})$$. Найдём остальные решения $$\pm \widetilde{x}+b$$ из уравнения:
$${p}^{2k}{\widetilde{x}}^{2}\pm 2{p}^{2k}\widetilde{x}b+{{p}^{2k}b}^{2}={p}^{2k}{a'}+l{p}^{m}.$$Далее,
$$\pm 2{p}^{2k}\widetilde{x}b+{p}^{2k}{b}^{2}=\left(l-r\right){p}^{m}.$$Поскольку $$\widetilde{x}$$ не делится на $$p$$, то $${p}^{2k}b$$ делится на $${p}^{m}$$, и $$b$$ делится на $${p}^{m-2k}$$. Наоборот, если $$b$$ - кратное числа $${p}^{m-k}$$, и $${\widetilde{x}}^{2}={a'}+r{p}^{m'}$$, то $${\left(p\left(\pm \widetilde{x}+b\right)\right)}^{2}=a~(mod \ p^{m})$$. Тогда корнями исходного уравнения будут $$x={p}^{k}(\pm \widetilde{x}+{rp}^{m-2k})$$ и только они.
Теперь зная, как извлекать квадратный корень по примарному модулю, можно извлекать квадратный корень по произвольному модулю. Из китайской теоремы об остатках следует, что $${x}^{2}=a~(mod \ p_{1}^{{n}_{1}}{p}_{2}^{{n}_{2}}{\dots}{p}_{r}^{{n}_{r}})$$ тогда и только тогда, когда $${x}^{2}=a~(mod \ ~(p_{i}^{{n}_{i}}))$$ для всех $$i$$.
Пример 1.37 Найти квадратный корень из $$63$$ по модулю $$81$$.
Имеем: $${x}^{2}=63 \ mod \ 81$$. Делим обе части на 9. Тогда: $${\widetilde{x}}^{2}=7~(mod \ 9),x=3\widetilde{x}.$$
Для нахождения $$\widetilde{x}$$ используем вышеописанный алгоритм.
Отсюда $$\widetilde{x}=\pm 4,x=3 \cdot \left(\pm 4+9r\right)=12,15,39,42,66,69$$.
Пример 1.38 Найти квадратный корень из $$387$$ по модулю $$567$$.
Поскольку $$567=81 \cdot 7$$, имеем: $${x}^{2}=18 \ mod\ 81$$, $${x}^{2}=2 \ mod \ 7$$. Из этих уравнений находим $$x=12,15,39,42,66,69 \ mod\ 81$$ (из предыдущего примера) и $$x=\pm 3~(mod \ 7)$$. Из полученных двенадцати систем уравнений по китайской теореме об остатках имеем:
$$x=255,417,339,501,444,39,528,123,66,228,150,312.$$При необходимости более глубокого знакомства с материалом можно воспользоваться любым из университетских учебников алгебры и теории чисел. Кроме того, имеются пособия по криптографии, содержащие необходимый минимум теоретических сведений в указанных областях. В частности, отметим пособие [1], особенно полезными мы считаем главы 2 и 3 этой книги. Мы приводим краткие сведения из теории и примеры решения некоторых задач по теории чисел.
Будем считать известными свойства операций над целыми числами (сложения, вычитания, умножения), понятие модуля целого числа и свойства модуля.
Рассмотрим свойства отношения делимости во множестве целых чисел, это множество обозначается $$\mathbb{Z}$$.
Определение 1.1 Целое число $$a$$ делится на целое число $$b$$, если существует такое целое число $$c$$, что $$a=b\cdot c$$. Число $$a$$ называется делимым, $$b$$ - делителем, $$c$$ - частным.
Если число $$a$$ делится на $$b$$, то пишут $$a\, \vdots \,b$$ ($$a$$ кратно $$b$$).
Отношение делимости $$a\, \vdots \,b$$ в $$\mathbb{Z}$$ обладает следующими свойствами:
Если $$a \, \vdots \,c$$ и $$b \in \mathbb{Z}$$, то $$(ab)\, \vdots \,c$$.
Отметим, что утверждения, обратные 4 и 5, ложны: из делимости суммы не вытекает делимость слагаемых, а из делимости произведения не вытекает делимость сомножителей.Например, $$35+13=48$$ делится на 12, но ни 35, ни 13 не делятся на 12; $$3\cdot 8=24$$ делится на 12, но ни 3, ни 8 на 12 не делятся.
Определение 1.2 Разделить целое число $$a$$ на целое число $$b \neq 0$$ с остатком - это значит найти два таких целых числа $$q$$ и $$r$$, чтобы выполнялись условия:
Число $$q$$ называется неполным частным, а число $$r$$ - остатком от деления $$a$$ на $$b$$.
Заметим, что остаток - всегда есть число неотрицательное, а вот неполное частное может быть каким угодно целым числом. Поэтому на вопрос: "Сколько будет минус пять поделить на три с остатком?", правильный ответ: "Неполное частное минус два, остаток - один".
Теорема 1.1 Каковы бы ни были целое число a и целое число $$b \neq 0$$, всегда возможно, и притом единственным способом, разделить $$a$$ на $$b$$ с остатком.
Определение 1.3 Целое число $$\delta \neq 0$$ называется общим делителем целых чисел $$a_1, a_2, \dots, a_n$$, если каждое из этих чисел делится на $$\delta$$.
Определение 1.4 Целое число $$d$$ называется наибольшим общим делителем чисел $$a_1, a_2, \dots, a_n$$, если:
Теорема 1.2 Наибольший общий делитель чисел $$a_1, a_2, \dots, a_n$$ определён однозначно с точностью до знака (т.е. если $$d_1$$ и $$d_2$$ наибольшие общие делители чисел $$a_1, a_2, \dots, a_n$$, то либо $$d_1=d_2$$, либо $$d_1=-d_2$$).
Условимся всегда рассматривать положительное значение наибольшего общего делителя чисел $$a_1, a_2, \dots, a_n$$. Обозначение: $$d=НОД(a_1, \dots, a_n )$$.
Пример 1.1 $$НОД(135,-180)=45.$$
Действительно, множество положительных делителей числа $$135$$ есть $$A={1,3,5,9,15,27,45,135}$$, а для числа $$-180$$ такое множество имеет вид $$B={1,2,3,4,5,6,9,10,12,15,18,20,30,$ $36,45,60,90,180}$$. Пересечение этих множеств $$A \cap B = {1,3,5,9,15,45}$$. Число $$45$$ является общим делителем чисел $$135$$ и $$-180$$ и делится на все остальные общие делители этих чисел. Значит, $$НОД(135,-180)=45$$. Заметим, что $$45$$ - наибольший по величине положительный общий делитель чисел $$135$$ и $$-180$$.
Для любых целых чисел $$a_1, a_2, \dots, a_n$$ их наибольший общий делитель является наибольшим по величине положительным общим делителем.
Однако данное здесь определение является более удобным, так как распространяется на достаточно большой класс объектов, в частности, на многочлены. Определение же, включающее слова "наибольший по величине", не применимо к многочленам.
Опишем способ нахождения наибольшего общего делителя, предложенный древнегреческим математиком Евклидом. Алгоритм Евклида применяется при решении многих задач, как теоретических, так и прикладных.
Алгоритм Евклида состоит в следующем. Сначала $$a$$ делят на $$b$$ ($$a>b>0$$). Если $$a \, \vdots \, b$$, то $$НОД(a,b)=b$$. В противном случае $$a=b \cdot q_0 +r_1$$. Делим $$b$$ на $$r_1$$. Если $$b \, \vdots \, r_1$$, то $$НОД(b,r_1)=r_1$$, но тогда и $$НОД(a,b)=НОД(b,r_1)=r_1$$. Если $$b$$ не делится на $$r_1$$, то получится остаток $$r_2$$. Делим $$r_1$$ на $$r_2$$ и т.д.
Остатки, получаемые в процессе деления, убывают и являются натуральными числами, значит, на некотором шаге получим деление без остатка.
Последний не равный нулю остаток является наибольшим общим делителем чисел $$a$$ и $$b$$. Сформулируем это утверждение в виде теоремы.
Теорема 1.3 Если
| $$a=b\cdot q_0 + r_1$, $0 \leq r_1 < b,$$ |
| $$b=r_1 \cdot q_1 + r_2$, $0 \leq r_2 < r_1,$$ |
| $$r_1=r_2 \cdot q_2 + r_3$, $0 \leq r_3 < r_2,$$ |
| $$\dots$$ |
| $$r_{n-2}=r_{n-1} \cdot q_{n-1} + r_n$$, $$0 \leq r_n < r_{n-1},$$ |
| $$r_{n-1}=r_n \cdot q_n,$$ |
то $$НОД(a,b)=r_n$$
Пример 1.2 Найдём $$НОД(1547,560)$$
| $$1547 = 560 \cdot 2 + 427$$ |
| $$560 = 427 \cdot 1 + 133$$ |
| $$427 = 133 \cdot 3 + 28$$ |
| $$133 = 28 \cdot 4 + 21$$ |
| $$28 = 21 \cdot 1 + 7$$ |
| $$21 = 7 \cdot 3$$. |
| Отсюда $$НОД(1547, 560) = 7$$. |
Следствие 1.1 (Следствие из теоремы 1.3) Пусть $$d=НОД(a,b)$$, $$a>b>0$$, тогда существуют такие целые числа $$u$$ и $$v$$, что $$d=ua+bv$$. Другими словами, наибольший общий делитель двух чисел можно представить в виде линейной комбинации этих чисел с целыми коэффициентами.
Продолжение примера 1.2.
| $$7=28-1\cdot21=28-1\cdot(133-4\cdot28)=5\cdot28-1\cdot133=$$ |
| $$=5\cdot(427-133\cdot3)-1\cdot133=5\cdot427-16\cdot133=$$ |
| $$=5\cdot427-16\cdot(560-427\cdot1)=21\cdot427-16\cdot560=$$ |
| $$21\cdot(1547-2\cdot560)-16\cdot560=21\cdot1547-58\cdot560$$ |
Из алгоритма Евклида вытекает существование наибольшего общего делителя для любых двух целых чисел $$a$$ и $$b$$, кроме пары $$(0,0)$$, для которой НОД не существует.
Теорема 1.4 Если $$\delta = НОД(a_1, \dots, a_{n-1})$$ и $$d=НОД(\delta,a_n)$$, то $$d=НОД( a_1, a_2, \dots, a_n)$$.
Отметим еще одно свойство НОД. Если каждое из чисел $$a$$ и $$b$$ умножить на одно и то же число $$k \neq 0$$, то их наибольший общий делитель умножится на $$k$$.
Определение 1.5 Если $$НОД(a_1, a_2, \dots, a_n)=1$$, то числа $$a_1, a_2, \dots, a_n$$ называются взаимно простыми.
Например, числа 30 и 77 взаимно просты, а числа 30 и 72 не являются взаимно простыми, так как $$НОД(30,72)=6$$.
Теорема 1.5 Для того, чтобы числа $$a$$ и $$b$$ были взаимно простыми, необходимо и достаточно, чтобы существовали такие целые числа $$x$$ и $$y$$, что $$ax+by=1$$.
Следствие 1.2 Если числа $$a$$ и $$b$$ взаимно просты и $$a \, \vdots \,a_1$$, $$b \, \vdots \, b_1$$, то числа $$a_1$$ и $$b_1$$ взаимно просты.
И еще одно свойство: частные от деления чисел $$a$$ и $$b$$ на $$НОД(a,b)$$ взаимно просты.
Определение 1.6 Пусть $$a_1, a_2, \dots, a_n$$ - целые числа, отличные от нуля. Целое число $$M$$ называется общим кратным этих чисел, если оно делится на каждое из данных чисел.
Например, произведение $$a_1 \cdot a_2 \cdot \cdots \cdot a_n$$ - общее кратное всех своих сомножителей.
Определение 1.7 Целое число $$m$$ называется наименьшим общим кратным чисел $$a_1, a_2, \dots, a_n$$,если оно является их общим кратным и при этом любое общее кратное этих чисел делится на $$m$$.
Если наименьшее общее кратное существует, то оно определено с точностью до знака. Мы будем выбирать положительное значение наименьшего общего кратного и обозначать его так:
$$m=\LCM(a_1, a_2, \dots, a_n).$$Имеет место важная теорема.
Теорема 1.6 Число $$\dfrac{a\cdot b}{НОД(a,b)}$$, где $$НОД(a, b)$$ - наибольший общий делитель двух натуральных чисел $$a$$ и $$b$$, является наименьшим общим кратным этих чисел.
Рассмотрим основные свойства наименьшего общего кратного.
Пример 1.3 Найдем $$\LCM(5640, 2500)$$.
Разделим каждое из данных чисел на $$10$$ (очевидный делитель) и найдём $$\LCM(564, 250)$$. Имеем:
$$\LCM(564, 250)= \frac{564\cdot 250}{(564,250)}=\frac{564\cdot 250}{2}=564\cdot 125=70500.$$Тогда $$\LCM(5640, 2500)=70500\cdot10=705000$$.
Для нахождения НОК нескольких чисел имеет правило, аналогичное рассмотренному выше правилу нахождения НОД нескольких чисел.
Теорема 1.7 Если
$$\LCM(a_1, a_2)=m_1, \LCM(m_1, a_3)=m_2, \dots, \LCM(m_{n-2}, a_n) = m_{n-1},$$то $$\LCM(a_1, \dots, a_n) = m_{n-1}$$.
Иными словами, для нахождения НОК чисел $$a_1, \dots, a_n$$ надо сначала найти $$m_1=\LCM(a_1, a_2)$$, потом $$m_2=\LCM(m_1, a_3)$$, и т.д. вплоть до $$m_{n-1}=\LCM(m_{n-2}, a_n)$$. На каждом шаге нам придется находить НОК двух чисел, а это мы уже умеем делать.
Пример 1.4 Найдем $$\LCM(35, 77, 1141)$$.
$$\LCM(35, 77)= \dfrac{35\cdot 77}{НОД(35,77)}=\dfrac{35\cdot 77}{7}=35\cdot 11=385,$$ $$\LCM(385, 1141)= \dfrac{385\cdot 1141}{НОД(385,1141)}=\frac{385\cdot 1141}{7}=385\cdot 163=62755.$$Ответ. $$\LCM(35, 77, 1141)=62755$$.
Теорема 1.8 НОК попарно взаимно простых чисел равно их произведению.
Пример 1.5 Найдём $$\LCM(37, 43, 95)$$.
Имеем $$НОД(37, 43)=1$$, $$НОД(37, 95)=1$$, $$НОД(43, 95)=1$$. Следовательно, $$\LCM(37, 43, 95)=37\cdot43\cdot95=151145$$.
Определение 1.8 Натуральное число $$p$$ называется простым, если оно больше $$1$$ и не имеет положительных делителей, отличных от $$1$$ и $$p$$.
Определение 1.9 Натуральное число $$n$$ называется составным, если оно больше $$1$$ и имеет по крайней мере один положительный делитель, отличный от $$1$$ и $$n$$.
Согласно определению 1.2, если $$n$$ - составное, то существует такой делитель $$\delta$$, что $$n=n_1\delta$$, где $$1<n_1<n$$, $$1<\delta<n$$.
Число 1 не относят ни к простым, ни к составным числам.
Первыми простыми числами в натуральном ряду чисел являются 2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 37, 41...
Среди простых чисел имеется лишь одно четное число 2.
Итак, множество всех натуральных чисел разбивается на три подмножества: 1) простые числа, 2) составные числа, 3) число 1.
Теорема 1.9 (основная теорема арифметики) Всякое натуральное число $$n>1$$ либо просто, либо может быть представлено, и притом единственным образом (с точностью до перестановки множителей), в виде произведения простых чисел.
Отметим, что среди простых множителей числа могут встречаться одинаковые. Пусть, например, $$p_1$$ встречается $$\alpha_1$$ раз, $$p_2$$ встречается $$\alpha_2$$ раз, ..., $$p_k$$ встречается $$\alpha_k$$ раз; тогда разложение числа $$n$$ на простые множители можно записать следующим образом:
$$n={p}_{1}^{\alpha_1 }\cdot {p}_{2}^{\alpha_2 }\dots {p}_{k}^{\alpha_k }.$$Множители $$p_1, p_2,\dots, p_k$$ обычно располагают в порядке возрастания.
Определение 1.10 Представление натурального числа $$n$$ в форме 1.1 называется каноническим; это представление единственно, его называют также факторизацией числа $$n$$.
Пример 1.6 $$1176=2^{3}\cdot3\cdot7^{2}$; $136125=5^{3}\cdot11^{2}$$.
Из канонического представления числа вытекают следующие предложения.
Следствие 1.3 Если $$a=p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdots p_k^{\alpha_k}$$ - каноническое разложение числа $$a$$, то все делители этого числа имеют вид:
$$c=p_1^{\beta_1} \cdot p_2^{\beta_2} \cdots p_k^{\beta_k},$$где $$0\leq\beta_i\leq \alpha_i$$ $$(i=1, 2, {\ldots}, k)$$.
Пусть даны натуральные числа $$a$$ и $$b$$. Их каноническое разложение всегда можно записать в виде:
$$a=p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdots p_k^{\alpha_k}, \qquad b=p_1^{\gamma_1} \cdot p_2^{\gamma_2} \cdots p_k^{\gamma_k}.$$Мы предполагаем здесь, что $$\alpha_i$$ и $$\gamma_i$$ могут принимать и нулевые значения. Это позволит писать в обоих разложениях одни и те же простые числа $$p_1, p_2, \dots, p_s$$, а именно простые числа, которые входят в разложение хотя бы одного из чисел $$a$$ и $$b$$. Справедливы следующие утверждения.
Следствие 1.4 Наибольший общий делитель чисел $$a$$ и $$b$$ имеет вид:
$$НОД(a,b) = p_1^{\lambda_1}\cdot p_2^{\lambda_2}\cdots p_s^{\lambda_s},$$где $$\lambda_i=\min(\alpha_i,\gamma_i).$$
Следствие 1.5 Наименьшее общее кратное чисел $$a$$ и $$b$$ имеет вид:
$$\LCM(a,b)=p_1^{\mu_1}\cdot p_2^{\mu_2}\cdots p_s^{\mu_s},$$где $$\mu_i = \max(\alpha_i,\gamma_i)$$.
Из этих свойств непосредственно следует тождество $$(a, b) \cdot [a, b] =a \cdot b$$. Эти утверждения переносятся и на случай более чем двух чисел.
Теорема 1.10 (Евклида) Множество простых чисел бесконечно.
Поучительно сравнить эту теорему и следующую.
Теорема 1.11 (об интервалах) В натуральном ряде существуют сколько угодно длинные интервалы, не содержащие ни одного простого числа.
Сопоставление фактов, вытекающих из теоремы Евклида и теоремы об интервалах, свидетельствует о сложном характере распределения простых чисел в натуральном ряде. Вопрос этот является одним из труднейших в математике.
Рассмотрим некоторые функции, заданные на множестве натуральных чисел и связанные с арифметической природой этих чисел. Их называют числовыми функциями. Примерами таких функций могут служить:
Теорема 1.12 Если каноническая запись числа $$n$$ имеет вид:
$$n= {p}_{1}^{k_1} {p}_{2}^{k_2} {\dots} {p}_{m}^{k_m},$$то число натуральных делителей числа $$n$$ равно:
$$\tau(n)=(k_1+1)(k_2+1)\cdots (k_m+1).$$Пример 1.7 Поскольку $$60=2^{2}\cdot3\cdot5$$, то
$$\tau (60)=(2+1)(1+1)(1+1)=3\cdot2\cdot2=12.$$Делителями числа $$60$$ являются $$1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60$$. Их число действительно равно $$12$$. Приведём формулу для $$\sigma (n)$$.
Теорема 1.13 Если каноническая запись числа $$n$$ имеет вид $$n= {p}_{1}^{k_1} \dots {p}_{m}^{k_m}$$, то
$$\sigma (n)= \frac{{p}_{1}^{{k}_{1}+1}-1}{{p}_{1}-1}\cdot \frac{{p}_{2}^{{k}_{2}+1}-1}{{p}_{2}-1}{\dots}\frac{{p}_{m}^{{k}_{m}+1}-1}{{p}_{m}-1}.$$Пример 1.8 Найдём сумму натуральных делителей числа $$360$$.
Так как $$360=2^3\cdot3^2\cdot5$$, то
$$\sigma (360)= \frac{{2}^{4}-1}{2-1}\cdot \frac{{3}^{3}-1}{3-1}\cdot \frac{{5}^{2}-1}{5-1}=15\cdot 13\cdot 6=1170.$$Определение 1.11 Числа, дающие при делении на m одинаковые остатки, называются сравнимыми по модулю $$m$$. Обозначение: $$a \equiv b ~(mod \ m)$$.
Теорема 1.14 (признак сравнимости по модулю) Два целых числа сравнимы по модулю $$m$$ тогда и только тогда, когда их разность делится на $$m$$.
Итак, если два целых числа $$a$$ и $$b$$ сравнимы по модулю $$m$$, то этот факт можно записать разными способами: $$a \equiv b (mod \ m)$$ или $$a=b+mk$$, где $$k$$ - целое число, или $$a-b=mk$$ или $$(a-b)\, \vdots \,m$$.
Далее, если $$a=mq+r$$, то есть $$a$$ при делении на $$m$$ дает остаток $$r$$, то $$a-r=mq$$ или $$a \equiv r (mod \ m)$$. Таким образом, любое целое число $$a$$ всегда сравнимо с остатком $$r$$, получающимся при делении его на $$m$$.
Отношение сравнимости удовлетворяет условиям:
Отношение, заданное на множестве и обладающее перечисленными свойствами, задает разбиение этого множества на непересекающиеся классы. Применительно к отношению сравнимости по модулю $$m$$ это означает: все множество целых чисел разбивается на классы чисел, эти классы не пересекаются. Так, есть класс нуля: это все числа, сравнимые с нулем по модулю $$m$$,то есть делящиеся на $$m$$ без остатка(включая и само число 0), класс единицы - все числа, дающие остаток 1 при делении на $$m$$, класс 2, ...,класс $$m-1$$. Например, пусть $$m=5$$. Получаем следующие классы:
$$ \begin{array}{lcl} \bar{0}=\{\dots,-10, -5, 0, 5, 10, 15, 20,\dots\} \\[1ex] \bar{1}=\{\dots,-9, -4, 1, 6, 11, 16, 21,{\dots}\} \\[1ex] \bar{2}=\{\dots,-8, -3, 2, 7, 12, 17, 22,{\dots}\} \\[1ex] \bar{3}=\{{\dots},-7, -2, 3, 8, 13, 18, 23,{\dots}\} \\[1ex] \bar{4}=\{{\dots},-6, -1, 4, 9, 14, 19, 24,{\dots}\}. \end{array} $$Определение 1.12 Классы (1.2) называются классами вычетов.
Сравнения по одному и тому же модулю можно почленно складывать.
Два сравнения по одному и тому же модулю можно почленно вычитать одно из другого.
К обеим частям сравнения можно прибавлять одно и то же целое число.
Следствие 1.6 Члены сравнения можно переносить из одной части сравнения в другую с противоположным знаком.
Сравнения по одному и тому же модулю можно почленно перемножать.
Следствие 1.7 Обе части сравнения можно возводить в одну и ту же целую неотрицательную степень: если $$a \equiv b (mod \ m)$$ и $$k$$ - целое неотрицательное число, то $$a^k \equiv b^k (mod \ m)$$.
Если $$a \equiv b ~(mod \ m)$$ и $$m \, \vdots \, n$$, то $$a \equiv b ~(mod \ n)$$.
Обе части сравнения и модуль можно умножить на одно и то же целое положительное число.
Если $$ak \equiv bk \ mod \ m$$ и $$(k, m)=d$$, то $$a \equiv b \ mod \ {\frac{m}{d}}$$.
Приведем следствия из свойства 9.
Следствие 1.8 Если $$d=k$$, т. е. если $$m \, \vdots \, k$$, то из $$ak \equiv bk \ mod \ m$$ следует $$a \equiv b \ mod \frac{m}{k}$$, а это означает, что обе части сравнения и модуль можно разделить на любой их общий делитель.
Большое значение имеет
Следствие 1.9 Если $$d=1$$, т. е. если $$(k, m)=1$$, то из $$ak \equiv bk \ mod \ m$$ следует $$a \equiv b \ mod \ m$$, а это означает, что обе части сравнения можно разделить на их общий делитель, если он взаимно прост с модулем.
Пример 1.9 $$60 \equiv 9 (mod \ 17)$$.
После деления обеих частей сравнения на $$3$$ получим $$20 \equiv 3 ~(mod \ 17)$$.Делить обе части сравнения на число, не взаимно простое с модулем, вообще говоря, нельзя, так как после деления могут получиться числа, несравнимые по данному модулю.
Пример 1.10 $$8 \equiv 4~(mod \ 4)$$, но $$2 \not\equiv 1~(mod \ 4)$$.
Из рассмотренных свойств сравнений вытекает следующее общее свойство.
Пусть $$P(x)$$ - многочлен с целыми коэффициентами, $$a$$ и $$b$$ - переменные, принимающие целые значения. Тогда если $$a\equiv b ~(mod \ m)$$, то $$P(a) \equiv P(b) ~(mod \ m)$$.
Если $$a\equiv b~(mod \ m)$$ и $$c_i\equiv d_i ~(mod \ m)$$, то
$$c_na^n+c_{n-1}a^{n-1}+\ldots+c_1a + c_0 = d_nb^n + d_{n-1}b^{n-1}+\ldots+d_1b + d_0 ~(mod \ m).$$Таким образом, в сравнении по модулю $$m$$ отдельные слагаемые и множители можно заменять числами, сравнимыми по тому же модулю $$m$$. В частности, все числа, кратные модулю, можно заменять нулями (так как если $$a \, \vdots \, m$$, то $$a \equiv 0~(mod \ m)$$).
Вместе с тем следует обратить внимание на то, что встречающиеся в сравнениях показатели степеней заменять таким образом нельзя: из $$a^{n} \equiv c~(mod \ m)$$ и $$n \equiv k~(mod \ m)$$ не следует, что $$a^{k} \equiv c~(mod \ m)$$.Свойство 11 имеет ряд важных применений. В частности, с его помощью можно дать теоретическое обоснование признаков делимости.
Пример 1.11 Доказать, что при любом натуральном $$n$$ число $$37^{n+2} + 16^{n+1} +23^{n }$$ делится на $$7$$.
Решение. Очевидно, что $$37 \equiv 2~(mod \ 7)$$, $$16 \equiv 2~(mod \ 7)$$, $$23 \equiv 2~(mod \ 7)$$.
Возведем первое сравнение в степень $$n+2$$, второе - в степень $$n+1$$, третье - в степень $$n$$. Полученные сравнения: $$37^{n+2} \equiv 2^{n+2}~(mod \ 7)$$, $$16^{n+1} \equiv 2^{n+1}~(mod \ 7)$$, $$23^{n} \equiv 2^{n}~(mod \ 7)$$, сложим:
$$37^{n+2} +16^{n+1} +23^{n } \equiv 2^{n} \cdot (2^{2}+2^{1}+1) ~(mod \ 7) \equiv 2^{n}\cdot 7~(mod \ 7)$$, то есть $$37^{n+2} +16^{n+1} +23^{n}$$ делится на $$7$$.
Пример 1.12 Найти остаток от деления числа $$(9674^{6} +28)^{15}$$ на $$39$$.
Решение. Так как $$9674 \equiv 2~(mod \ 39)$$, то $$9674^{6} \equiv 2^{6}~(mod \ 39)=64 \equiv 25~(mod \ 39)$$. Далее, $$25+28=53 \equiv 14~(mod \ 39)$$. Следовательно, $$(9674^{6} +28)^{15}\equiv 14^{15}$$. И задача теперь сведена к следующей: найти остаток от деления $$14^{15}$$ на $$39$$. Воспользуемся сравнениями: $$14\equiv -1~(mod \ 3)$$ и $$14\equiv 1 ~(mod \13)$$. Из $$14\equiv -1~(mod \ 3)$$ следует: $$14^{14}\equiv 1~(mod \ 3)$$. А из сравнения $$14\equiv 1 ~(mod \13)$$ следует: $$14^{14}\equiv 1~(mod \ 13)$$. И так как сравнение имеет место по модулям $$3$$ и $$13$$, то оно имеет место и по модулю $$39$$, являющемуся НОК чисел $$3$$ и $$13$$. Итак, $$14^{14}\equiv 1~(mod \ 39)$$. Но в таком случае $$14^{15}\equiv 14~(mod \ 39)$$.
Пусть $$a,b,m\in \mathbb{N}$$, нам необходимо вычислить $$c = a^b ~(mod \ m)$$. В дальнейшем перед нами часто будет стоять такая задача с очень большими числами $$a$$, $$b$$, $$m$$. Очевиднейший способ вычислить $$c$$ - вычислить произведение $$\underbrace{a\cdot a\cdots a}_{n\ \text{раз}}$$ и взять остаток от деления на $$m$$. Для этого потребуется $$b$$ умножений и взятие остатка от деления огромного числа (не всегда даже его хранение в памяти может быть простым) по модулю $$m$$. Приведём оптимизации для этой задачи.
Из свойства
$$((a\cdot b)~(mod \ m) \cdot c)~(mod \ m) = (a\cdot b \cdot c)~(mod \ m)$$следует, что промежуточные результаты вычислений можно перед хранением брать по модулю $$m$$.
Сгруппируем сомножители в произведении особым образом. Пусть $$b=b_0 + 2b_1 + \ldots + 2^n b_n$$, $$b_i\in\{0,1\}$$. Имеем:
$$a^b ~(mod \ m) = a^{b_0} \cdot (a^2)^{b_1} \cdot (a^4)^{b_2} \cdots \left(a^{(2^n)}\right)^{b_n} ~(mod \ m).$$Используя пункт 1, будем все промежуточные результаты хранить по модулю $$m$$. Также для деления на 2 мы будем использовать операцию сдвига бит вправо:
$$2^n b_n + 2^{n-1} b_{n-1} + \ldots + 2 \cdot b_1 + b_0 ~~\rightarrow~~ 2^{n-1} b_{n} + \ldots + 2 \cdot b_2 + b_1.$$Микропроцессоры имеют специальные инструкции, а языки программирования - специальные операторы для оптимизированного выполнения битового сдвига, которые и следует использовать при реализации данного алгоритма.
Пункт 2 даёт следующий алгоритм возведения в степень по модулю.
Вход: $$a$$, $$b$$, $$m$$ - целые неотрицательные числа.
| 1) Положить $$r=1$$, $$b'=b$$, $$x=a$$. |
| 2) Повторять, пока $$b' > 0$$: |
| 2.1) Если $$b' \equiv 1 ~(mod \ 2)$$, положить $$r:=r\cdot x ~(mod \ m)$$. |
| 2.2) Положить $$x := x^2 ~(mod \ m)$$. |
| 2.3) Сдвинуть биты числа $$b'$$ на один вправо (что эквивалентно вычислению $$b' = \lfloor b'/2 \rfloor $$). |
Выход: $$r$$ - результат возведения $$a$$ в степень $$b$$ по модулю $$m$$.
Также отметим, что на шаге 1 копирование $$b'=b$$, $$x=a$$ выполняются для того, чтобы не испортить значения $$a$$, $$b$$, которые могут передаваться в наш алгоритм по указателю или ссылке.
Определение 1.13 Функция Эйлера $$\varphi(m)$$ - количество положительных чисел, не превосходящих $$m$$ и взаимно простых с $$m$$.
Пример 1.13 Пусть $$m=9$$. Взаимно простыми с $$9$$ являются числа: $$1$$, $$2$$, $$4$$, $$5$$, $$7$$, $$8$$. Так как количество этих чисел равно $$6$$, то $$\varphi(9)=6$$.
Пример 1.14 Пусть $$m=10$$. Взаимно простые с $$10$$ числа, меньшие $$10$$ - это $$1$$,$$3$$,$$7$$, $$9$$. Поэтому $$\varphi(10)=4$$.
Рассмотрим простое число $$p$$. Все числа, меньшие $$p$$, взаимно просты с ним. Итак, $$\varphi(p)=p-1$$ для простого $$p$$.
Для чисел 9, 10 можно было вычислить значение функции Эйлера непосредственным перечислением чисел, взаимно простых с данным числом. Для числа 100 сделать это уже труднее, а для 10000 еще труднее. Оказывается, есть формула, позволяющая вычислять значение функции Эйлера достаточно просто.
Пусть задано каноническое разложение числа $$m$$:
$$m= {p}_{1}^{{\alpha }_{1}}\cdot{\dots}\cdot {p}_{k}^{{\alpha }_{k}}$$.
Тогда $$\varphi(m)=m\cdot \left(1-\frac{1}{{p}_{1}}\right){\dots}\left(1-\frac{1}{{p}_{k}}\right)$$.
Теорема 1.15 (Эйлер) Если a - такое число, что $$(a, m)=1$$, то $${a}^{\varphi (m)}\equiv 1~(mod \ m)$$.
Пример 1.16 Пусть $$a=2$$, $$m=9$$. Тогда $$\varphi(m)=6$$, и по теореме Эйлера получаем: $${2}^{6}\equiv 1~(mod \ 9)$$. В справедливости этого равенства легко убедиться, если учесть, что $${2}^{6}=64$$.
Пример 1.17 Пусть $$a=17$$, $$m=32$$. Тогда $$\varphi(32)=16$$, то по теореме Эйлера получаем: $${17}^{16}\equiv 1~(mod 32)$$. Убедиться в справедливости этого равенства непосредственным подсчётом было бы затруднительно.
Особенно простой вид теорема Эйлера принимает, если $$m=p$$ - простое число. В этом случае $$\varphi(p)=p-1$$, а потому получаем следующее утверждение:
Теорема 1.16 (малая теорема Ферма) Если $$p$$ - простое число и $$a$$ - целое число, такое, что $$(a, p)=1$$, то $${a}^{p-1}\equiv 1~(mod \ p)$$.
Часто используется следствие малой теоремы Ферма, если $$p$$ - простое число, то для любого целого числа a имеет место сравнение: $${a}^{p} \equiv a~(mod \ p)$$.
Рассмотрим примеры на применение теорем Эйлера и Ферма.
Пример 1.18 Найдём остаток отделения $${3}^{28}$$ на $$7$$.
Согласно теореме Ферма $${3}^{6}\equiv 1~(mod \ 7)$$, тогда $${3}^{24}\equiv 1~(mod \ 7)$$. Кроме того, $${3}^{4}\equiv 81\equiv 4~(mod \ 7)$$. Тогда $${3}^{28}\equiv {3}^{24\cdot }{3}^{4} ~(mod \ 7)\equiv 4$$. Следовательно, искомый остаток $$r=4$$.
Пример 1.19 Найдём остаток от деления $${243}^{132}$$ на $$34$$.
Имеем: $$243\equiv 5~(mod \ 34)$$. Тогда $${243}^{132}\equiv {5}^{132}~(mod \ 34)$$. Согласно теореме Эйлера $${5}^{\varphi (34)}\equiv 1~(mod \ 34)$$, или $${5}^{16}\equiv 1~(mod \ 34)$$. Далее делим $$132$$ на $$16$$, получим: $$132=16\cdot8+4$$. Поэтому $${5}^{132}={\left({5}^{16}\right)}^{8}\cdot {5}^{4}\equiv {5}^{4}\equiv 625\equiv 13$$. Таким образом, $${243}^{132}\equiv 13~(mod \ 34)$$.
Следовательно, $$r=13$$.
Пример 1.20 Найдем остаток от деления числа $$a=2^{18}+3^{18}+4^{18}+5^{18}+6^{18}+2$$ на $$7$$.
Решение. Числа $$1,2,3,4,5,6$$ взаимно просты с числом 7. По теореме Ферма, $$1^{6}\equiv 1~(mod 7)$$, $$2^{6}\equiv 1~(mod \ 7)$$, $$3^{6}\equiv 1~(mod \ 7)$$, $$4^{6}\equiv 1~(mod \ 7)$$, $$5^{6}\equiv 1~(mod \ 7)$$, $$6^{6}\equiv 1~(mod \ 7)$$. Возведем эти сравнения в третью степень и сложим, получим: $$1^{18}+2^{18}+3^{18}+4^{18}+5^{18}+6^{18}\equiv 6~(mod \ 7)\equiv -1~(mod \ 7)$$. Следовательно, $$1+1^{18}+2^{18}+3^{18}+4^{18}+5^{18}+6^{18}\equiv 0$$, то есть число $$a$$ делится на 7 без остатка.
Пример 1.21 Найти остаток от деления $$7^{402}$$ на $$101$$.
Решение. Число 101 простое, $$(7,101)=1$$, $$\varphi(101)=100$$. По теореме Ферма, $$7^{100}\equiv 1~(mod \ 101)$$. Возведем это сравнение в четвертую степень, получим: $$7^{400}\equiv 1~(mod \ 101)$$. Умножим полученное сравнение на сравнение $$7^{2}\equiv 49~(mod \101)$$. Итак, $$7^{402}\equiv 49~(mod \101)$$, то есть остаток равен 49.
Пример 1.22 Доказать, что $$73^{12}-1$$ делится на $$105$$.
Решение. Разложим на множители: $$105=3\cdot5\cdot7$$. Далее, $$(73,3)=(73,5)=(73,7)=1$$. По теореме Ферма, $$73^{2}\equiv 1~(mod \ 3)$$, $$73^{4}\equiv 1~(mod \ 5)$$, $$73^{6}\equiv 1~(mod \ 7)$$. Возведем первое сравнение в шестую степень, второе в третью степень, третье во вторую, получим: $$73^{12}\equiv 1~(mod \ 3)$$, $$73^{12}\equiv 1~(mod \ 5)$$, $$73^{12}\equiv 1~(mod \ 7)$$. А отсюда следует, что $$73^{12}\equiv 1~(mod \ 105)$$, так как 105- наименьшее общее кратное чисел 3, 5, 7.
Определение 1.14 Число $$b$$ называется обратным к $$a$$ по модулю $$m$$, если $$a\cdot b\equiv 1(mod \ m)$$. Пишут: $$b= a^{-1} ~(mod \ m)$$.
Например, 3 обратно к 2 по модулю 5, так как $$2\cdot3\equiv 1~(mod \ 5)$$. Заметим, что обратное к $$a$$ по модулю $$m$$ можно найти лишь в случае $$(a,m)=1$$. Если $$(a,m)=d>1$$, то обратный к $$a$$ по модулю $$m$$ не существует. Например, обратного к 2 по модулю 10 не существует: при умножении любого числа $$b$$ на 2 мы не получим 1 по модулю 10. Если модуль сравнения $$m$$- простое число, то обратный элемент есть для каждого числа.
Пример 1.23 Найдем число, обратное к $$26$$ по модулю $$49$$.
Числа 26 и 49 взаимно просты, поэтому искомое число существует. Реализуем расширенный алгоритм Евклида для чисел 26 и 49.
| Имеем: $$49=1 \cdot 26+23$$, |
| $$26=1 \cdot 23+3$$, |
| $$23=7 \cdot 3+2$$, |
| $$3=1 \cdot 2+1$$. |
И теперь $$1=3 - 1 \cdot 2=3-1 \cdot (23-7 \cdot 3)=%-1 \cdot 23+8 \cdot 3=-1 \cdot 23+8 \cdot (26-1 \cdot 23)=%8 \cdot 26-9 \cdot 23=8 \cdot 26-9 \cdot (49-1 \cdot 26)=%-9 \cdot 49+17 \cdot 26$$. Итак, $$49 \cdot (-9)+17 \cdot 26=1$$. То есть $$26 \cdot 17\equiv 1~(mod \ 49)$$. Таким образом, число 17 является обратным к 26 по модулю 49.
Сравнение с одним неизвестным $$x$$ имеет вид
$${a}_{n}{x}^{n}+{a}_{n-1}{x}^{n-1}+{\dots}+{a}_{1}x+{a}_{0} \equiv 0~(mod \ m),$$где $$m \in \mathbb{N}$$, $$m>1$$. Если $${a}_{n}$$ не делится на $$m$$, то $$n$$ называется степенью сравнения (1.3).
Определение 1.15 Решением сравнения (1.3) называется всякое целое число $${x}_{0}$$, для которого $${a}_{n}{x}_{0}^{n}+{a}_{n-1}{x}_{0}^{n-1}+{\dots}+{a}_{0} \equiv 0 ~(mod \ m)$$.
Если $${x}_{0}$$ удовлетворяет сравнению (1.3), то, согласно свойству 11 сравнений, этому сравнению будут удовлетворять все целые числа, сравнимые с $${x}_{0}$$ по модулю $$m$$. Поэтому все числа, сравнимые по модулю $$m$$ с $${x}_{0}$$, будем рассматривать как одно решение. Другими словами, решениями сравнения (1.3) будут классы чисел. Например, $$\bar{1}$$ - это класс единицы, то есть все числа, сравнимые с 1, $$\bar{2}$$ - класс числа 2, то есть все числа, сравнимые с 2, т.д. И фразу "данное сравнение имеет 2 решения" надо понимать так: данному сравнению удовлетворяют два класса чисел. Как отмечалось выше, эти классы не имеют общих элементов. В дальнейшем мы записываем какое-либо число - представитель класса без черты сверху, называя это число решением.
Сравнения, множества решений которых совпадают, называются равносильными.
Любое сравнение первой степени с одним неизвестным $$x$$ можно привести к виду
$$ax \equiv b~(mod \ m),$$где $$a \not\equiv 0 ~(mod \ m)$$.
Выясним условия, при которых сравнение (1.4) имеет:
Теорема 1.17 Для того, чтобы сравнение (1.4) имело хотя бы одно решение, необходимо и достаточно, чтобы число $$b$$ делилось на $$НОД(a,m)$$.
Пример 1.24 Сравнение $$9x\equiv 6~(mod \12)$$ имеет решение, так как $$6$$ делится на $$3=НОД(9,12)$$.
Пример 1.25 Сравнение $$6x\equiv 9 ~(mod \12)$$ не имеет решений, так как $$НОД(6,12)=6$$, а $$9$$ не делится на $$6$$.
Теорема 1.18 Пусть сравнение (1.4) разрешимо и $$d=НОД(a,m)$$. Тогда множество решений сравнения (1.4) состоит из $$d$$ классов по модулю $$m$$, а именно, если $${x}_{0}$$ - одно из решений, то все другие решения - это $${x}_{0}+m_1, {x}_{0}+2m_1,{\dots}, {x}_{0}+(d-1)m_1$$, где $$m_1= \frac{m}{d}$$.
Пример 1.26 Сравнение $$9x\equiv 6~(mod \ 12)$$ имеет ровно три решения, так как $$НОД(9,12)=3$$. Эти решения: $${x}_{0}=2$$, $${x}_{0}+4=6$$, $${x}_{0}+2 \cdot 4=10$$.
Пример 1.27 Сравнение $$11x\equiv 2~(mod \ 15)$$ имеет единственное решение $${x}_{0}=7$$, т.к. $$НОД(11,15)=1$$.
Покажем, как решать сравнение первой степени. Рассмотрим случай $$НОД(a,m)=1$$. Тогда решение сравнения (1.4) можно искать, например, по алгоритму Евклида. Действительно, используя расширенный алгоритм Евклида, представим число 1 в виде линейной комбинации чисел $$a$$ и $$m$$: $$1=aq+mr$$.
Умножим обе части этого равенства на $$b$$, получим: $$b=abq+mrb$$, откуда $$abq-b=-mrb$$, то есть $$a \cdot (bq) \equiv b~(mod \ m)$$ и $$bq$$ - решение сравнения (1.4).
Другой способ: использовать теорему Эйлера. Пусть, снова, $$НОД(a,m)=1$$. Применяем теорему Эйлера: $${a}^{\varphi (m)}\equiv 1~(mod \ m)$$. Умножим обе части сравнения на $$b$$: $${a}^{\varphi (m)}b \equiv b~(mod \ m)$$. Переписывая последнее выражение в виде $$a( {a}^{\varphi (m)-1}b) \equiv b~(mod \ m)$$, получаем, что $${a}^{\varphi (m)-1}b$$ - решение сравнения (1.4).
Допустим теперь, что $$НОД(a,m)=d>1$$. Тогда $$a=a_1 d$$, $$m=m_1 d$$, где $$НОД(a_1,m_1)=1$$. Кроме того, необходимо $$b=b_1 d$$ для того, чтобы сравнение было разрешимо. Если $${x}_{0}$$ - решение сравнения $$a_1 x\equiv b_1 ~(mod \ m_1)$$, причем единственное, поскольку $$НОД(a_1,m_1)=1$$, то $${x}_{0}$$ будет решением и сравнения $$a_1 dx\equiv b_1 d ~(mod \ m_1) d$$, то есть исходного сравнения (1.4). Остальные решения (их $$d-1$$) находим по теореме.
Итак, если $$НОД(a,m)=1$$, то сравнение (1.4) имеет единственное решение, и решением сравнения является класс $$x=ba^{\varphi(m)-1}~(mod \ m)$$. Если $$НОД(a,m)=d>1$$, $$b$$ не делится на $$d$$, то сравнение решений не имеет. Если $$b$$ делится на $$d$$, то сравнение имеет $$d$$ различных решений. Все эти решения образуют один класс по модулю $$\frac{m}{d}$$.
Пример 1.28 Решим сравнение: $$12x\equiv 9~(mod \ 21)$$$.
Вычисляем $$НОД(12,21)=3$$. Число 9 делится на 3, поэтому сравнение разрешимо, и у него три решения. Поделим обе части сравнения и модуль на их наибольший общий делитель: $$4x\equiv 3 ~(mod \ 7)$$. Поскольку $$НОД(4, 7)=1$$, можем воспользоваться теоремой Эйлера: $${x}_{0}={4}^{\varphi \left(7\right)-1} \cdot 3 \equiv {4}^{5} \cdot 3 \equiv 6 ~(mod \ 7)$$.
Поясним:$$\varphi(7)=6$$, $$4^{2}=16\equiv 2~(mod \ 7)$$, поэтому $${4}^{5}\equiv 4^{2} \cdot 4^{2} \cdot 4\equiv 2 \cdot 2 \cdot 4\equiv 2$$, и $$2 \cdot 3\equiv 6$$.
Таким образом, 6 - это одно из решений сравнения $$12x\equiv 9 ~(mod \ 21)$$. Находим остальные решения:
$$6+ \frac{21}{3} =6+7=13, 6+2 \cdot \frac{21}{3} =6+14=20.$$Проверка: $$12 \cdot 6-9=63=21 \cdot 3$$; $$12 \cdot 13-9=147=21 \cdot 7$$; $$12 \cdot 20-9=231=21 \cdot 11$$.
Пример 1.29 $$45 x \equiv 31~(mod \ 100)$$.
Так как $$НОД(45,100)=5$$, а 31 не делится на 5, то решений сравнение $$45 x \equiv 31~(mod \ 100)$$ не имеет.
Пример 1.30 $$51 x \equiv 141~(mod \ 234)$$.
Поскольку $$НОД(51,234)=3$$, $$141 \, \vdots \, 3$$, то сравнение имеет 3 решения. После деления обеих частей и модуля на 3 получим сравнение: $$17 x \equiv 47~(mod \ 78)$$. Решение этого сравнения: $$x \equiv 67~(mod \ 78)$$.
Решения исходного сравнения найдём по теореме 1.18: $$x \equiv 67~(mod \ 234)$$, $$x \equiv 67+78 \equiv 145~(mod \ 234)$$, $$x \equiv 67+2\cdot 78 \equiv 223~(mod \ 234)$$.
Пусть $$t=\dfrac{a}{b}$$, $$b>0$$, $$a$$, $$b$$ - целые. Число $$t$$ можно представить в виде дроби особого вида. Это представление получается из алгоритма Евклида. Применим алгоритм Евклида к числам $$a$$ и $$b$$. Получим:
$$ \begin{array}{lll} a=b\cdot q_0+r_1, \vphantom{\rule{0em}{2 em}} \hphantom{\rule{4em}{1em}} \dfrac{a}{b}=q_0+\dfrac{r_1}{b},\\ b=r_1\cdot q_1+r_2, \vphantom{\rule{0em}{2 em}} \hphantom{\rule{4em}{1em}} \dfrac{b}{r_1}=q_1+\dfrac{r_2}{r_1},\\ r_1=r_2\cdot q_2+r_3,\vphantom{\rule{0em}{2 em}} \hphantom{\rule{4em}{1em}} \dfrac{r_1}{r_2}=q_2+\dfrac{r_3}{r_2},\\ \cdots \vphantom{\rule{0em}{2 em}} \hphantom{\rule{4em}{1em}} \cdots \\ r_{n-2}=r_{n-1}\cdot q_{n-1}+r_n, \vphantom{\rule{0em}{2em}} \hphantom{\rule{4em}{1em}} \dfrac{r_{n-2}}{r_{n-1}}=q_{n-1}+\dfrac{r_n}{r_{n-1}},\\ r_{n-1}=r_n\cdot q_n,\vphantom{\rule{0em}{2 em}} \hphantom{\rule{4em}{1em}} \dfrac{r_{n-1}}{r_n}=q_n \end{array} $$Из второго равенства получаем:
$$\dfrac{r_1}{b}=\dfrac{1}{q_1+\dfrac{r_2}{r_1}}.$$Подставим это выражение в первое из равенств (1.5), получим:
$$\frac{a}{b}=q_0+\dfrac{1}{q_1+\dfrac{r_2}{r_1}}.$$Третье из равенств (1.5) даёт:
$$\frac{r_2}{r_1}=\dfrac{1}{q_2+\dfrac{r_3}{r_2}}.$$Подставим это выражение в (1.7), получим:
$$\frac{a}{b}=q_0+\dfrac{1}{q_1+\dfrac{1}{q_2+\dfrac{r_3}{r_2}}}.$$Продолжая действовать аналогично, за конечное число шагов получим:
$$\frac{a}{b}=q_0+\dfrac{1}{q_1+\dfrac{1}{q_2+\dfrac{1}{q_3+\dots+\dfrac{1}{q_n}}}}.$$Определение 1.16 Дробь вида (1.8) называется конечной цепной (другое название: непрерывной) дробью.
Сокращенная (и, конечно, более удобная) запись: $$[q_0; q_1,q_2,q_3,\dots,q_n]$$.
Числа $$q_0 \, \vdots \, q_1,q_2,q_3,\dots,q_n$$ называются неполными частными, все они - целые, а начиная с $$q_1$$ - натуральные.
Равенство вида (1.8) называется представлением рационального числа конечной цепной дробью.
Теорема 1.19 Всякое рациональное число может быть представлено в виде конечной цепной дроби.
Пример 1.31
Если допустить, что последнее неполное частное может равняться 1, то для всякого рационального числа можно получить два представления в виде конечной цепной дроби.
Пример 1.32 $$2+\dfrac{1}{5+\dfrac{1}{3}}=2+\dfrac{1}{5+\dfrac{1}{2+\dfrac{1}{1}}}$$
Теорема 1.20 Представление рационального числа в виде конечной цепной дроби, такой, что последнее неполное частное отлично от $$1$$, единственно.
Имеет место простая, но важная
Теорема 1.21 Всякая конечная цепная дробь есть рациональное число.
Определение 1.17 Дроби $$\delta_0 = \dfrac{{P}_{0}}{{Q}_{0}}= \dfrac{{q}_{0}}{1}$$, $$\delta_1 = \dfrac{{P}_{1}}{{Q}_{1}}= {q}_{0}+ \dfrac{1}{{q}_{1}}$$, $$\delta_2 = \dfrac{{P}_{2}}{{Q}_{2}}=q_0+\dfrac{1}{q_1+\dfrac{1}{q_2}}$$ и т.д. называются подходящими дробями цепной дроби (1.8) или соответствующего ей числа $$\dfrac{a}{b}$$.
Очевидно, что последняя подходящая дробь $$\delta_n = \dfrac{{P}_{n}}{{Q}_{n}}$$ есть число $$\dfrac{a}{b}$$. Каждая подходящая дробь есть некоторое рациональное число. Заметим, что $$s$$-я подходящая дробь $$\delta_s$$ получается заменой $${q}_{s-1}$$ на $${q}_{s-1}+\frac{1}{{q}_{s}}$$.
Подходящие дроби последовательно можно представить в виде:
$$\delta_0 = \frac{{q}_{0}}{1}=\frac{{P}_{0}}{{Q}_{0}}, \quad \delta_1 = {q}_{0}+ \frac{1}{{q}_{1}}= \frac{{P}_{1}}{{Q}_{1}}$$ $${\delta }_{2}={q}_{0}+\dfrac{1}{{q}_{1}+\dfrac{1}{{q}_{2}}}={q}_{0}+\dfrac{{q}_{2}}{{q}_{1}{q}_{2}+1}=\dfrac{{q}_{0}{q}_{1}{q}_{2}+{q}_{0}+{q}_{2}}{{q}_{1}{q}_{2}+1}=\dfrac{\left({q}_{0}{q}_{1}+1\right){q}_{2}+{q}_{0}}{{q}_{1}{q}_{2}+1}=\\\dfrac{{P}_{1}{q}_{2}+{P}_{0}}{{Q}_{1}{q}_{2}+{Q}_{0}}=\dfrac{{P}_{1}}{{Q}_{2}}.$$Общая формула имеет вид:
$${\delta }_{s}=\frac{{P}_{s}}{{Q}_{s}}=\frac{{P}_{s-1}{q}_{s}+{P}_{s-2}}{{Q}_{s-1}{q}_{s}+{Q}_{s-2}}.$$Напомним кратко основные свойства цепных дробей.
Одно уравнение с несколькими неизвестными имеет, как правило, бесконечное множество решений. Поэтому такие уравнения называют неопределенными. В теории чисел рассматривают задачу отыскания целочисленных решений неопределенных уравнений (их еще называют диофантовыми по имени древнегреческого математика Диофанта). Связь сравнений и диофантовых уравнений дается следующей теоремой.
Теорема 1.22 Если $$({x}_{0}, {y}_{0})$$ - целочисленное решение неопределенного уравнения $$ax+by=c$$, где $$a$$, $$b$$, $$c$$ - целые числа, $$a \neq 0$, $b \neq 0$$, то $$x_0$$ - решение сравнения $$ax_0=c ~(mod \ b)$$.
Обратно, если $$x_0$$ - решение сравнения $$ax=c ~(mod \ b)$$, то существует такое целое число $$y_0$$, что $$(x_0, y_0)$$ - решение неопределенного уравнения $$ax+by=c$$.
Эта теорема позволяет свести решение неопределенных уравнений вида $$$ax+by=c$$ к решению сравнений первой степени, и обратно. В частности, из приведенных выше утверждений о сравнениях первой степени легко получается
Теорема 1.23 Если $$НОД(a,b)=d$$, то неопределенное уравнение $$ax+by=c$$ имеет целочисленное решение в том и только в том случае, когда $$c$$ делится на $$d$$.
В частности, если $$НОД(a,b)=1$$, то урвнение $$ax+by=c$$ при любом целом c имеет целочисленное решение.
Процесс нахождения целочисленных решений уравнений вида $$ax+by=c$$ состоит из даух этапов: нахождение хотя бы одного такого решения и нахождение общего вида таких решений. Рассмотрим сначала второй этап.
Теорема 1.24 Если известно частное целочисленное решение $$({x}_{0}, {y}_{0})$$ неопределенного уравнения $$ax+by=c$$ и $$НОД(a,b)=d$$, то общее решение этого уравнения имеет вид $$x= {x}_{0}-\dfrac{b}{d}t$$, $$y= {y}_{0}+\dfrac{a}{d}t$$, где $$t$$ пробегает множество целых чисел.
Для нахождения частных решений применяют те же способы, что и для решения сравнений (например, можно использовать теорему Эйлера). Покажем, как искать решения неопределенных уравнений (а тем самым и сравнений) с помощью цепных дробей.
Из предыдущего следует, что общее решение уравнения имеет вид:
$$x= {(-1)}^{n-1} c {Q}_{n-1}-bt, y= {(-1)}^{n} c {P}_{n-1}+at,$$где $${P}_{n-1}$ и ${Q}_{n-1}$$ - числитель и знаменатель предпоследней подходящей дроби разложения $$\frac{a}{b}$$ в цепную дробь, а $$t$$ - любое целое число.
Пример 1.33 Решим в целых числах уравнение $$142x+82y=6$$.
Решение. Так как $$НОД(142,82)=2$$ и $$6\, \vdots \,2$$, то уравнение имеет решение. Данное уравнение равносильно уравнению $$71x+41y=3$$.
Разложим $$\dfrac{71}{41}$$ в цепную дробь : $$\dfrac{71}{41}=[1; 1,2,1,2,1,2]$$.
Составим все подходящие дроби:
$$\frac{{P}_{0}}{{Q}_{0}}= \frac{1}{1},~~ \frac{{P}_{1}}{{Q}_{1}}=\frac{2}{1},~~\frac{{P}_{2}}{{Q}_{2}}= \frac{5}{3},~~ \frac{{P}_{3}}{{Q}_{3}}=\frac{7}{4},~~\frac{{P}_{4}}{{Q}_{4}}=\frac{19}{11},~~ \frac{{P}_{5}}{{Q}_{5}}=\frac{26}{15},~~\frac{{P}_{6}}{{Q}_{6}}=\frac{71}{41}.$$На основании свойства подходящих дробей $${P}_{k-1}{Q}_{k}- {P}_{k}{Q}_{k-1}= {(-1)}^{k}$$ Получим: $$26\cdot41-71\cdot15= {(-1)}^{6}$$, или $$71\cdot(-15)+41\cdot26=1$$.
Умножив обе части равенства на 3, находим: $$71\cdot(-45)+41\cdot78=3$$, т.е. $${x}_{0}=-45$$, $${y}_{0}=78$$ - частное решение данного уравнения.
Все решения могут быть найдены по формулам: $$x=-45+41t$$, $$y=78-71t$$, или $$x=-4+41t$$, $$y=7-71t$$, где $$t$$ принимает любые целые значения.
Рассмотрим систему сравнений первой степени:
$$x\equiv {a}_{1} (mod \ {m}_{1}), x\equiv {a}_{2} (mod \ {m}_{2}), {\dots}, x\equiv {a}_{r} (mod \ {m}_{r}),$$где числа $${m}_{1},{m}_{2},...,{m}_{r}$$ попарно взаимно простые, и найдём значение $${x}_{0} \in \mathbb{Z}$$, удовлетворяющее всем $$r$$ сравнениям.
Теорема 1.25 (китайская теорема об остатках) Пусть $${m}_{1},{m}_{2},...,{m}_{r}$$ - попарно взаимно простые, и числа $${a}_{1},{a}_{2},...,{a}_{r}$$ - произвольные целые. Тогда существует единственное такое целое число $${x}_{0}$$, что $$0 \leq x_{0} < {m}_{1} \cdot {m}_{2} \cdot \dots \cdot {m}_{r}$$ и $${x}_{0}\equiv{a}_{1}~(mod \ {m}_{1})$$, $${x}_{0}\equiv {a}_{2}~(mod \ {m}_{2}), {\dots}, {x}_{0}\equiv {a}_{r}~(mod \ {m}_{r})$$.
$${x}_{0}\equiv \sum _{i=1}^{r}{{a}_{1}}{M}_{i}{N}_{i}~(mod \ m_1) \cdot {m}_{2} \cdot ... \cdot {m}_{r},$$где $${M}_{i}={m}_{1} \cdot {\dots}{ \cdot m}_{i-1} \cdot {m}_{i+1} \cdot {\dots}{ \cdot m}_{r}$$ и $${N}_{i}{ \equiv M}_{i}^{-1}~(mod \ m_i)$$.
Пример 1.34 Решим систему сравнений $$x\equiv 2 ~(mod \ 5)$$, $$x\equiv 3 ~(mod \ 6)$$, $$x\equiv 4 ~(mod \ 7)$$.
Вычисляем: $${M}_{1}=6 \cdot 7=42$$, $${M}_{2}=5 \cdot 7=35$$, $${M}_{3}=5 \cdot 6=30$$. Находим обратные числа:
$${N}_{1} \equiv {42}^{-1} \equiv {2}^{-1} \equiv 3mod5; $$ $${N}_{2} \equiv {35}^{-1} \equiv {5}^{-1} \equiv 5mod6; $$ $${N}_{3} \equiv {30}^{-1} \equiv {2}^{-1} \equiv 4mod7.$$Подставляем значения в формулу (1.10):
$${x}_{0}\equiv 2 \cdot 42 \cdot 3+3 \cdot 35 \cdot 5+4 \cdot 30 \cdot 4=252+525+480=1257\equiv 207 ~(mod \ 210).$$Проверка: $$207-2=205=5 \cdot 41$$, то есть $$207\equiv 2 ~(mod \ 5)$$; $$207-3=204=6 \cdot 34$$, то есть $$207\equiv 3 ~(mod \ 6)$$; $$207-4=203=7 \cdot 29$$, то есть $$207\equiv 4 ~(mod \ 7)$$.
Теорема 1.26 Система сравнений $$x={a}_{i} ~(mod \ n_i),i=1,{\dots},k$$, имеет решение $$x_0$$ тогда и только тогда, когда $${a}_{i}={a}_{j}~(mod НОД(n_i,n_j))$$, причем такое $$x_0$$ с условием $$0\leq x_0<\LCM({n}_{1},{\dots},{n}_{k})$$ - единственное.
Для решения системы найдём $$N=\LCM\left({n}_{1},{\dots},{n}_{k}\right)={p}_{1}^{{j}_{1}}{p}_{2}^{{j}_{2}}{\dots}{p}_{r}^{{j}_{r}}$$, где $${p}_{i}$$ - попарно различные простые числа. Для каждого делителя $${p}_{i}^{{j}_{i}}$$ найдём номер $${l}_{i}$$ такой, что $${n}_{{l}_{i}}$$ делится на него, и число $${b}_{i}={a}_{{l}_{i}}~(mod p_{i}^{{j}_{i}})$$. Полученная система $$x={b}_{i}~(mod p_{i}^{{j}_{i}})$$ будет иметь взаимно простые модули, и единственное её решение $$x_0$$ с условием $$0\leq x_0<\LCM({n}_{1},{\dots},{n}_{k})$$ даёт Китайская теорема об остатках.
Пример 1.35 Решим систему уравнений: $$x=12mod14$$, $$x=4mod18$$, $$x=4mod12$$.
Решение. Нетрудно убедиться, что наша система удовлетворяет условию теоремы. Решим её. Найдём $$\LCM\left(14,18,12\right)=4 \cdot 9 \cdot 7=252.$$ На 4, 7 и 9 делятся, соответственно, 12, 14 и 18. Следовательно, исходная система эквивалентна системе: $$x=0mod4$$, $$x=4mod9$$ и $$x=5mod7$$. Решение $$x=40mod252$$ последней системы находим по китайской теореме об остатках.
Определение. Число $$a$$ называется квадратичным вычетом по модулю $$m$$, если сравнение $$x^2 \equiv a (mod \ m)$$ имеет решение при некотором целом $$x$$, если сравнение $$x^2 \equiv a (mod \ m)$$ не имеет решений, то $$a$$ называют квадратичным невычетом.
Определение. Символ Лежандра определяется следующим образом:
$$\left(\frac{a}{p}\right)=\left\{\begin{array}{rl}0, \text{если $a$ делится на $p$};\\1, \text{если $a$ - квадратичный вычет}~(mod \ p);\\-1, \text{если $a$ - квадратичный невычет}~(mod \ p).\end{array}\right$$Следующие свойства используются для вычисления символа Лежандра:
Пример 1.36 Найти случайный квадратичный невычет по модулю $$449$$.
Решение. Будем выбирать числа случайно, и тестировать их с помощью символа Лежандра.
Пусть выбранное нами случайное число оказалось 51:
$$\left(\frac{51}{449}\right)=\left[\text{по свойству 3}\right]=\left(\frac{3}{449}\right)\left(\frac{17}{449}\right)=\left[\text{по свойству 5}\right]=\\{\left(-1\right)}^{\frac{448 \cdot 2}{4}}\left(\frac{449}{3}\right){\left(-1\right)}^{\frac{448 \cdot 16}{4}}\left(\frac{449}{17}\right)=\left[\text{по свойству 2}\right]=\left(\frac{2}{3}\right)\left(\frac{7}{17}\right).$$По свойству 1,
$$\left(\frac{2}{3}\right)={2}^{\frac{3-1}{2}}=-1mod3.$$Далее,
$$\left(\frac{7}{17}\right)={\left(-1\right)}^{\frac{16 \cdot 6}{4}}\left(\frac{17}{7}\right)=\left(\frac{3}{7}\right)={\left(-1\right)}^{\frac{6 \cdot 2}{4}}\left(\frac{7}{3}\right)=-\left(\frac{1}{3}\right)=-1.$$Итак, 51 - квадратичный вычет по модулю 449. Выберем другое число. Пусть выпало число 34.
$$\left(\frac{34}{449}\right)=\left(\frac{2}{449}\right)\left(\frac{17}{449}\right)={\left(-1\right)}^{\frac{{449}^{2}-1}{8}}\left(\frac{17}{449}\right)=\left(\frac{17}{449}\right)=\left(\frac{449}{17}\right)=\\ \left(\frac{7}{17}\right)=-1.$$Следовательно, число 34 является квадратичным вычетом по модулю 449.
Очевидным недостатком символа Лежандра является необходимость иногда применять свойство 3, требующее факторизации числа. Обобщение числа Лежандра, символ Якоби, который определяется для произвольного числа $$a$$ и нечетного числа $$n={p}_{1}{p}_{2}{\dots}{p}_{k}$$, где числа $${p}_{i}$$ - простые не обязательно различные числа, лишен этого недостатка.
По определению,
$$\left(\frac{a}{n}\right)=\left(\frac{a}{{p}_{1}}\right) \cdot \left(\frac{a}{{p}_{2}}\right){\dots}\left(\frac{a}{{p}_{k}}\right).$$Поскольку при простом $$n$$ символ Якоби равен символу Лежандра, одинаковое обозначение не введёт нас в заблуждение. Отметим, что символ Якоби не является полным аналогом символа Лежандра, т.е. равенство
$$\left(\frac{a}{n}\right)=\left\{\begin{array}{rl}0, \text{если $a$ не взаимно просто с } n;\\1, \text{если $a$ - квадратичный вычет}~(mod n);\\-1, \text{если $a$ - квадратичный невычет}~(mod n)\end{array}\right.$$в общем случае не выполняется.
Свойства символа Якоби:
Повторим наши вычисления из примера с помощью символа Якоби:
$$\left(\frac{51}{449}\right)={\left(-1\right)}^{\frac{448 \cdot 50}{4}}\left(\frac{449}{51}\right)=\left(\frac{41}{51}\right)={\left(-1\right)}^{\frac{50 \cdot 40}{4}}\left(\frac{51}{41}\right)=\left(\frac{10}{41}\right)=\\\left(\frac{2}{41}\right)\left(\frac{5}{41}\right)={\left(-1\right)}^{\frac{{41}^{2}-1}{8}}{\left(-1\right)}^{\frac{40 \cdot 4}{2}}\left(\frac{41}{5}\right)=1 \cdot 1 \cdot \left(\frac{1}{5}\right)=1.$$В некоторых криптографических алгоритмах требуется извлечение квадратного корня в кольце вычетов.
Задача нахождения квадратного корня по произвольному составному модулю сводится к задаче нахождения квадратного корня по простому модулю с помощью китайской теоремы об остатках. Для последней задачи существует много различных подходов. Один из них, алгоритм Тонелли-Шенкса, мы рассмотрим ниже.
Пусть $$p={2}^{s}q+1$$, где $$q$$ - нечетное число, $$z$$ - произвольный квадратичный невычет. Положим $$c={z}^{q}$$ и будем искать корень $$x=\sqrt{a}~(mod \ p)$$ в виде:
$$x={a}^{\frac{q+1}{2}} \cdot {c}^{{\alpha }_{0}+2{\alpha }_{1}+4{\alpha }_{2}+{\dots}}.$$Подставив в равенство $${x}^{{2}^{s-1}}={a}^{{2}^{s-2}}~(mod \ p)$$ выражение для $$x$$. Поскольку
$${\left({c}^{2{\alpha }_{1}+4{\alpha }_{2}+{\dots}}\right)}^{{2}^{s-1}}={z}^{q \cdot {2}^{s}({\alpha }_{1}+2{\alpha }_{2}+{\dots})}={z}^{(p-1)({\alpha }_{1}+2{\alpha }_{2}+{\dots})}=1~(mod \ p),$$то получим:
$${a}^{\frac{p-1}{4}} \cdot {a}^{{2}^{s-2}} \cdot {z}^{\frac{p-1}{2} \cdot {\alpha }_{0}}={a}^{{2}^{s-2}}~(mod \ p).$$Далее, заметим, что $${z}^{\frac{p-1}{2}}=\left(\dfrac{z}{p}\right)~(mod \ p)=-1$$, так как $$z$$ - квадратичный невычет, а $${a}^{\frac{p-1}{2}}=1~(mod \ p)$$, так как $$a$$ - квадратичный вычет. Поэтому $${a}^{\frac{p-1}{4}}$$ есть корень из единицы, и может быть либо 1, либо $$-1$$. В первом случае берём $${\alpha }_{0}=0$$, во втором $${\alpha }_{0}=1$$. В результате мы получаем:
$${a}^{\frac{p-1}{4}}{c}^{{{2}^{s-2}\alpha }_{0}}=1 \ mod \ p$$Теперь в равенство $${x}^{{2}^{s-2}}={a}^{{2}^{s-3}}~(mod \ p)$$ подставим выражение для $$x$$ и получим:
$${a}^{\frac{p-1}{8}}{a}^{{2}^{s-3}}{z}^{\frac{p-1}{4}{\alpha }_{0}+\frac{p-1}{2}{\alpha }_{1}}={a}^{{2}^{s-3}}~(mod \ p).$$Аналогично предыдущему, $${z}^{\frac{p-1}{2}{\alpha }_{1}}=-1~(mod \ p)$$, а $${a}^{\frac{p-1}{8}}{z}^{\frac{p-1}{4}{\alpha }_{0}}$$ является корнем из единицы и может быть либо 1, либо $$-1$$. В первом случае берём $${\alpha }_{1}=0$$, во втором $${\alpha }_{1}=1$$. Рассматривая аналогично равенства $${x}^{{2}^{s-3}}={a}^{{2}^{s-4}}~(mod \ p)$$, $${x}^{{2}^{s-4}}={a}^{{2}^{s-5}}~(mod \ p)$$, $$\dots$$, $${x}^{2}=a~(mod \ p)$$, мы найдём все коэффициенты $${\alpha }_{i}$$.
Данная идея реализуется алгоритмом Тонелли-Шенкса [2]:
Вход: $$p$$ - простое число, $$a$$ - квадратичный вычет по модулю $$p$$.
Выход: число $$x$$ такое, что $${x}^{2}=a~(mod \ p)$$.
Отметим, что на каждом шаге числа и $${b}_{i}$$ и $${t}_{i}$$ имеют мультипликативный порядок степень двойки, причем на каждом шаге он понижается, поэтому алгоритм задан корректно. Для нахождения порядка $$t_i$$ на шаге 5 нужно последовательно возводить его в степень.
Алгоритм Тонелли-Шенкса не позволяет находить корень по $$p$$-примарному модулю. Для решения этой задачи нам потребуется следующая идея. Если $$a$$ не делится на $$p$$, и мы вычислили $${x}_{0}$$ - корень из $$a$$ по модулю $$p$$, то корень $${x}_{1}$$ из $$a$$ по модулю $${p}^{n}$$ можно искать в виде $$x={x}_{0}+p{t}_{1}$$. Тогда мы получим:
$${x}^{2}={x}_{0}^{2}+2p{t}_{1}{x}_{0}+{p}^{2}{t}_{1}^{2}=a ~(mod {p}^{2}).$$Поскольку $${x}_{0}^{2}-a$$ делится на $$p$$, то имеем:
$$\frac{{x}_{0}^{2}-a}{p}+2{t}_{1}{x}_{0}=0~(mod \ p^{2}).$$Отсюда находим
$${t}_{1}={t'}_{1}+p{t}_{2},\ {t'}_{1}=\frac{-{{x}_{0}^{2}-a}}{p} \cdot \left({\left(2{x}_{0}\right)}^{-1}~(mod \ p)\right),\ {x}_{1}={x}_{0}+p{t'}_{1}.$$Отметим, что $${x}_{1}^{2}=a~(mod {p}^{2})$$, $$x={x}_{1}+{p}^{2}{t}_{2}$$. Тогда имеем:
$${x}^{2}={x}_{1}^{2}+2{p}^{2}{t}_{2}{x}_{1}+{p}^{4}{t}_{2}^{2}=a~(mod {p}^{2}).$$Поскольку $${x}_{1}^{2}-a$$ делится на $${p}^{2}$$, то имеем:
$$\frac{{x}_{1}^{2}-a}{{p}^{2}}+2{t}_{2}{x}_{1}=0~(mod {p}^{2}).$$Отсюда находим
$${t}_{2}={t'}_{2}+{p}^{2}{t}_{3},\ {t'}_{2}=\frac{-{{x}_{1}^{2}-a}}{{p}^{2}} \cdot \left({\left(2{x}_{1}\right)}^{-1}~(mod \ p)\right),\ {x}_{2}={x}_{1}+{p}^{2}{t'}_{2}.$$Продолжая последовательность $${x}_{i}$$ по описанному принципу, мы найдём $${x}_{n-1}^{2}=a~(mod \ p^{n}).$$
Если $$a$$ делится на $$p$$, имеем:
$${x}^{2}={a'}{p}^{v}+r{p}^{m},$$и $$x$$ делится на $$p$$. Следовательно, решение есть тогда и только тогда, когда $$a$$ делится на четную степень $$p$$, поэтому далее можем писать:
$${x}^{2}={a'}{p}^{2k}+r{p}^{m},\ x={p}^{k}\widetilde{x}.$$В этом случае два решения $$\pm \widetilde{x}$$ находим из уравнения $${\widetilde{x}}^{2}={a'}~(mod {p}^{m-2k})$$. Найдём остальные решения $$\pm \widetilde{x}+b$$ из уравнения:
$${p}^{2k}{\widetilde{x}}^{2}\pm 2{p}^{2k}\widetilde{x}b+{{p}^{2k}b}^{2}={p}^{2k}{a'}+l{p}^{m}.$$Далее,
$$\pm 2{p}^{2k}\widetilde{x}b+{p}^{2k}{b}^{2}=\left(l-r\right){p}^{m}.$$Поскольку $$\widetilde{x}$$ не делится на $$p$$, то $${p}^{2k}b$$ делится на $${p}^{m}$$, и $$b$$ делится на $${p}^{m-2k}$$. Наоборот, если $$b$$ - кратное числа $${p}^{m-k}$$, и $${\widetilde{x}}^{2}={a'}+r{p}^{m'}$$, то $${\left(p\left(\pm \widetilde{x}+b\right)\right)}^{2}=a~(mod \ p^{m})$$. Тогда корнями исходного уравнения будут $$x={p}^{k}(\pm \widetilde{x}+{rp}^{m-2k})$$ и только они.
Теперь зная, как извлекать квадратный корень по примарному модулю, можно извлекать квадратный корень по произвольному модулю. Из китайской теоремы об остатках следует, что $${x}^{2}=a~(mod \ p_{1}^{{n}_{1}}{p}_{2}^{{n}_{2}}{\dots}{p}_{r}^{{n}_{r}})$$ тогда и только тогда, когда $${x}^{2}=a~(mod \ ~(p_{i}^{{n}_{i}}))$$ для всех $$i$$.
Пример 1.37 Найти квадратный корень из $$63$$ по модулю $$81$$.
Имеем: $${x}^{2}=63 \ mod \ 81$$. Делим обе части на 9. Тогда: $${\widetilde{x}}^{2}=7~(mod \ 9),x=3\widetilde{x}.$$
Для нахождения $$\widetilde{x}$$ используем вышеописанный алгоритм.
Отсюда $$\widetilde{x}=\pm 4,x=3 \cdot \left(\pm 4+9r\right)=12,15,39,42,66,69$$.
Пример 1.38 Найти квадратный корень из $$387$$ по модулю $$567$$.
Поскольку $$567=81 \cdot 7$$, имеем: $${x}^{2}=18 \ mod\ 81$$, $${x}^{2}=2 \ mod \ 7$$. Из этих уравнений находим $$x=12,15,39,42,66,69 \ mod\ 81$$ (из предыдущего примера) и $$x=\pm 3~(mod \ 7)$$. Из полученных двенадцати систем уравнений по китайской теореме об остатках имеем:
$$x=255,417,339,501,444,39,528,123,66,228,150,312.$$
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.