Очень интересными с математической (и не только) точки зрения считаются простые числа. Для начала сформулируем несколько определений для дальнейшей работы.
Определение. Простое число — это натуральное число больше единицы и которое делится нацело только на единицу и на само себя. Таким образом, $p$ считается простым, если $$p \in N, p > 1, \forall a \in N, a \neq 1, a \neq p, p \mbox{ mod } a \neq 0 .$$
Определение. Натуральное число не являющиеся простым и больше $1$ называется составным.
Примеры
$3, 5, 7, 23$ — простые числа, что можно с легкостью проверить мысленно перебрав возможные делители для этих чисел. $177539$ — тоже простое число, однако проверить это устным перебором делителей будет значительно сложнее.
Любое четное число кроме $2$ — составное, так как имеет как минимум один делитель помимо $1$ и самого себя — $2$.
Леммы
Сформулируем и докажем несколько лемм. Далее, если это потребуется, будем упоминать их как лемму и её номер в списке. Лемма (2), к примеру.
Лемма. Пусть $p$ и является наименьшим делителем (не считая $1$) $ n \in N, n > 1$. Тогда $p$ — простое число.
Спойлер
Докажем от обратного. Предположим что $p$, наименьший делитель для $n$ из условия, составное число. В таком случае, его можно представить как $p=p_{1}p_{2}$. Отсюда $n=pb$ можно представить как $n=p_{1}p_{2}b$, где $p_{1}, p_{2} < p$. Если $n \vdots p$, то оно делится и на $p_{1}, p_{2}$. А так как они оба меньше $p$, то $p$ не может быть наименьшим делителем $n$. Таким образом, составное число не может быть наименьшим делителем числа, так как его всегда можно разложить на множители, которые в свою очередь тоже будут делителями $n$.
[свернуть]
Лемма. Пусть $p$ — наименьший (не считая $1$) натуральный делитель составного числа $n$. Тогда $p\leqslant \sqrt{n}$.
Спойлер
Пусть, по условию леммы, $p$ — наименьший отличный от нуля делитель $n$. Тогда $n = pb$, где $b\in N$ и $b\mid n$. Очевидно, что в таком случае $p \leqslant b < n$ и отсюда $p^{2} \leqslant n$, что доказывает неравенство данное в условии.
[свернуть]
Решето Эратосфена
Алгоритм. Способ нахождения простых чисел до определенного $n$. Метод подразумевает фильтрацию чисел до $n$, отсеивая составные числа. Является псевдополиномиальным алгоритмом. Алгоритм заключается в следующем:
Требуется выписать все числа от $2$ до $n$.
Изначально $p=2$.
Далее вычеркнем все числа представимые в виде $2p, 3p, 4p, \ldots$ до $n$.
Присвоим $p$ следующее не вычеркнутое число. Будем повторять $3$ и $4$ шаги до тех пор, пока $p \leqslant \sqrt{n}$ (по лемме (2)).
Таким образом, все составные числа будут вычеркнуты и останутся только простые.
Замечание
Если внимательно взглянуть на алгоритм, можно заметить что мы начинаем вычеркивать с $p^{2}$. Пусть $k \in N, k > 1$ и $k$ очередное простое (а значит не вычеркнутое) число в списке. А значит, что перед тем как $p=k$, мы вычеркнули (при условии что $k>2$) $2k$, ведь на первом шаге мы вычеркнули все делящиеся на $2$ числа. Если $k>3$, то и все делящиеся на $3$ числа были уже вычеркнуты. То есть $3k$ уже вычеркнуто. Таким образом, все составные числа имеющие нетривиальные делители до $k(k-1)$ включительно уже вычеркнуты, поэтому искать число чтобы вычеркнуть стоит начиная от $p^{2}$. Подробнее с модфикациями алгоритма можно ознакомится на википедии и e-max.
Пример
Найдем все простые числа до $20$ с помощью решета Эратосфена. Для начала выпишем все числа. $$2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20$$
Положим $p=2$ и уберем все числа от $p^{2}$ до $20$. Останется $$2,3,\phantom{4,} 5,\phantom{6,} 7,\phantom{8,} 9,\phantom{10,} 11, \phantom{12,} 13,\phantom{14,} 15,\phantom{16,} 17,\phantom{18,} 19 \phantom{,20}$$
Далее $p=3$, и мы снова убираем ненужные нам числа. $$2,3,\phantom{4,} 5,\phantom{6,} 7,\phantom{8,} \phantom{9,10,} 11, \phantom{12,} 13,\phantom{14, 15, 16,} 17,\phantom{18,} 19 \phantom{,20}$$
Брать следующее $p$ не смысла, так как это будет $5$, а $5^{2}>20$. Таким образом мы нашли все простые числа до $20$.
Тест на простые числа и решето Эратосфена
Лимит времени: 0
Навигация (только номера заданий)
0 из 5 заданий окончено
Вопросы:
1
2
3
4
5
Информация
У вас есть возможность проверить то, как вы усвоили материал.
Вы уже проходили тест ранее. Вы не можете запустить его снова.
Тест загружается...
Вы должны войти или зарегистрироваться для того, чтобы начать тест.
Вы должны закончить следующие тесты, чтобы начать этот:
Результаты
Правильных ответов: 0 из 5
Время вышло
Вы набрали 0 из 0 баллов (0)
Средний результат
Ваш результат
Рубрики
Алгебра0%
1
2
3
4
5
С ответом
С отметкой о просмотре
Задание 1 из 5
1.
Введите количество простых чисел до 50.
Правильно
Неправильно
Подсказка
Используйте решето Эратосфена.
Задание 2 из 5
2.
Выберите все простые числа.
Правильно 6 / 6Баллы
Неправильно / 6 Баллы
Задание 3 из 5
3.
Выстройте правильный алгоритм решета Эратосфена.
Выписать все числа от $2$ до $n$. Повторять следующие шаги пока $p \leqslant \sqrt{n}$.
Пусть $p$ равно первому не вычеркнутому и не использованному ранее числу.
Вычеркнуть все числа которые делятся на $p$ кроме самого $p$.
Правильно
Неправильно
Задание 4 из 5
4.
Выберите верное утверждение. Если $p$ наименьший делитель (не считая $1$) числа $n$, то:
Правильно
Неправильно
Задание 5 из 5
5.
Впишите пропущенные слова.
(Составное) число - имеет больше двух делителей.
Если $p$ - наименьший делитель $n$ (не считая $1$), то это (простое) число.
Один из способов нахождения всех простых чисел до $n$ является решето (Эратосфена, Аткина).
Правильно 4 / 4Баллы
Неправильно / 4 Баллы
Литература
Электронный конспект по алгебре. Автор Белозеров.Г.С.
Теорема Кронекера-Капелли. Критерий совместности системы линейных алгебраических уравнений. СЛАУ совместна тогда и только тогда, когда ранг матрицы системы равен рангу расширенной матрицы. То есть, если в СЛАУ $r=\operatorname{rang}A=\operatorname{rang}\widetilde{A}$, где $\operatorname{rang}A$ — обозначает ранг матрицы системы, а $\operatorname{rang}\widetilde{A}$ — ранг расширенной матрицы, тогда данная матрица совместна, причём система имеет единственное решение, если $\operatorname{rang}A=\operatorname{rang}\widetilde{A}=n$, где $n$ — число неизвестных, и бесконечное число решений, если $\operatorname{rang}A=\operatorname{rang}\widetilde{A}<n$.
Скажем, что данная система совместна, в таком случае существуют числа $\left(c_{1},c_{2},\dots,c_{n}\right)$, которые являются частным решением матрицы, при подстановке их в систему. Мы получим равенство:
Следовательно, вектор-столбец свободных членов является линейной комбинацией столбцов $\left(a_{1},a_{2},\dots,a_{n}\right),$ матрицы $A.$ Так же, мы можем заметить, что сколько бы мы раз не приписали или не вычеркнули строку(столбец), от этого не меняется ранг системы, из этого следует, что $\operatorname{rang}A=\operatorname{rang}\widetilde{A}$.
Достаточность. Если $\operatorname{rang}A=\operatorname{rang}\widetilde{A}$, то это означает, что у них один и тот же базисный минор. Тогда, согласно теореме о базисном миноре, последний столбец свободных членов – линейная комбинация столбцов базисного минора.
При $\lambda\neq0$: $\operatorname{rang}\widetilde{A}=3$, $\operatorname{rang}A=2$. По теореме Кронекера-Капелли система линейных уравнений несовместна.
При $\lambda=0$: $\operatorname{rang}\widetilde{A}=2$, $\operatorname{rang}A=2$. По теореме Кронекера-Капелли система линейных уравнений совместна.
Критерий совместности СЛАУ Кронекера-Капелли
Лимит времени: 0
Навигация (только номера заданий)
0 из 4 заданий окончено
Вопросы:
1
2
3
4
Информация
Тест на закрепление материала «Критерий совместности СЛАУ Кронекера-Капелли».
Вы уже проходили тест ранее. Вы не можете запустить его снова.
Тест загружается...
Вы должны войти или зарегистрироваться для того, чтобы начать тест.
Вы должны закончить следующие тесты, чтобы начать этот:
Результаты
Правильных ответов: 0 из 4
Ваше время:
Время вышло
Вы набрали 0 из 0 баллов (0)
Средний результат
Ваш результат
Рубрики
Нет рубрики0%
1
2
3
4
С ответом
С отметкой о просмотре
Задание 1 из 4
1.
матрица совместима, если…
Задание 2 из 4
2.
Впишите пропущенные слова.
Система имеет единственное решение, если ранг (равен) числу неизвестных, и бесконечное число решений, если ранг (меньше) числа неизвестных.
Определение. Ортонормированный базис (ОНБ) — это базисная система векторов, которая ортогональна и нормирована.
Определение. Ортогональная система векторов — это система состоящая либо из только одного ненулевого вектора, либо из нескольких ненулевых векторов, которые попарно ортогональны.
Определение. Любой вектор евклидова пространства, скалярный квадрат которого равен единице, называется нормированным. Причем любой ненулевой вектор можно нормировать. Если вектор $a_{1} = \mu a,$ при $\mu = \left(a, a\right)^{-\frac{1}{2}},$ становится нормированным.
Определение. Система называется нормированной, если каждый вектор этой системы нормирован.
Теорема. (существование ОНБ в евклидовом пространстве) В любом конечномерном евклидовом пространстве можно найти ортонормированный базис.
Допустим, имеется система $S = \langle e_{1},e_{2},…,e_{n}\rangle$ в евклидовом пространстве $\forall e \neq 0.$ Если мы возьмем произвольный вектор $a$ из $E$ и если бы ортонормированная система $S = \langle e_{1},e_{2},…,e_{n}\rangle$ была бы базисом, то вектор $a$ совпадал бы с вектором $b$. Тогда рассмотрим вектор $a-b$ при $$b = \left(a, e_{1}\right)e_{1} + \left(a, e_{2}\right)e_{2} + … + \left(a, e_{n}\right)e_{n}.$$ Тогда вектор $a-b:$ $$\left(a-b, e_{k}\right) = \left(a-\sum\limits_{i = 1}^{n}\left(a, e_{i}\right)e_{i}, e_{k}\right) = \left(a, e_{k}\right)-\sum\limits_{i = 1}^{n}\left(a, e_{i}\right)\left(e_{i}, e_{k}\right) =$$ $$=\left(a, e_{k}\right)-\left(a, e_{k}\right) = 0.$$ То есть вектор $a-b$ ортогонален ко всем векторам системы $S = \langle e_{1},e_{2},…,e_{n}\rangle.$ Причем мы еще и доказали, что $$a-b = 0 \Rightarrow a = b.$$ Значит ЛНЗ система $S = \langle e_{1},e_{2},…,e_{n}\rangle$ образует базис в евклидовом пространстве, т. к. векторы $S$ линейно выражают векторы $E.$ Таким образом, в любом конечномерном евклидовом пространстве мы можем найти ортонормированный базис, причем ортогонализировать его векторы можно процессом ортогонализации Грама-Шмидта, а нормировать по определению выше.
Смотрите также
Личный конспект на основе лекций Белозерова Г.С. Евклидовы пространства
Тест на знание темы «Существование ортонормированного базиса»
Вы уже проходили тест ранее. Вы не можете запустить его снова.
Тест загружается...
Вы должны войти или зарегистрироваться для того, чтобы начать тест.
Вы должны закончить следующие тесты, чтобы начать этот:
Результаты
Правильных ответов: 0 из 5
Ваше время:
Время вышло
Вы набрали 0 из 0 баллов (0)
Средний результат
Ваш результат
Рубрики
Алгебра0%
максимум из 66 баллов
Место
Имя
Записано
Баллы
Результат
Таблица загружается
Нет данных
Ваш результат был записан в таблицу лидеров
Загрузка
1
2
3
4
5
С ответом
С отметкой о просмотре
Задание 1 из 5
1.
Количество баллов: 3
Рубрика: Алгебра
В любом ли конечномерном евклидовом пространстве $\exists$ ортонормированный базис?
Правильно
Неправильно
Задание 2 из 5
2.
Количество баллов: 16
Рубрика: Алгебра
Определение нормирования.
(любой, каждый, все, Любой, Каждый, Все) вектор (евклидова, Евклидова) пространства, скалярный квадрат которого равен (единице, 1, одному, единичке, Единице, Одному, Единичке), называется нормированным. Причем любой (не нулевой) вектор можно нормировать.
Правильно
Неправильно
Задание 3 из 5
3.
Количество баллов: 12
Рубрика: Алгебра
Какая система может образовать базис в евклидовом пространстве?
Правильно
Неправильно
Задание 4 из 5
4.
Количество баллов: 20
Рубрика: Алгебра
Сопоставьте части предложений.
Элементы сортировки
вектор, скалярный квадрат которого равен единице.
система, в которой скалярный квадрат каждого вектора равен единице.
наличие в системе одного не нулевого вектора или векторов, которые попарно ортогональны.
базисная система которая ортогональна и нормирована.
Определение. Если наблюдатель, идя против часовой стрелке сначала встречает вектор $\vec {c},$ затем встречает вектор $\vec {a},$ затем вектор $\vec {b},$ то тройка векторов $\left\{\vec {a}, \vec {b}, \vec {c}\right\}$ называется правой (рис. 1), если же наблюдатель шел по часовой стрелке и встретил вектора в той же последовательности, то тогда тройка векторов $\left\{\vec {a}, \vec {b}, \vec {c}\right\}$ называется левой.
Определение с использованием руки (мнемоническое правило). Если обозначить указательный палец как $\vec {a},$ средний палец как $\vec {b},$ а большой палец как их произведение, т.е. $\vec {c},$ то расположение пальцев на правой руке является правой тройкой векторов, а на левой руке левой тройкой векторов.
На рисунке 1 показано как будет выглядеть правая тройка векторов.
Определение. Векторным произведением неколлинеарных векторов $\vec {a}$ и $\vec {b}$ называется вектор $\vec {c},$ такой, что
$\left|\vec {c}\right| = \left|\vec {a}\right| \cdot \left|\vec {b}\right| \cdot \sin \varphi,$ где $\varphi$ — угол между векторами $\vec {a}$ и $\vec {b};$
Смотря на определение видно, что произведения $\vec {a} \times \vec {b}$ и $\vec {b} \times \vec {a}$ имеют одинаковую длину. Так же они имеют противоположное направление из-за того, что $\sin \varphi$ нечетен.
Для того, чтобы два ненулевых вектора были коллинеарны, необходимо и достаточно, чтобы их векторное произведение равнялось нулевому вектору. $$\vec{a} \| \vec{b}, \quad \left| \vec{a}\right| \neq 0, \quad \left|\vec{b}\right| \neq 0 \Longleftrightarrow \vec{a} \times \vec{b} = \vec{0}.$$
Необходимость. Очевидно, что если вектора $\vec {a}$ и $\vec {b}$ коллинеарны, то синус угла между ними равен нулю, отсюда видим, что по определению, векторное произведение равно нулю. Достаточность. Теперь докажем в обратную сторону: если $\vec{a} \times \vec{b} = \vec{0},$ то $\left|\vec{a}\right| \cdot \left|\vec{b}\right| \cdot \sin \left(\vec{a}; \vec{b}\right) = 0 \Rightarrow$ один из сомножителей равен нулю. Так как ни один из векторов не равен нулю, то $\sin \left(\vec{a}; \vec{b}\right) = 0,$ т.е. либо $\widehat {\left(\vec{a}; \vec{b}\right)} = 0,$ либо $\widehat {\left(\vec{a}; \vec{b}\right)} = \pi$ и значит $\vec{a} \| \vec{b}.$
Модуль векторного произведения равен площади параллелограмма построенного на перемножаемых векторах (рис. 2).
Если посмотреть векторного произведения $\left|\vec{a} \times \vec{b}\right| = \left|\vec{a}\right| \cdot \left|\vec{b}\right| \cdot \sin \left(\vec{a}; \vec{b}\right),$ то мы видим общеизвестную формулу площади параллелограмма со сторонами, длины которых равны $\left|\vec {a}\right|$ и $\left|\vec {b}\right|.$
Координатное представление векторного произведения
Найти модуль векторного произведения векторов $\vec {a} = \left(0, 3, 4\right)$ и $\vec {b} = \left(5, 12, 0\right), \, \varphi = \frac{\pi}{3}.$
Решение
Для того, чтобы использовать формулу вычисления модуля векторного произведения $|\vec {c}| = |\vec {a}| |\vec {b}| \sin \varphi$ надо знать длины наших векторов, для этого воспользуемся формулой $|\vec {f}| = \sqrt{\left(f_{x}\right)^2 + \left(f_{y}\right)^2 + \left(f_{z}\right)^2}.$ Тогда $|\vec {a}| = \sqrt{0 + 9 + 16} = 5$ и $|\vec {b}| = \sqrt{25 + 144 + 0} = 13.$ Тогда $\left|\vec {c}\right| = 5 \cdot 13 \cdot \sin \left(\frac {\pi}{3}\right) = 80 \cdot \frac {\sqrt{3}}{2} = 40\sqrt {3}.$ Ответ: $40\sqrt {3}.$
[свернуть]
Найти координаты вектора $\vec {c},$ который является результатом векторного произведения векторов $\vec {a} = \left(1, -2, 3\right)$ и $\vec {b} = \left(3, 4, 6\right).$
Найти площадь треугольника, у которого заданы координаты его вершин. $A = (1, 2, 3), B = (5, 11 -2), C = (3, -6, 4).$
Решение
Чтобы решить эту задачу достаточно найти площадь параллелограмма, построенного на каких-то двух сторонах треугольника. Пусть этими сторонами будут $AB$ и $AC.$ Для начала надо найти координаты этих векторов $\vec {AB} = (5 — 1, 11 — 2, -2 — 3) = (4, 9, 5), \vec {AC} = (3 — 1, -6 — 2,4 — 3) =$ $= \, (2, -8, -1).$ Найдем координаты вектора, полученного в результате векторного умножения сторон треугольника $$\vec {a} = \left|
\begin{matrix}
\vec{i} & \vec{j} & \vec{k} \\
4 & 9 & 5 \\
2 & -8 & -1
\end{matrix}
\right| = \vec {i} \cdot \left|
\begin {matrix}
9 & 5 \\
-8 & -1
\end {matrix}
\right| — \vec {j} \cdot \left|
\begin {matrix}
4 & 5 \\
2 & -1
\end {matrix}
\right| +$$ $$+ \, \vec {k} \cdot \left|
\begin {matrix}
4 & 9 \\
-8 & -1
\end {matrix}
\right| = 31 \cdot \vec {i} \, — \, (-14) \cdot \vec {j} + 68 \cdot \vec {k} = 31 \cdot \vec {i} + 14 \cdot \vec {j} + 68 \cdot \vec {k}.$$ Как мы уже знаем, координатами вектора $\vec {a}$ будет $(31, 14, 68).$ Осталось найти модуль полученного вектора по уже известной формуле $\left|\vec {a}\right| = \sqrt {961 + 196 + 4624} = \sqrt {5781}$ и поделить его на $2, S = \frac {\sqrt {5781}}{2}.$
[свернуть]
Найти площадь параллелограмма, построенного на векторах $\vec {a} = (1, -3, 4), \vec {AB},$ если $A = (3, 8 ,6), B = (2, 4, -7)$ и угол между ними равен $\varphi = \frac {\pi}{6}.$
Решение
Для начала надо найти вектор $\vec {AB} = (2 — 3, 4 — 8, -7 — 6) =$ $= \, (-1, -4, -13)$ и его модуль $\left|\vec {AB} \right| = \sqrt {1 + 16 + 169} = \sqrt {186}.$ Так же надо найти модуль вектора $\left|\vec {a}\right| = \sqrt {1 + 9 + 16} = \sqrt {26}.$ Теперь воспользуемся определением $\vec {a} \times \vec {AB} = \sqrt {186} \cdot \sqrt {26} \cdot \sin \frac {\pi}{6} = \sqrt {4836} \cdot \frac {1}{2}.$ На данном этапе можем внести $\frac {1}{2}$ под корень и тогда ответом будет $\sqrt {1209}.$
Тройка некомпланарных векторов, называется ______, если идя против часовой стрелки, начиная с $\vec{c}$, наблюдатель сначала видит $\vec {b}$, затем $\vec {a}.$
Пусть число $\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}. $$ Докажем это с помощью математической индукции.
Лемма. При $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}$ в непрерывную дробь. Решение
Найти все подходящие дроби числа $\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}$$
Простейшие сведения о непрерывных дробях и их свойствах
Лимит времени: 0
Навигация (только номера заданий)
0 из 6 заданий окончено
Вопросы:
1
2
3
4
5
6
Информация
Тест на знание темы «Простейшие сведения о непрерывных дробях и их свойствах».
Вы уже проходили тест ранее. Вы не можете запустить его снова.
Тест загружается...
Вы должны войти или зарегистрироваться для того, чтобы начать тест.
Вы должны закончить следующие тесты, чтобы начать этот:
Результаты
Правильных ответов: 0 из 6
Ваше время:
Время вышло
Вы набрали 0 из 0 баллов (0)
Рубрики
Нет рубрики0%
1
2
3
4
5
6
С ответом
С отметкой о просмотре
Задание 1 из 6
1.
Какая из данных непрерывных дробей имеет ровно $3$ неполных частных?
Правильно
Неправильно
Задание 2 из 6
2.
Выберите все дроби, которые являются подходящими для $\displaystyle x = \frac{227}{53}$
Правильно
Неправильно
Задание 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.
Сопоставьте иррациональные числа с количеством чисел, которые образуют цикл при представлении данных иррациональных числе в виде непрерывных дробей.
Элементы сортировки
2
1
5
4
$\sqrt{12}$
$\sqrt{17}$
$\sqrt{29}$
$\sqrt{34}$
Правильно
Неправильно
Задание 6 из 6
6.
Заполните пропуски
Если число (рациональное), то количество его неполных частных будет числом конечным, а если (иррациональное), то бесконечным.