Простейшие сведения о непрерывных дробях и их свойствах

Пусть число $\usepackage{amsfonts} x \in \mathbb {R}$ . Тогда обозначим через $q_1$ наибольшее целое число, меньшее $x$ . Если $x$ не целое число, то мы получим равенство вида $\displaystyle x = q_1 + \frac{1}{x_1}$ , так как дробь $\displaystyle \frac{1}{x_1} < 1$ , то $x_1>1$ , и тогда аналогично для $x_1$ находим такое целое $q_2 < x_1$ , получаем $\displaystyle x_1 = q_2 + \frac{1}{x_2}$ , возвращаясь к первому равенству $\displaystyle x = q_1 + \frac{1}{\displaystyle q_2 + \frac{1}{x_2}}$ . Продолжая этот процесс будем получать представления последующих $\displaystyle x_k:$ $x_2 = q_3 + \frac{1}{x_3},$ $x_3 = q_4 + \frac{1}{x_4},$ $\ldots$ $x_i = q_{i+1} + \frac{1}{x_{i+1}},$ $\ldots$

В итоге и получим непрерывную дробь: $\usepackage{amsmath} \begin{multline*} \displaystyle x = q_1 + \frac{1}{\displaystyle q_2+ \frac{1}{q_3+\cdots}} \\ \ddots \\ \cdots + \frac{1}{\displaystyle q_{n-1} + \frac{1}{\displaystyle q_{n}+\frac{1}{x_n}}}. \end{multline*}$

Далее, нам стоит рассмотреть два случая: первый — $\usepackage{amsfonts} x \in \mathbb {Q}$ , т. е. $x$ — рациональное число и второй — $\usepackage{amsfonts} x \in \mathbb {R} \setminus \mathbb {Q}$ , т. е. $x$ — иррациональное число. Почему важны именно эти случаи?

По определению, рациональное число представимо в виде несократимой дроби $\displaystyle \frac{m}{n}$ , где $\usepackage{amsfonts} m \in \mathbb {Z}, \; n \in \mathbb {N}$ , а, значит, и разложение, представленное сверху, должно быть конечным и, более того, может быть получено благодаря алгоритму Евклида.

С иррациональным числом получим ситуацию обратную — процесс можно будет продолжать неограниченно долго т. к. на каждом этапе $x_i$ будет иррационально.

Пусть $x_i$ — иррационально, тогда $\displaystyle x_i = q_{i+1} + \frac{1}{x_{i+1}},$ сумма $\displaystyle q_{i+1} + \frac{1}{x_{i+1}}$ — иррациональна, однако $q_{i+1}$ является целым по определению, которое мы дали ему выше $\Rightarrow$ дробь $\displaystyle \frac{1}{x_{i+1}}$ должна быть иррациональной. А это означает, что и $x_{i+1}$ — иррациональное число.

Т. е. получаем, что иррациональность $x_i$ влечёт за собой иррациональность $x_{i+1}$ , а т. к. изначальное число $x$ — иррационально, то и все $x_j,$ при $j = 1,2,3 \ldots$ — иррациональны.

Как было упомянуто ранее, если $\usepackage{amsfonts} x \in \mathbb {Q}$ , то его разложение в непрерывную дробь можно получить с помощью алгоритма Евклида.

Перед описанием алгоритма стоит ввести понятие неполного частного — это целые числа вида $q_i, \; i = \overline{1,n}$ .

Опишем сам алгоритм:

Суть алгоритма заключается в том, что на каждом шаге мы будем непосредственно получать одно из неполных частных — $q_i$ , а также отношение $\displaystyle \frac{r_{i}}{r_{i-1}}$ (начиная со второго шага).

Пусть нам задано рациональное число, тогда его можно записать в виде несократимой дроби $\displaystyle \frac{m}{n}$ , где $\usepackage{amsfonts} m \in \mathbb {Z}, \; n \in \mathbb {N}$ . Тогда, первый шаг: $m=nq_1 + r_1 \Rightarrow \displaystyle \frac{m}{n} = q_1 + \frac{1}{\displaystyle \frac{m}{r_1}},$ узнали значение $q_1$ , а так же получили возможность вычислить значение $r_1$ . Второй шаг: $n = r_1q_2+r_2 \Rightarrow \displaystyle \frac{n}{r_1} = q_2 + \frac{1}{\displaystyle \frac{r_1}{r_2}},$ узнали значение $q_2$ , а так же получили возможность вычислить значение $r_2$ . Продолжая алгоритм далее: $r_1 = r_2q_3+r_3 \Rightarrow \displaystyle \frac{r_1}{r_2} = q_3 + \frac{1}{\displaystyle \frac{r_2}{r_3}}, \\ r_2 = r_3q_4+r_4 \Rightarrow \frac{r_2}{r_3} = q_4 + \frac{1}{\displaystyle \frac{r_3}{r_4}},\\ \cdots \\r_{n-2} = r_{n-1}q_n+r_n \Rightarrow \frac{r_{n-2}}{r_{n-1}} = q_n + \frac{1}{\displaystyle \frac{r_{n-1}}{r_n}}, \\ r_{n-1} = r_nq_{n+1}, \frac{r_{n-1}}{r_n} = q_{n+1}.$ Заканчиваем алгоритм тогда, когда получим, что очередная дробь $\displaystyle \frac{r_{i-1}}{r_{i}}$ будет целым числом и, соответственно, $q_{i+1}$ будет полным частным.

Так как найдены все неполные частные, то дробь $\displaystyle \frac{m}{n}$ можно представить в виде: $\usepackage{amsmath} \begin{multline*} \displaystyle x = q_1 + \frac{1}{\displaystyle q_2+ \frac{1}{q_3+\cdots}} \\ \ddots \\ \cdots + \frac{1}{\displaystyle q_{n-1} + \frac{1}{\displaystyle q_{n}+\frac{1}{q_{n+1}}}}. \end{multline*}$

С помощью алгоритма Евклида есть возможность найти разложение в непрерывную дробь, однако, иногда промежуточные результаты важнее конечного, а именно: $\displaystyle \delta_1 = q_1, \; \delta_2 = q_1 + \frac{1}{q_2}, \; \delta_3 = q1 + \frac{1}{q_2 + \displaystyle \frac{1}{q_3}}, \; \ldots$ $\delta_i$ называются . Несложно заметить зависимость $\delta_{i+1}$ от $\delta_i$ — если в записи $\delta_i$ число $q_i$ заменить на сумму $\displaystyle q_i + \frac{1}{q_{i+1}}$ , то мы получим $\delta_{i+1}.$

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

Введем специальные обозначения для нахождения значений подходящих дробей: $\displaystyle \delta_i = \frac{P_i}{Q_i}$ . При этом положим, что $P_0=1, \; P_1 = q_1$ и $Q_0=0, \; Q_1 = 1$ . Так же стоит отметить, что в силу того, что для рационального числа $\displaystyle x = \frac{m}{n}$ непрерывная дробь конечна, то и количество подходящих дробей будет конечно, а это означает что существует равенство $\displaystyle \frac{m}{n} = \frac{P_i}{Q-i}$ . А так как подходящие дроби так же являются несократимыми, то равенство можно упростить до $m = P_i$ и $n = Q_i$ . Тогда получим, что: $\displaystyle \delta_1 = \frac{q_1}{1} = \frac{P_1}{Q_1},$ $\delta_2 = q_1 + \frac{1}{q_2} = \frac{q_2 q_1+1}{q_2 \cdot 1 + 0} = \frac{q_2 P_1+P_0}{q_2 Q_1 + Q_0} = \frac{P_2}{Q_2},$ $\delta_3 = q1 + \frac{1}{q_2 + \displaystyle \frac{1}{q_3}} = \frac{q_1 \left( q_2 + \displaystyle \frac{1}{q_3} \right) +1}{q_2 + \displaystyle \frac{1}{q_3}} = \frac{q_1 \left( q_2 q_3 + 1\right)+q_3}{q_2 q_3 +1} =$ $= \frac{q_1 q_2 q_3 + q_1 +q_3}{q_2 q_3} = \frac{q_3 \left( q_1 q_2 + 1 \right) + q_1}{q_3 q_2 + 1} = \frac {q_3 P_2 + P_1}{q_3 Q_2 + Q_1}.$

Несложно заметить рекуррентное выражение для $\displaystyle \frac{P_i}{Q_i}$ : $P_i = q_i P_{i-1} + P_{i-2} \\ Q_i = q_i Q_{i-1} + Q_{i-2}.$ Докажем это с помощью математической индукции.

База индукции: $\delta_3 = \displaystyle \frac{P_3}{Q_3} = \frac{q_3 P_2 + P_1}{q_3 Q_2 + Q_1}$ .

Предположим, что $\delta_k = \displaystyle \frac{P_k}{Q_k} =\frac{q_k P_{k-1} + P_{k-2}}{q_k Q_{k-1} + Q_{k-2}}$ .

Тогда: $\delta_{k+1} = \frac{\displaystyle \left(q_k + \frac{1}{q_{k+1}} \right) P_{k-1} + P_{k-2} }{\displaystyle \left(q_k + \frac{1}{q_{k+1}} \right) Q_{k-1} + Q_{k-2}} = \frac {\displaystyle \frac{P_{k-1}}{q_{k+1}} + q_k P_{k-1} + P_{k-2}}{\displaystyle \frac{Q_{k-1}}{q_{k+1}} + q_k Q_{k-1} + Q_{k-2}} =$ (выполним замену по предположению индукции) $\displaystyle = \frac{\displaystyle \frac{P_{k-1}}{q_{k+1}} + P_k}{\displaystyle \frac{Q_{k-1}}{q_{k+1}} + Q_k} = \frac{P_{k-1} + P_k q_{k+1}}{Q_{k-1} + Q_k q_{k+1}} = \frac{P_{k+1}}{Q_{k+1}},$ что и требовалось доказать.

Имеет место следующее свойство подходящих дробей:

При $n > 0$ имеет место равенство $P_n Q_{n-1} — P_{n-1}Q_n = (-1)^n$ .

Проверим значение левой части при $n = 1$ , получим: $P_1 Q_0 — P_0 Q_1 = -1,$ далее вычислим значение левой части при увеличении индекса на 1, т. е. при $n+1,$ получим: $P_{n+1} Q_n — P_n Q_{n+1} = \left( q_{n+1} P_n + P_{n-1} \right) Q_n — P_n \left( q_{n+1} Q_n + Q_{n-1} \right) = \\ = P_{n-1} Q_n — P_{n} Q_{n-1},$ получили выражение противоположное заданному в условии. А, значит, при изменении индекса на единицу меняется и знак выражения, а т. к. первое значение $-1$ , то и получаем требуемое.

Примеры решения задач

Рассмотрим примеры задач в которых могут быть использованы непрерывные дроби. Рекомендуется сначала решать примеры самому, а только затем сверить решение с представленным ниже.

Разложить число $\displaystyle x = \frac{89}{13}$ в непрерывную дробь.

Решение

Применяя алгоритм Евклида получим: $89 = 13 \cdot 6 + 11, \; q_1 = 6;$ $13 = 11 \cdot 1 + 2, \; q_2 = 1;$ $11 = 2 \cdot 5 + 1, \; q_3 = 5;$ $2 = 1 \cdot 2, \; q_4 = 2.$ Нашли все $q_i \Rightarrow$ можем записать $x$ как непрерывную дробь: $\displaystyle x = 6 + \frac{1}{\displaystyle 1 + \frac{1}{\displaystyle 5 + \frac{1}{2}}}$
Найти все подходящие дроби числа $\displaystyle x = \frac{127}{19}$ .

Решение

Для этого используем рекуррентные формулы подходящих дробей. Воспользуемся алгоритмом Евклида для поиска всех $q_i$ : $127 = 19 \cdot 6 + 13, \; q_1 = 6;$ $19 = 13 \cdot 1 + 6, \; q_2 = 1;$ $13 = 6 \cdot 2 + 1, \; q_3 = 2;$ $6 = 1 \cdot 6, \; q_4 = 6.$
Далее будем выписывать подходящие дроби в порядке возрастания индекса: $\displaystyle \delta_1 =\frac{q_1}{1} = \frac{6}{1}$ $\displaystyle \delta_2 =\frac{q_2 P_1 + P_0}{q_2 Q_1 + Q_0} = \frac{1 \cdot 6 + 1}{1 \cdot 1 + 0} = \frac{7}{1},$ продолжая расчеты получим: $\displaystyle \delta_3 = \frac{2 \cdot 7 + 6}{2 \cdot 1 + 1} = \frac{20}{3}$ и, наконец, $\displaystyle \delta_4 = \frac{6 \cdot 20 + 7}{6 \cdot 3 + 1} = \frac{127}{19} = x,$ как и ожидалось четвертая подходящая дробь равна заданному числу, т. к. максимальный индекс $q_i$ был равен четырём.
Разложить в непрерывную дробь иррациональное число $\sqrt{7}$ .

Решение

Для этого воспользуемся разложением, которое было представлено в теме первым. А именно
$\displaystyle x_0 = \sqrt{7} = q_1 + \frac{1}{x_1} = 2 + \left( \sqrt{7} — 2 \right)$ $\displaystyle \frac{1}{x_1} = \sqrt{7} — 2 \Rightarrow x_1 = \frac{1}{\sqrt{7}-2} = \frac{\sqrt{7}+2}{3} = 1 + \frac{\sqrt{7}-1}{3} = 1 + \frac{1}{x_2},$ $\displaystyle x_2 = \frac{3}{\sqrt{7}-1} = \frac{3 \left( \sqrt{7} + 1 \right) }{6} = \frac{\sqrt{7}+1}{2} = 1 + \frac{\sqrt{7} — 1}{2} = 1 + \frac{1}{x_3},$ $\displaystyle x_3 = \frac{2}{\sqrt{7}-1} = \frac{2 \left( \sqrt{7} + 1 \right) }{6} = \frac{\sqrt{7}+1}{3} = 1 + \frac{\sqrt{7} — 2}{3} = 1 + \frac{1}{x_4},$ $\displaystyle x_4 = \frac{3}{\sqrt{7} — 2} = \frac{3 \left(\sqrt{7} + 2 \right) }{3} = \sqrt{7} + 2 = 4 + \left( \sqrt{7} — 2 \right).$
Однако, слагаемое вида $\sqrt{7} — 2$ у нас уже было, а значит мы пришли к циклу. Выпишем все неполные частные, они же — целые части дробей. Получим: $\sqrt{7} = \left[2,\: \overline{1, \: 1, \: 1, \: 4} \right]$ — часть чисел находятся под чертой т. к. они находятся в цикле.
Восстановить по заданным $q_i = \left[10, \: 4, \: 3, \: 2, \: 4 \right]$ рациональное число $x$ .

Решение

Для этого воспользуемся разложением, полученным в результате алгоритма Евклида:
Получим дробь: $10 + \frac{1}{\displaystyle 4 + \frac{1}{\displaystyle 3 + \frac{1}{\displaystyle 2 + \frac{1}{4}}}},$ её значением и будет искомым $x$ . Посчитав значение этой дроби получим, что $\displaystyle x = \frac{1361}{133}.$
Восстановить по заданным $q_i = \left[\overline{2, \: 9} \right]$ иррациональное число $x$ .

Решение

Так как число $x$ — иррациональное, то его непрерывная дробь будет бесконечной, поэтому воспользоваться методом из предыдущего примера не получится. Однако, так как мы видим по данным $q_i$ , что дробь зацикливается, то можем записать следующие выражение: $\displaystyle x = 2 + \frac{1}{\displaystyle 9 + \frac{1}{x}}$ приведем дробь к квадратному уравнению: $9x^2 — 18x + 2 = 0,$ $D = 324 + 72 = 396, \; \displaystyle x_{1,2} = 1 \pm \frac{\sqrt{396}}{18}.$ Т. к. целая часть числа равна 2, то вариант $\displaystyle x = 1-\frac{\sqrt{396}}{18}$ можно отбросить. И окончательный ответ: $\displaystyle x = 1 + \frac{\sqrt{396}}{18}$

Простейшие сведения о непрерывных дробях и их свойствах

Тест на знание темы «Простейшие сведения о непрерывных дробях и их свойствах».

Задание 1 из 6

1.
Какая из данных непрерывных дробей имеет ровно $3$ неполных частных?
- $\displaystyle \frac{415}{94}$
- $\displaystyle \frac{416}{94}$
- $\displaystyle \frac{415}{93}$
- $\displaystyle \frac{416}{93}$
Правильно

Неправильно
Задание 2 из 6

2.
Выберите все дроби, которые являются подходящими для $\displaystyle x = \frac{227}{53}$
- $4$
- $\displaystyle \frac{14}{3}$
- $\displaystyle \frac{17}{4}$
- $\displaystyle \frac{35}{8}$
- $\displaystyle \frac{30}{7}$
Правильно

Неправильно
Задание 3 из 6

3.
Отсортировать числа по убыванию количества их неполных частных.
- $\displaystyle \frac{923}{1089}$
- $\displaystyle \frac{532}{235}$
- $\displaystyle \frac{1039}{57}$
- $\displaystyle \frac{103}{7}$
- $\displaystyle \frac{65}{9}$
Правильно

Неправильно
Задание 4 из 6

4.
Найдите сумму чисел, образующих цикл в представлении числа $x = \sqrt{13}$ как непрерывной дроби.
Правильно

Неправильно

Задание 5 из 6

5.

Сопоставьте иррациональные числа с количеством чисел, которые образуют цикл при представлении данных иррациональных числе в виде непрерывных дробей.

Элементы сортировки

$\sqrt{12}$

$\sqrt{17}$

$\sqrt{29}$

$\sqrt{34}$

Задание 6 из 6

6.
Заполните пропуски
- Если число (рациональное), то количество его неполных частных будет числом конечным, а если (иррациональное), то бесконечным.
Правильно

Неправильно

Смотрите также

Виноградов И.М. Основы теории чисел. cтр. 14-18
Арнольд В.И. Цепные дроби.
Теоретические материалы основанные на конспекте и лекциях Белозерова Г.С.

НОД двух многочленов

Для многочленов, также как и для множества целых чисел, можно определить наибольший общий делитель (НОД) и наименьшее общее кратное.

При определении понятия НОД, для начала необходимо ознакомиться с понятием общего делителя двух многочленов. Заранее для краткости и удобства договоримся, что в дальнейшем под понятиями общего делителя и наибольшего общего делителя мы будем подразумевать их аналоги на множестве $P\left[x\right].$

Определение 1 (общий делитель)

Пусть даны $f\left(x\right), g\left(x\right) \in P\left[x\right],$ причем $f\left(x\right), g\left(x\right) \neq 0.$ Тогда общим делителем этих многочленов будет являться многочлен $d\left(x\right) \in P\left[x\right]$ при условии, что $f\left(x\right) \vdots d\left(x\right)$ и $g\left(x\right) \vdots d\left(x\right).$

Замечание. Любая ненулевая константа является общим делителем для любых двух многочленов.

Пусть $f\left(x\right) = x^8-1,$ $g\left(x\right) = x^4-1.$ Для того, чтобы найти общие делители разложим эти многочлены по формуле разности квадратов: $f\left(x\right) = x^8-1 = \left(x^4-1\right)\left(x^4 + 1\right) = \left(x^2-1\right)\left(x^2 + 1\right)\left(x^4 + 1\right) =\\= \left(x-1\right)\left(x + 1\right)\left(x^2 + 1\right)\left(x^4 + 1\right),$ $g\left(x\right) = x^4-1 = \left(x^2-1\right)\left(x^2 + 1\right) = \left(x-1\right)\left(x + 1\right)\left(x^2 + 1\right).$ Как мы видим, общими делителями являются $\left(x-1\right),$ $\left(x + 1\right)$ и $\left(x^2 + 1\right).$

Было бы некорректно применять такое определение НОД, по которому наибольшим общим делителем двух многочленов является их общий делитель наибольшей степени, т.к. оно является слишком обобщенным. Поэтому мы введём такое понятие:

Определение 2 (наибольший общий делитель)

Пусть даны $f\left(x\right), g\left(x\right) \in P\left[x\right],$ причем $f\left(x\right), g\left(x\right) \neq 0.$ Тогда многочлен $d\left(x\right) \in P\left[x\right]$ будет являться их наибольшим общим делителем, если сам будет являться их общим делителем, который делится на любые другие общие делители $f\left(x\right)$ и $g\left(x\right).$ Обозначение: $d\left(x\right) = \left(f\left(x\right), g\left(x\right)\right)$ — НОД для $f\left(x\right), g\left(x\right) \in P\left[x\right].$

Пусть $f\left(x\right) = 0$ и $g\left(x\right) = 0.$ Тогда НОД $\left(f\left(x\right), g\left(x\right)\right) = 0.$

Лемма. НОД определен (если существует) с точностью до постоянного ненулевого множителя.

Пусть даны $f\left(x\right), g\left(x\right) \in P\left[x\right],$ для которых $d_1\left(x\right), d_2\left(x\right) \in P\left[x\right]$ — два НОД.

Тогда, по определению, $d_1\left(x\right) \vdots d_2\left(x\right)$ и $d_2\left(x\right) \vdots d_1\left(x\right).$ По свойству делимости $\left(f\left(x\right) \vdots g\left(x\right) \wedge g\left(x\right) \vdots f\left(x\right) \Leftrightarrow \exists c \in P^*: f\left(x\right) = c \cdot g\left(x\right)\right)$ $d_1\left(x\right) = c_1 \cdot d_2\left(x\right),$ $c_1 \in P^*,$ $c_1 = \text{const}.$

Пусть $\exists c_2 \in P^*,$ $c_2 = \text{const}.$ Тогда, если $d_2\left(x\right)$ — общий делитель для $f\left(x\right)$ и $g\left(x\right)$ (по определению), то и $c_2 \cdot d_2\left(x\right)$ — тоже общий делитель. Соответственно, если $d_2\left(x\right)$ — НОД, т.е. делится на любой другой общий делитель (по определению), то и $c_2 \cdot d_2\left(x\right)$ — тоже является НОД.

Возьмём те же $f\left(x\right)$ и $g\left(x\right),$ что и в примере 1: $f\left(x\right) = x^8-1,$ $g\left(x\right) = x^4-1.$ Чтобы найти НОД этих многочленов, разложим их так же, как и в предыдущем примере: $f\left(x\right) = x^8-1 = \left(x^4-1\right)\left(x^4 + 1\right) = \left(x^2-1\right)\left(x^2 + 1\right)\left(x^4 + 1\right) =\\= \left(x-1\right)\left(x + 1\right)\left(x^2 + 1\right)\left(x^4 + 1\right),$ $g\left(x\right) = x^4-1 = \left(x^2-1\right)\left(x^2 + 1\right) = \left(x-1\right)\left(x + 1\right)\left(x^2 + 1\right).$ Очевидно, что наибольшим общим делителем будет являться $\left(x^4-1\right).$

Теперь разберем способ получения НОД двух многочленов. Находить его можно таким же способом, что и для двух целых чисел, — алгоритмом Евклида (или алгоритмом последовательного деления).

Замечание. С помощью этого алгоритма доказывается существование НОД двух многочленов.

Построим НОД для двух многочленов с помощью алгоритма Евклида. Пусть даны $f\left(x\right) = x^4+x^3-3x^2-4x-1$ и $g\left(x\right) = x^4+x^3-x-1.$

$x^4$	$+$	$x^3$	$-$	$3x^2$	$-$	$4x$	$-$	$1$
$x^4$	$+$	$x^3$			$-$	$x$	$-$	$1$
			$-$	$3x^2$	$-$	$3x$

$x^4$	$+$	$x^3$	$-$	$x$	$-$	$1$
$1$

$x^4$	$+$	$x^3$	$-$	$x$	$-$	$1$
$x^4$	$+$	$x^3$
			$-$	$x$	$-$	$1$

$-$	$3x^2$	$-$	$3x$
$-$	$\frac{1}{3}x^2$

$-$	$3x^2$	$-$	$3x$
$-$	$3x^2$	$-$	$3x$
			$0$

$-$	$x$	$-$	$1$
$3x$

Последний ненулевой остаток и будет являться НОД этих многочленов, т.е. НОД $\left(f\left(x\right), g\left(x\right)\right) = -x-1.$

Может возникнуть случай, когда НОД двух многочленов будет равен $1.$ При этом говорят, что многочлены являются взаимно простыми.

Пусть даны $f\left(x\right) = -x^3+x-1$ и $g\left(x\right) = x-2.$ Найдем их НОД. Для удобства умножим $f\left(x\right)$ на $-1,$ получим $f\left(x\right) = x^3-x+1.$

$x^3$	$+$	$0x^2$	$-$	$x$	$+$	$1$
$x^3$	$+$	$2x^2$
		$2x^2$	$-$	$x$	$+$	$1$
		$2x^2$	$-$	$4x$
				$3x$	$+$	$1$
				$3x$	$-$	$6$
						$7$

$x$	$-$	$2$
$x^2$	$+$	$2x$	$+$	$3$

Таким образом, многочлен $q\left(x\right) = x^2+2x+3$ — частное деления многочленов, а $r\left(x\right) = 7$ — остаток. Дальнейшее деление можно не продолжать, т.к. и так понятно, что в следующем остатке мы получим $0,$ т.е. $7$ будет последним ненулевым остатком, после умножения которого на $\displaystyle\frac{1}{7},$ НОД $\left(f\left(x\right), g\left(x\right)\right) = 1.$ Следовательно, $f\left(x\right)$ и $g\left(x\right)$ — взаимно простые.

Также стоит упомянуть и линейное представление НОД: $d\left(x\right) = f\left(x\right) \cdot u\left(x\right) + g\left(x\right) \cdot v\left(x\right),$ где $f\left(x\right), g\left(x\right), u\left(x\right), v\left(x\right) \in P\left[x\right],$ а $d\left(x\right) = \left(f\left(x\right), g\left(x\right)\right).$

Примеры решения задач

Определить наибольший общий делитель многочленов:

$f\left(x\right) = x^2-9$ и $g\left(x\right) =x^3-27;$
$f\left(x\right) = x^5+x^3+x$ и $g\left(x\right) = x^4+x^3+x;$

Решение (пример a.)

Для построения НОД воспользуемся алгоритмом Евклида. Так как степень многочлена $g\left(x\right)$ больше степени многочлена $f\left(x\right),$ то мы будем делить $g\left(x\right)$ на $f\left(x\right).$

$x^3$	$+$	$0x^2$	$+$	$0x$	$-$	$27$
$x^3$			$-$	$9x$
				$9x$	$-$	$27$

$x^2$	$-$	$9$
$x$

После первого деления мы получили остаток $r_1\left(x\right) = 9x-27.$ Для удобства мы можем умножить его на $\displaystyle\frac{1}{9}.$ Получим $r_1\left(x\right) = x-3.$

Продолжаем наше деление, только в этот раз мы делим многочлен $g\left(x\right)$ на остаток $r_1\left(x\right).$

$x^2$	$+$	$0x$	$-$	$9$
$x^2$	$-$	$3x$
		$3x$	$-$	$9$
		$3x$	$-$	$9$
				$0$

$x$	$-$	$3$
$x$	$+$	$3$

Теперь в остатке мы получили $0$ — значит деление закончено. Последний ненулевой остаток и будет являться НОД многочленов $f\left(x\right)$ и $g\left(x\right).$ В нашем случае это $x+3.$

Ответ: НОД $\left(f\left(x\right), g\left(x\right)\right) = x+3.$

[свернуть]

Решение (пример b.)

Также как и в прошлом примере, воспользуемся алгоритмом последовательного деления.

$x^5$	$+$	$0x^4$	$+$	$x^3$	$+$	$0x^2$	$+$	$x$
$x^5$	$+$	$x^4$			$+$	$x^2$
	$-$	$x^4$	$+$	$x^3$	$-$	$x^2$	$+$	$x$
	$-$	$x^4$	$-$	$x^3$			$-$	$x$
				$2x^3$	$-$	$x^2$	$+$	$2x$

$x^4$	$+$	$x^3$	$+$	$x$
$x$	$-$	$1$

В результате первого деления мы получили остаток $r_1\left(x\right) = x-1.$ Продолжаем деление.

$x^4$	$+$	$x^3$	$+$	$0x^2$	$+$	$x$
$x^4$	$-$	$\frac{1}{2}x^3$	$+$	$x^2$
		$\frac{3}{2}x^3$	$-$	$x^2$	$+$	$x$
		$\frac{3}{2}x^3$	$-$	$\frac{3}{4}x^2$	$+$	$\frac{3}{2}x$
			$-$	$\frac{1}{4}x^2$	$-$	$\frac{1}{2}x$

$2x^3$	$-$	$x^2$	$+$	$2x$
$\frac{1}{2}x$	$+$	$\frac{3}{4}$

Для удобства умножим остаток $r_2\left(x\right) = -\frac{1}{4}x^2-\frac{1}{2}x$ на $-4$ и получим $r_2\left(x\right) = x^2+2x.$ Продолжаем деление.

$2x^3$	$-$	$x^2$	$+$	$2x$
$2x^3$	$+$	$4x^2$
	$-$	$5x^2$	$+$	$2x$
	$-$	$5x^2$	$-$	$10x$
				$12x$

$x^2$	$+$	$2x$
$2x$	$-$	$5$

Третий остаток умножим на $\displaystyle\frac{1}{12}$ и получим $r_3\left(x\right) = x.$ Поделим в последний раз.

$x^2$	$+$	$2x$
$x^2$
		$2x$
		$2x$
		$0$

$x$
$x$	$+$	$2$

Как мы видим, последний ненулевой остаток равен $x$ — это и будет нашим НОД.

Ответ: НОД $\left(f\left(x\right), g\left(x\right)\right) = x.$

[свернуть]

Пользуясь алгоритмом Евклида, убедиться в том, что многочлены

$f\left(x\right)$ и

$g\left(x\right)$ взаимно простые, и подобрать

$u\left(x\right)$ и

$v\left(x\right)$ так, чтобы

$f\left(x\right) \cdot u\left(x\right) + g\left(x\right) \cdot v\left(x\right) = 1:$

$f\left(x\right) = 3x^3-2x^2+x+2,\\ g\left(x\right) =x^2-x+1.$

Решение

Как и сказано в условии задачи, воспользуемся алгоритмом Евклида, чтобы проверить равен ли НОД наших многочленов $1.$ В отличии от прошлого задания, здесь надо запоминать все частные и остатки.

$3x^3$	$-$	$2x^2$	$+$	$x$	$+$	$2$
$3x^3$	$-$	$3x^2$	$+$	$3x$
		$x^2$	$-$	$2x$	$+$	$2$
		$x^2$	$-$	$x$	$+$	$1$
			$-$	$x$	$+$	$1$

$x^2$	$-$	$x$	$+$	$1$
$3x$	$+$	$1$		$=$	$q_1\left(x\right)$

Получили остаток $r_1\left(x\right) = -x+1.$ Продолжаем деление.

$x^2$	$-$	$x$	$+$	$1$
$x^2$	$-$	$x$
				$1$

$-$	$x$	$+$	$1$
$-$	$x$			$=$	$q_2\left(x\right)$

$r_2\left(x\right) = 1,$ следовательно НОД $\left(f\left(x\right), g\left(x\right)\right) = 1,$ значит, наши многочлены взаимно простые и можно продолжать решать. Запишем многочлены в таком виде: $\begin{cases} f\left(x\right) = g\left(x\right) \cdot q_1\left(x\right) + r_1\left(x\right); \\ g\left(x\right) = r_1\left(x\right) \cdot q_2\left(x\right) + r_2\left(x\right). \end{cases}$ Выразим $r_1\left(x\right)$ из первого равенства и подставим во второе: $\begin{cases} r_1\left(x\right) = f\left(x\right)-g\left(x\right) \cdot q_1\left(x\right); \\ g\left(x\right) = \left(f\left(x\right)-g\left(x\right) \cdot q_1\left(x\right)\right) \cdot q_2\left(x\right) + r_2\left(x\right). \end{cases}$ Помня про то, что $r_2\left(x\right) = d\left(x\right),$ продолжаем наши преобразования: $f\left(x\right) \cdot \left(-q_2\left(x\right)\right) + g\left(x\right) \cdot \left(1 + q_1\left(x\right) \cdot q_2\left(x\right)\right) = d\left(x\right).$ Подставляем значения: $f\left(x\right) \cdot \left(x\right) + g\left(x\right) \cdot \left(-3x^2-x+1\right) = d\left(x\right).$

Если сравнить данное равенство с формулой линейного представления НОД, мы увидим, что получили $u\left(x\right) = x$ и $v\left(x\right) = -3x^2-x+1.$

Ответ: $u\left(x\right) = x,$ $v\left(x\right) = -3x^2-x+1.$

[свернуть]

Пользуясь алгоритмом Евклида, найти многочлены

$u\left(x\right)$ и

$v\left(x\right)$ такие, чтобы они удовлетворяли равенству

$f\left(x\right) \cdot u\left(x\right) + g\left(x\right) \cdot v\left(x\right) = d\left(x\right),$ где

$d\left(x\right)$ — НОД многочленов

$f\left(x\right)$ и

$g\left(x\right):$

$f\left(x\right) = x^4+2x^3-x^2-4x-2,\\ g\left(x\right) = x^4+x^3-x^2-2x-2.$

Решение

Для начала необходимо построить НОД. Для этого используем алгоритм Евклида.

$x^4$	$+$	$2x^3$	$-$	$x^2$	$-$	$4x$	$-$	$2$
$x^4$	$+$	$x^3$	$-$	$x^2$	$-$	$2x$	$-$	$2$
		$x^3$			$-$	$2x$

$x^4$	$+$	$x^3$	$-$	$x^2$	$-$	$2x$	$-$	$2$
$1$				$=$	$q_1\left(x\right)$

Получили остаток $r_1\left(x\right) = x^3-2x.$ Делим дальше.

$x^4$	$+$	$x^3$	$-$	$x^2$	$-$	$2x$	$-$	$2$
$x^4$			$-$	$2x^2$
		$x^3$	$+$	$x^2$	$-$	$2x$	$-$	$2$
		$x^3$			$-$	$2x$
				$x^2$			$-$	$2$

$x^3$	$-$	$2x$
$x$	$+$	$1$			$=$	$q_2\left(x\right)$

Второй остаток $r_2\left(x\right) = x^2-2.$ Выполняем последнее деление.

$x^3$	$-$	$2x$
$x^3$	$-$	$2x$
		$0$

$x^2$	$-$	$2$
$x$				$=$	$q_3\left(x\right)$

$r_3\left(x\right) = 0,$ следовательно НОД $\left(f\left(x\right), g\left(x\right)\right) = x^2-2.$ Дальнейшие наши действия ведутся по тому же принципу, что и в прошлой задаче, поэтому запишем многочлены в таком виде: $\begin{cases} f\left(x\right) = g\left(x\right) \cdot q_1\left(x\right) + r_1\left(x\right); \\ g\left(x\right) = r_1\left(x\right) \cdot q_2\left(x\right) + r_2\left(x\right). \end{cases}$ Выразим $r_1\left(x\right)$ и подставим его во второе равенство: $\begin{cases} r_1\left(x\right) = f\left(x\right)-g\left(x\right) \cdot q_1\left(x\right); \\ g\left(x\right) = \left(f\left(x\right)-g\left(x\right) \cdot q_1\left(x\right)\right) \cdot q_2\left(x\right) + r_2\left(x\right). \end{cases}$ Помним, что $r_2\left(x\right) = d\left(x\right),$ поэтому делаем замену: $f\left(x\right) \cdot \left(-q_2\left(x\right)\right) + g\left(x\right) \cdot \left(1 + q_1\left(x\right) \cdot q_2\left(x\right)\right) = d\left(x\right).$ Подставляем значения: $f\left(x\right) \cdot \left(-x-1\right) + g\left(x\right) \cdot \left(x+2\right) = d\left(x\right).$

Итак, мы получили $u\left(x\right) = -x-1$ и $v\left(x\right) = x+2.$ На этом можно и закончить, но иногда стоит перепроверить правильность своих вычислений. Для проверки нам необходимо вместо $f\left(x\right)$ и $g\left(x\right)$ подставить их значения, а после раскрыть скобки. Если в итоге мы получим многочлен равный построенному НОД, то $u\left(x\right)$ и $v\left(x\right)$ подобраны верно. В нашем случае все сходится, а значит мы можем записывать их в ответ.

Ответ: $u\left(x\right) = -x-1,$ $v\left(x\right) = x+2.$

[свернуть]

Тест на проверку знаний по теме «НОД двух многочленов»

Задание 1 из 5

1.
Количество баллов: 2
Что означает аббревиатура «НОД»?
Задание 2 из 5

2.
Количество баллов: 2
При каких $f\left(x\right)$ и $g\left(x\right)$ возможно существование их наибольшего общего делителя?
- $f\left(x\right), g\left(x\right) \in P\left[x\right]$ ; $f\left(x\right), g\left(x\right) = 0$
- $f\left(x\right), g\left(x\right) \in P\left[x\right]$ ; $f\left(x\right), g\left(x\right) \neq 0$
- $f\left(x\right), g\left(x\right) \notin P\left[x\right]$ ; $f\left(x\right), g\left(x\right) = 0$
- $f\left(x\right), g\left(x\right) \notin P\left[x\right]$ ; $f\left(x\right), g\left(x\right) \neq 0$
Задание 3 из 5

3.
Количество баллов: 4
Выберите все правильные утверждения
- Общим делителем для $f\left(x\right)$ и $g\left(x\right)$ может являться многочлен $d\left(x\right)$ при условии, что $f\left(x\right) \vdots g\left(x\right)$ и $g\left(x\right) \vdots d\left(x\right)$ .
- Не любая ненулевая константа может являться общим делителем для любых двух многочленов.
- Любая ненулевая константа является общим делителем для любых двух многочленов.
- Если $f\left(x\right) = 0$ и $g\left(x\right) = 0$ , то НОД $\left(f\left(x\right), g\left(x\right)\right) = 0$ .
- НОД определен (если существует) с точностью до нулевого множителя.

Задание 4 из 5

4.

Количество баллов: 4

Установите соответствие между многочленами $f\left(x\right)$ , $g\left(x\right)$ и их НОД $d\left(x\right)$ .

Элементы сортировки

$d\left(x\right) = x$
$d\left(x\right) = 1$
$d\left(x\right) = 2x^5-1$
$d\left(x\right) = x^2+x+1$

$f\left(x\right) = 3x^3+2x^2+x\\g\left(x\right) = x^3+2x^2+3x$

$f\left(x\right) = x^4+2x^2+4\\g\left(x\right) = 4x^4+2x^2+1$

$f\left(x\right) = -4x^{10}+1\\g\left(x\right) = 2x^5-1$

$f\left(x\right) = x^5+x^4+1\\g\left(x\right) = x^4+x^2+1$

Задание 5 из 5

5.
Количество баллов: 3
Вставьте пропущенное слово.
- Для построения НОД двух многочленов необходимо воспользоваться алгоритмом (Евклида), другое название которого - алгоритм последовательного деления.
  
  Деление нужно продолжать до того момента, когда мы получим в остатке . Тогда наибольшим общим делителем многочленов будет являться последний остаток.

Фадеев Д. К. Лекции по алгебре: Учебное пособие для вузов. — М., Наука. Главная редакция физико-математической литературы, 1984. — 416 с., стр. 168-170
Курош А. Г. Курс высшей алгебры — И., Наука. Главная редакция физико-математической литературы, 1968. — 431 с., стр. 137-141
Личный конспект, составленный на основе лекций Белозерова Г.С.

Алгоритм Евклида

Алгоритм Евклида — это эффективный алгоритм для нахождения НОД. Для натуральных чисел, таких как $9$ и $6,$ достаточно было просто перебирать числа для нахождения НОД. Если же перебирать числа для более сложных примеров, как, например, $52152$ и $9875,$ то процесс нахождение НОД будет слишком долгим. Поэтому, вместо того чтобы перебирать числа, можно просто выполнить ряд простых действий.

Даны числа $A, B \in \mathbb{Z}^{+},$ где $A \geqslant B$ и $r_{k}, q_{k} \in \mathbb{Z}^{+},$ при $k = 1,2,3…n,$ где $r_k$ — остаток, а $q_{k}$ — частное. Находим ряд равенств: $A = Bq_{1} + r_{1}$ $B = r_{1}q_{2}+r_2$ $r_{1} = r_{2}q_{3}+r_{3}$ $……$ $r_{n-1} = r_{n}q_{n+1}+0,$ где $r_{n}$ и будет НОД целых чисел $A$ и $B$ . Все ранее написанное и называется алгоритмом Евклида.

Другими словами, мы представляем деление $A$ на $B,$ как $A = Bq + r$ и пока остаток $r \neq 0$ мы делим делитель на остаток от деления. А так как остаток всегда меньше делителя двух целых чисел ( $r_{1} < B$ или $r_{n} < r_{n-1}$ ), то рано или поздно остаток будет равен нулю. А НОД двух чисел будет последний делитель.

Выполним те же действия, но на этот раз запишем деление в столбик.

Спойлер

НОД двух многочленов

Как и с большими целыми числами, алгоритм Евклида очень удобен для поиска НОД двух многочленов.

Теорема. Наибольший общий делитель двух многочленов существует.

Пусть даны два многочлена $f\left(x\right), g\left(x\right) \in P[x],$ где $\deg \left(f\left(x\right)\right) \geqslant \deg \left(g\left(x\right)\right)$ . Находим ряд равенств: $f\left(x\right) = g\left(x\right)q_1\left(x\right)+r_1\left(x\right)$ $g\left(x\right) = r_{1}\left(x\right)q_{2}\left(x\right)+r_{2}\left(x\right)$ $r_{1}\left(x\right) = r_{2}\left(x\right)q_{3}\left(x\right)+r_{3}\left(x\right)$ $……$ $r_{n-1}\left(x\right) = r_{n}\left(x\right)q_{n+1}\left(x\right)+0,$ где $r_{k}, q_{k} \in P[x]$ при $k = 1,2,3,…,n,$ где $r_{k}$ — остаток, а $q_{k}$ — частное. В случае с целыми числами, остатки в алгоритме убывают, при многочленах же убывают степени остатка ( $\deg \left(r_{n}\left(x\right)\right) < \deg \left(r_{n-1}\left(x\right)\right) < \deg \left(r_{n-2}\left(x\right)\right) < …$ ), это означает, что наступит момент деления без остатка. Поэтому НОД двух многочленов, по алгоритму Евклида, будет последний отличный от нуля остаток(в нашем случае $r_{n}$ ).

В доказательстве мы явно описали принцип работы алгоритма Евклида для нахождения НОД двух многочленов над одним полем.

Запишем тот же алгоритм делением в столбик.

Примеры решения задач

Решим пару простых задач, где используется алгоритм Евклида. Рекомендую решить задания самостоятельно, а потом смотреть решение.

Найти НОД $784$ и $552$ используя алгоритм Евклида.

Решение

Для лучшего понимания распишу два деления. Одно в столбик, другое — по определению. Деление в столбик: Деление по определению: $784 = 552 \times 1 + 232$ $552 = 232 \times 2 + 88$ $232 = 88 \times 2 + 56$ $88 = 56 \times 1 + 32$ $56 = 32 \times 1 + 24$ $32 = 24 \times 1 + 8$ $24 = 8 \times 3 + 0,$ где число $8$ — НОД $784$ и $552,$ так как это последний делитель.
Найти НОД $868$ и $923$ используя алгоритм Евклида.

Решение

Для лучшего понимания распишу два деления. Одно в столбик, другое — по определению. Деление в столбик: Деление по определению: $923 = 868 \times 1 + 55$ $868 = 55 \times 15 + 43$ $55 = 43 \times 1 + 12$ $43 = 12 \times 3 + 7$ $12 = 7 \times 1 + 5$ $12 = 7 \times 1 + 5$ $7 = 5 \times 1 + 2$ $5 = 2 \times 2 + 1$ $2 = 1 \times 2 + 0,$ где число $1$ — НОД $868$ и $923,$ так как это последний делитель.
Найти НОД $52800$ и $54108$ используя алгоритм Евклида.

Решение

Для лучшего понимания распишу два деления. Одно в столбик, другое — по определению. Деление в столбик: Деление по определению: $54108 = 52800 \times 1 + 1308$ $52800 = 1308 \times 480 + 480$ $1308 = 480 \times 2 + 348$ $480 = 348 \times 1 + 132$ $348 = 132 \times 2 + 84$ $132 = 84 \times 1 + 48$ $84 = 48 \times 1 + 36$ $48 = 36 \times 1 + 12$ $36 = 12 \times 3 + 0,$ где $12$ — НОД $52800$ и $54108$ .
Найти НОД $x^5-10x^3-20x^2-15x-4$ и $x^4-6x^2-8x-3$ используя алгоритм Евклида.

Решение

Для лучшего понимания распишу два деления. Одно в столбик, другое — по определению. Деление в столбик: Деление по определению: $x^5-10x^3-20x^2-15x-4 = x\left(x^4-6x^2-8x-3\right) — 4x^3-12x^2-12x-4$ $x^4-6x^2-8x-3 = \left(- 4x^3-12x^2-12x-4\right)\left(- \frac{x}{4}\right) — 3x^3-9x^2x-9x-3$ $- 4x^3-12x^2-12x-4 =\left(-3x^3-9x^2x^2-9x-3\right)\left(-\frac{4}{3}\right) + 0,$ где $3x^3-9x^2-9x-3$ — НОД многочленов $x^5-10x^3-20x^2-15x-4$ и $x^4-6x^2-8x-3,$ так как это последний делитель в алгоритме.

Проверка на освоение материала «Алгоритм Евклида».

Смотрите также

Конспект Г.С.Белозерова. Глава 3 — 15с. — С. 3-5.
Д.К. Фаддеев. Лекции по алгебре: Учебное пособие для вузов. — М.: Наука, 1984. — 416 с. — С. 7-11.
И.М. Виноградов. Основы теории чисел. — Москва, 1952. — 181 с. — С. 8-12.

М1689. Задача об арифметической прогрессии

Задача из журнала «Квант» (1999 год, 3 выпуск)

Условие

Арифметическая прогрессия из натуральных чисел содержит не менее трех членов, их произведение – делитель некоторого числа $n^2 + 1$ .

Докажите, что существует такая прогрессия с разностью $12$ .
Докажите, что такой прогрессии с разностью $10$ или $11$ не существует.
* Какое наибольшее число членов может содержать такая прогрессия с разностью $12$ ?

Решение

Рассмотрим числа $1$ , $13$ , $25$ ; для них $5^2 + 1 = 13\cdot2$ ,
$7^2 + 1 = 25 \cdot 2$ . Число $57^2 + 1$ делится на $13\cdot25$ : к этому легко придти непосредственно, а общий метод см. ниже.
Из трех чисел $а$ , $а + 10$ , $а + 20$ одно делится на $3$ , а $n^2 + 1$ на $3$ не делится.
Случай разности $11$ рассматривается аналогично.
Ни один из членов прогрессии не делится на $7$ , ибо на $7$ не делится $n^2 + 1$ . Значит, из семи членов прогрессии (если бы такая была) можно было бы выбрать два, разность которых делится на $7$ . Получили противоречие:
$k\cdot 12$ кратно $7$ (пишут: $k\cdot 12 \vdots 7$ ), где $0 < k < 7$ .

Докажем, что прогрессия из шести членов есть:

$\left(5, 17, 29, 41, 53, 65\right)$ .

Нам нужно доказать существование такого числа $n$ , что $n^2 + 1$ делится на
$\begin{equation}\label{eq:exp1}5\cdot17\cdot 29\cdot 41\cdot 53\cdot 65 = \left( 25\right) \cdot 17\cdot 29\cdot 41\cdot 53\cdot 13.\end{equation}$
Каждое из шести чисел в правой части $\eqref{eq:exp1}$ обладает
нужным свойством:

$\left(7 + 25x\right)^2 + 1 \vdots 25$ , $\left(4 + 17y\right)^2+ 1 \vdots 17$ ,

$\left(12 + 29z\right)^2 + 1 \vdots 29$ , $\left(9 + 41u\right)^2+ 1 \vdots 41$ ,

$\left(23 + 53v\right)^2 + 1 \vdots 53 \left( так \;как \;23^2 + 1 = 530\right),$

$\left(5 + 13w\right)^2+ 1 \vdots 13$ .

Теперь нам понадобится предложение, известное как «китайская теорема об остатках».

$a_1, \dotsc , a_m —$ натуральные числа, каждые
два из которых взаимно просты, $r_1, \dotsc , r_m —$ произвольные целые числа. Тогда существуют целые числа $x_1, \dotsc , x_m$ такие, что

$a_1x_1+r_1=\dotsc=a_mx_m+r_m$ .
При $m = 2$ теорема доказывается с помощью алгоритма Евклида, после чего ее утверждение распространяется на общий случай $m > 2$ по индукции.
Для окончания решения пункта в) достаточно применить теорему к системе уравнений $7 + 25x = 4 + 14y = \dotsc + 23+53v=5+13w$ .

Существуют ли более длинные арифметические прогрессии, удовлетворяющие всем условиям нашей задачи? На этот вопрос нетрудно ответить с помощью результатов статьи «Суммы квадратов и целые гауссовы числа» (см. «Квант» №3 за 1999 год).Именно, легко показать, что разность любой прогрессии задачи обязана делиться на $12$ . С другой стороны, выше мы показали, что разность любой такой прогрессии, содержащей не менее семи членов, должна делиться на $7$ .
Прогрессия задачи с разностью $12\cdot7 = 84$ существует: с помощью статьи «Суммы квадратов…» и китайской теоремы об остатках легко показать, что делителем некоторого числа $n^2 + 1$ является произведение всех членов
прогрессии $\left(29, 113, 197, 281, 365, 449, 533, 617, 701,785\right)$ .
Эта прогрессия содержит $10$ членов; $11$ же членов прогрессия задачи с разностью $84$ содержать не может: $84$ не делится на простое число $р = 4k + 3 = 11$ .

В.Сендеров

Примеры решения задач

Простейшие сведения о непрерывных дробях и их свойствах

Навигация (только номера заданий)

Информация

Результаты

Рубрики

1.

2.

3.

4.

5.

Элементы сортировки

6.

Смотрите также

Примеры решения задач

Навигация (только номера заданий)

Информация

Тест на проверку знаний по теме «НОД двух многочленов»

Результаты

Рубрики

1.

2.

3.

4.

Элементы сортировки

5.

НОД двух многочленов

Примеры решения задач

Навигация (только номера заданий)

Информация

Результаты

Рубрики

1.

2.

3.

Элементы сортировки

4.

5.

6.

Смотрите также

Условие

Решение