![](/user_photo/2706_HbeT2.jpg)
3 Тема
Знаходження НОД і НОК.
Пустьимеетсяnцелых чисел: а1,а2…аn. Общим кратным этих чисел называется целое число, которое делится нацело на каждое их этих чисел. Наименьшее из этих общих кратных называется наименьшим общим кратным чисел а1, а2,…аn и обозначается НОК(а1,а2,…,аn) или[a1,a2,…,an]
Пустьимеетсяnцелых чисел: а1,а2…аn. Общим делителем этих чисел называется число, которое нацело делит каждое из этих чисел. Среди делителей имеется наибольшее число, которое называется наибольшим общим делителем - НОД(а1,а2,…,аn) или(а1,а2,…,аn)
Прості числа. Алгоритм знаходження простих чисел.
Число, которое не имеетникакихделителей, кроме 1 и самого себя, называетсяпростым числом.
Любое число Nможет быть представлено в виде произведения степеней простых чисел(каноническое представление числа). Такое представление единственное. Так, число 600=233152
Для представления числа N в канонической форме можно использовать следующий алгоритм. Число N делим на наименьшее простое число 2 до тех пор, пока оно делится нацело, затем на 3, на 5 и т.д.
Функція Ейлера. Властивості.
Функція Эйлера ᵠ(m) определяется для всех целых чисел m как количество чисел ряда 1,2,3…,m. Так как ᵠ(1)=1(по определению), ᵠ(2)=1, ᵠ(3)=2, ᵠ(4)=2, ᵠ(5)=4 и т.д. Легко показать, что для m=p(простых чисел) ᵠ(p)=p-1. Для m=pn функция Эйлера ᵠ(pn)=pn-1(p-1). Для произвольного числа m, представленного в канонической форме m=p1n1,p2n2,…,psфункція Єйлераопределяетсяследующим образом:ᵠ(m) =m(1–1/p1)(1–1/p2)…(1–1/ps).
Например: ᵠ(11)=10; ᵠ(9)=6; ᵠ(18)=6.
Функція Мьобіуса. Формула зведення Мьобіуса.
Определение. ФункцияМёбиуса μ(n) определяется для всехцелыхположительных чисел иравна
μ(n)=
гдеn=p1^a1,p2^a2…pk^ak – разложение на простые сомножители, pi – простые числа, ai– кратность piв разложении. Пример. μ (1)=1, μ(2)=-1, μ(3)=-1, μ(4)=0, μ(5)=-1, μ(6)=1…
Порівняння. Властивості.
Пустьm — целоеположительное число, котороеназовем модулем. Будем говорить, чтоцелые числа а и bсравнимы по модулюm, если а - b = t • m для некоторогоцелого t, т.е. равны остатки отделенияa и b на m. Сравнение чисел а и b по модулю т будемзаписывать а ≡b (modm).
Например, 77 = 5(mod 8), 102 = 0(mod 3).
Свойствасравнений
1. а = a (modm) — свойстворефлексивности.
2. a s b (modm) => b = a (mod m) — свойствосимметричности.
3. а = b (modm), b = c (mod т) => а = с (mod т)— свойствотранзитивности.
4. а = b (modm) => (а, m) = (b, m).
5. а = b (modm), с = d (mod m)=>a + csb + d (mod m).
6. a = b (mod m), c = d (mod m) =>ac = bd (mod m).
7. a = a1d, b = b1d, (d, m) = 1, a = b (mod m) => a1 = b1 (mod m).
8. a = b (modm), m1\m(m1делитm) => a = b (mod m1).
9. a = b (mod m), d\a, d\b, d\m =>a1 = b1(mod m1).
Повна система вичетов.
Свойства 1—3 сравненийпоказывают, чтооперациясравненияцелых чисел по модулю являетсяотношениемэквивалентности.Множествовсехцелых чисел Zразбивается на классыэквивален-
тности,которыеназываютсявычетами по модулю m.Числа г, s є Z лeжaт в одномклассе {ki}, т.е. г, s e {ki} тогда и толькотогда, когда г = s (modm) имеютодинаковые остатки от деленияна m. Числа одного и того же классаимеют с модулем т один и тотже наибольшийобщийделитель, т.к. из г, s е {ki } следует, что(г,m ) = (s, m) .Особенноважныклассы, для которыхэтотделительравенединице, т.е. классы, содержащие числа, взаимнопростые с модулем.
Определение. Множество классов вычетов {0}, {1},..., {m - 1} по модулю m называется полной системой вычетов (п.с.в.). Полную систему вычетов можно получить следующим образом.
Пусть Z— аддитивная (операция сложения) группа целых чисел, mZ— подгруппа всех чисел, кратных m. Тогда факторгруппа Z/mZ— аддитивная группа вычетов по модулю т (полная система вычетов).
Приведена система вичетов.
Определение. Пустьm — целоеположительное число. Множествоклассовизполнойсистемывычетов {0}, {1},..., [m- 1} взаимнопростых с mназываетсяприведеннойсистемойвычетов,которуюбудемобозначатькакMzили Мz(m). Приведеннуюсистему вычетов, следовательно, можносоставитьиз чиселп.с.в., взаимнопростых с модулем. Обыкновенноz„ выделя-
ют изсистемынаименьшихнеотрицательныхвычетов: О, 1,2,..., m-1.
Цепні дроби. Визначення. Теорема Дирихле.
Определение.
Цепной (или, непрерывной) дробью
называется выражениевида:
Теорема
Дирихле: Пусть и
–
действительные числа; существует
несократимая дробь
,
для которой
,
(или:
существует такая пара взаимно простых
целых чисел a и b,
что ,
).
Доказательство: Теорему легко доказать с помощью аппарата цепных дробей.
Пусть
подходящая
дробь числа a
; выберем наибольший из знаменателей
,
не превышающий
,
то есть наибольшееk,
чтобы
и
положим
=
.
Рассмотрим два случая:
не
является последним знаменателем, то
есть существует
такое,
что . Тогда при
имеем:
2) –
знаменатель последней подходящей дроби
разложенияa,
то есть a
=
.
Тогда при
,
имеем:
.
Кінцеві цепні дроби. Приведений алгоритм Евкліда.
Пусть -
рациональное число, причемb>0.
Применяя к a и b алгоритм
Евклида для определения их наибольшего
общего делителя, получаем конечную
систему равенств:
где
неполным частным последовательных
делений соответствуют
остатки
с
условием b>
>
>…>
>0,
а соответствует остаток 0.
Системе равенств (1) соответствует равносильная система
из
которой последовательной заменой
каждой из дробей и
т.д. ее соответствующим выражением из
следующей строки получается представление
дроби
в
виде:
Такое
выражение называется правильной
(конечной) цепной или правильной
непрерывной дробью, при этом предполагается,
что –
целое число, а
,
…,
-
натуральные числа.
Дати визначення та описати призначення підходящих дробів.
Задаче
разложения обыкновенной дроби в
непрерывную дробь противостоит обратная
задача – обращения или свертывания
цепной дроби в
простую дробь
.
При этом основную роль играют дроби вида:
или
которые
называются подходящими дробями данной
непрерывной дроби или соответствующего
ей числа
.
Цепна дроб дійсного числа.
Пустьa1, a2,…an – бесконечная цепная дробь с целыми неполными частями an>=1, n>=1, тогда справедливо следующее:
Последовательность подходящих дробей с четными номерами возрастает, а с нечетными – убывает, при этом любая подходящая дробь нечетного порядка больше любой подходящей дроби четного порядка;
Если цепная дробь бесконечна, то существует
α-иррациональное число.
Справедливо равенство
Число α будем называть значением бесконечной цепной дроби. Соответствующие подходящие дроби будем также называть подходящими дробями числа α.
Цепні дроби ірраціональних чисел.залишки цепних дробів.
Рассмотрим
пример разложения иррационального
числа .Пусть
.
Выделим из
его
целую часть.
=3,
а дробную часть
–3,
которая меньше представим в виде
,
где
.Повторяя
операцию выделения целой части и
перевертывания дробной, мы
получаем:
;
;
.Если
остановиться на этом шаге, то можно
записать:
С
другой стороны, из формулы для
видно,
что
=3+
.
Поэтому
,
вследствие чего, начиная с этого момента,
неполные частные станут повторяться.
Бесконечная непрерывная дробь, в которой определенная последовательность неполных частных, начиная с некоторого места, периодически повторяется, называетсяпериодической непрерывной дробью.
Если, в частности, периодическое повторение начинается с первого звена, то цепная дробь называется чисто периодической, в противном случае – смешанной периодической.
Найкращі приближення. Визначення та використання.
Наилучшим приближеним к числу α определяетсякакнаилучшеесреди приближений с заданымограничением знамена теля.
О.
Рациональнаядробьназывается
наилучшим приближением к числу α, если
для любой другой дроби
условие,
что
знаменатель не больше исходной и
выполняется
Всякое
наилучшее приближение к α это подходящая
дробь к нему. Всякая подходящая дробь
это
наилучшее приближение к этому числу.
Т.
Если несократимая дробь
удовлетворяет
, то она является наилучшим приближением
к числу α , и является одной из поддходящих
дробей.
Цепні дроби та поняття еквівалентності чисел.
На множестведействительніх чисел можно ввести отношениеэквивалентности для действительніх чисел.
α И β назовемэквивалентными, еслинайдутсяцелыеa,b,c,d числа такие, чтобудетсоблюдатся:
, гдеad-bc=+-1,
такое отношение обозначается α˜β=>β˜α,
при этом α˜α
если
α˜β, а β˜ᵠ,
то α˜ᵠ.
Из этих свойств следует, что м-во всех действительных чисел распадается на классы чмсел эквивалентных между собой.
Т. Действительные числа α и β эквивалентны тогда и только тогда, когда их разложение в непрерывные дроби, начиная с некоторого места совпадают.
Принципи розкладання дійсного числа в неперервну цепну дроб
Теорема. Всякое действительное число может быть разложено в цепную дробь единственным образом, и всякая конечная или бесконечная цепная дробь имеет своим значением некоторое действительное число.
Пусть
-
действительное число, заключенное
между двумя последовательными целыми
числами:а<a<а+1.
Число а
будем
называть нижним целым числаa(это просто
целая часть a), а число а+1
- верхним целым. Обозначениями для
нижнего и верхнего целого числа a пусть
будут, соответственно
Возьмем произвольное действительное число a eR,q1 = а – нижнее целое. Тогда a=q1+b1 , 0<=b1 < 1, следовательно
Если, далее,a1 - не целое, то снова:
Продолжая этот процесс взятия нижних целых и переворачивания дробных частей, получим запись произвольного числа a eR в виде цепной дроби. Изложенный процесс есть просто "лобовой" способ разложения произвольного числа в цепную дробь или, если угодно, наводящие соображения к доказательству основной теоремы.
Зв’язок цепних дробів та послідовностей багаточленів.
Несократимі дроби та їїх найкращі приближення.
Теорема про еквівалентність дійсних чисел.
На множестведействительніх чисел можно ввести отношениеэквивалентности для действительніх чисел.
α И β назовемэквивалентными, еслинайдутсяцелыеa,b,c,d числа такие, чтобудетсоблюдатся:
, гдеad-bc=+-1,
такое отношение обозначается α˜β=>β˜α,
при этом α˜α
если
α˜β, а β˜ᵠ,
то α˜ᵠ.
Из этих свойств следует, что м-во всех действительных чисел распадается на классы чмсел эквивалентных между собой.
Т. Действительные числа α и β эквивалентны тогда и только тогда, когда их разложение в непрерывные дроби, начиная с некоторого места совпадают.
Ірраціональні числа та несократимі дроби.
Зв’язок найкращих наближень та підходящих дробів.
Всякое наилучшее
приближение к α это подходящая дробь
к нему. Всякая подходящая дробь
это
наилучшее приближение к этому числу.
Т.
Если несократимая дробь
удовлетворяет
, то она является наилучшим приближением
к числу α , и является одной из поддходящих
дробей.