НОД целых чисел . Алгоритм Евклида .

НОД целых чисел . Алгоритм Евклида .

Если некоторое целое число d является делителем одновременно для каждого из двух заданных чисел a и b, то d называется их общим делителем . Среди всех общих делителей двух заданных целых чисел a и b выберем максимальный. Он называется наибольшим общим делителем этих чисел и обозначается НОД(a, b).

Алгоритм Евклида: пусть a и b - целые числа, не равные нулю. Тогда последовательность чисел a>b>r₁>...>r_n определена тем, что каждое r_k - это остаток от деления предпредыдущего на предыдущее число, а предпоследнее делится на последнее нацело. Последний не нулевой член этой последовательности - НОД.

Теорема. Для любых целых чисел a и b, не равных нулю, алг . Евк . останавливается за конечное число шагов и корректно вычисляет НОД {a, b}.

Док-во: 1) По свойству операции деления с остатком (остаток не меньше нуля и строго меньше модуля делителя) имеем: |b| < r1 < r2 < r3 < . . . ≤ 0 - ч. и т.д.

2) См. алгоритм. r_s-1:d (1). q_s :d и r_s :d => r_{s- 2} :d (2) . Из (1) и (2) : r_s-3:d и т.д. В конце получаем: r₂ :d, r₁:d, b:d, a:d. d - общий делитель. Тогда пусть δ - произвольный общий делитель. Докажем, что если d делится на δ, т.е. на любой общий делитель, то он больший.

b:δ , a:δ = > r₁=a-q₁b:δ, r₂=b-q₂r₁:δ, ...,  r_s=r_s-2-q_sr_s-1:δ ч. и т.д.

Расширенный алгоритм Евклида. Коэффициенты Безу (линейное разложение НОД)

Теорема о линейном разложении НОД: Пусть a, b — целые числа, одновременно не равные нулю, и d= НОД(a, b). Тогда найдутся такие целые u, v, что ua + vb = d.

Числа u и v называются коэффициентами Безу.

Док-во: Применим к a и b алгоритм Евклида. В ходе его работы получим последовательности частных q1, q2, . . . , qs+1 и остатков r1, r2, . . . , rs. На первой итерации запишем два тривиальных равенства: a = 1 ·a + 0·b, b = 0·a + 1·b. Вычтем из первого второе, умноженное на q1. Тогда согласно в левой части получим r1 (из алг. Евклида). В правой части соберем множители у a и у b: r1 = 1·a + (−q1)·b. На второй итерации вычтем из равенства 2 равенство 3, умноженное на q2. Согласно алг. в левой части получим r2. В правой части снова соберем множители у a и у b: r2 = (−q2)·a + (1 + q1q2)·b.

На третьей итерации получим r3 = (1 + q2q3)·a + (−q1 − q3 − q1q2q3)·b. Будем выполнять такие преобразования далее. На k-й итерации (k = 1, 2, . . . , s) получим: r_k = u_ka + v_kb. На s-й итерации получим: d = r_s = u_sa + v_sb. Ч. и т.д..

Алгоритм нахождения коэффициентов Безу, описанный при док-ве теоремы - расширенный алгоритм Евклида.

Бинарная алгебраическая операция. Ассоциативность. Коммутативность. Полугруппа. Примеры полугрупп. Нейтральный элемент в полугруппе. Симметричные элементы в полугруппе.

Пусть A — непустое множество. Правило, которое каждой упорядоченной паре элементов из A ставит в соответствие элемент из A, называется бинарной алгебраической операцией на множестве A (или над A). Или

Ассоциативность: для a, b, c из A

Коммутативность: для a, b из A

Нейтральный: Симметричный:

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

Примеры коммутативных полугрупп: 1) N+ и Z+; 2) N* и Z *; 3) Z⁻ (множество отрицательных целых чисел) +

Полугруппами не являются: N- (не б. алг. оп.), N /(не б. алг. оп.), Z - (отсутствие ассоциативности), Z /(не б. алг. оп.).

Утв.: Если полугруппа обладает нейтральным элементом, то он единственный.

Док-во: Пусть e1 и e2 — нейтральные элементы в M. Тогда

т. е. e₁ = e₂.

Утв.: Пусть полугруппа содержит нейтральный элемент e. Если элементa имеет симметричный элемент a′, то других симметричных элементов у a нет.

Док-во: Пусть a′ и a′′ — симметричные элементы к a. Имеем

т. е. a′ = a′′.

Группа. Примеры групп. Обратные элементы в группе.

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

Согласно утверждениям в вопросе 10, нейтральный элемент группы единственен и для любого элемента группы симметричный элемент единственен.

Если групповая операция называется сложением (+), то группа называется аддитивной. В этом случае нейтральный элемент называют нулем (или нулевым эл-м) и обозначают 0. Элемент b, симметричный к a - противоположный ( −a). Если групповая операция называется умножением (× или ·), то группа называется мультипликативной. В этом случае нейтральный элемент называют единицей (или единичным эл-м) и обозначают e или 1. Элемент b, симметричный к a, называют обратным и обозначают a⁻¹.

Примеры абелевых групп: 1) Z, Q, R, C +, причем Z; 2) Q^∗, R^∗, C^∗× , где через F^∗ обозначено множество ненулевых элементов в F; 3) множество U_n (всех значений корня n-й степени из 1) ×; 5) V2, V3 +; 6) множество Z_n классов вычетов по модулю n относительно +

Утв.: Пусть a, b — некоторые элементы из группы G. Тогда каждое из уравнений ax = b, ya = b имеет, причем единственное, решение в G: x = a⁻¹b, y = ba⁻¹.

Док-во: Проверим, что x = a⁻¹b является решением уравнения ax = b: ax = a(a⁻¹b) = (aa⁻¹)b = eb = b. Для доказательства единственности решения, предположим, что нашлось два решения: x и x′. Тогда ax = b, ax′ = b, откуда ax = ax′.

Умножая слева обе части этого тождества на a⁻¹, получаем

a⁻¹(ax) = a⁻¹(ax′), пользуясь ассоциативностью, получаем

(a⁻¹a)x = (a⁻¹a)x′, откуда ex = ex′, т. е. x = x′. Используя аналогичные рассуждения, легко проверить, что единственным решением уравнения ya = b является y=ba−1.

Кольцо. Примеры колец. Мультипликативное свойство нуля. Правило знаков при умножении. Дистрибутивность при вычитании. Лемма о сокращении.

Кольцом называется непустое множество K, на котором заданы две бинарные алгебраические операции, называемые сложением и умножением, причем относительно сложения K является абелевой группой (аддитивная группа кольца) и операции связаны законами дистрибутивности, т. е. для любых a, b, c из K 1) (a + b)c = ac + bc; 2) a(b + c) = ab + ac.

 

Примеры колец: 1) Числовые кольца Z, Q, R, C + и * -ассоц. и коммут. с единицей. Кольца Q, R, C являются полями. Множество N кольцом не является. 2) Кольцо nZ целых чисел, кратных заданному числу n, + и *. Оно ассоц. и коммут., при n ≥ 2 - без единицы. 3) Кольцо Zn вычетов по модулю n -  коммут. и ассоц., обладает единицей.

Утв.: Мультипликативные свойства нуля. Для любых элементов a, b, c кольца K верно a0 = 0a = 0.

Док-во: Имеем aa + a0 = a(a + 0) = aa, откуда получаем, что

a0 = aa − aa = 0. Аналогично показывается, что 0a = 0.

Утв.: « Правило знаков » при умножении. Для любых элементов a, b, c кольца K верно (−a)b = a(−b) = −(ab); (−a)(−b) = ab.

Док-во: Докажем, например, что (−a)b = −(ab). Остальные свойства доказываются аналогично. Имеем ab + (−a)b = (a−a)b = 0b = 0, т. е. (−a)b противоположен элементу ab.

Утв.: Дистрибутивность при вычитании. Для любых элементов a, b, c кольца K верно (a−b)c = ac−bc; a(b−c) = ab−ac.

Док-во: Имеем (a − b)c = (a + (−b))c = ac + (−b)c = ac + (−bc) = ac − bc. Второе равенство доказывается аналогично.

Утв.: Лемма о сокращении. Пусть кольцо K не содержит делителей нуля. Если a, b, c — элементы кольца K, причем a <> 0, то из каждого условия: ab = ac и ba = ca следует b = c.

Док-во. Если ab = ac, то a(b − c) = 0. Так как в кольце K нет делителей нуля и a<>0, то b − c = 0, откуда b = c. Если ba = ca, то рассуждения аналогичны.

Поле. Примеры числовых полей. Делители нуля в поле.

Кольцо F называется полем, если множество его ненулевых элементов, F \ {0}, непусто и образует абелеву группу. Эта группа называется мультипликативной группой поля. Из определения следует, что любое поле содержит по крайней мере 2 элемента: 0 и 1. Если F — поле и F′ ⊆ F, причем F′ само является полем относительно тех же операций сложения и умножения, тогда F′ называется подполем поля F.

Примеры: Числовые кольца Q, R, C с обычными операциями сложения и умножения являются полями. Кольцо Z полем не является.

Утв .: Поле не имеет делителей нуля.

Док-во: Пусть поле F обладает делителями нуля, т. е. ab = 0 для некоторого a <> 0 и некоторого b <> 0. Таким образом, F \ {0} не замкнуто относительно операции умножения, следовательно, не образует группу, т. е. F полем не является.

Расширенный алгоритм Евклида для многочленов. Коэффициенты Безу (линейное разложение НОД).

Пусть f, g, d — ненулевые многочлены из F[x] и d — НОД многочленов f и g. Тогда найдутся такие u, v из F[x], что       uf + vg = d, причем deg u < deg g, а deg v < deg f. Многочлены u и v называются коэффициентами Безу.

Доказательство. Очевидно, что достаточно научиться находить коэффициенты Безу по крайней мере для одного из возможных НОД, например, для НОД, выдаваемого алгоритмом Евклида. Применим к f и g алгоритм Евклида. В ходе его работы получим последовательности частных q₁, q₂, . . . , q_s+1 и остатков r₁, r₂, . . . , r_s. На первой итерации запишем два тривиальных равенства:

f = 1 · f + 0 · g, (γ−1)

g = 0 · f + 1 · g, (γ0)

и вычтем из первого второе, умноженное на q₁. Тогда согласно (β₀) в левой части получим r₁. В правой части соберем множители у f и у g:

r₁ = 1 · f + (−q₁) · g. (γ1)

На второй итерации вычтем из равенства (γ0) равенство (γ1), умноженное на q₂. Согласно (β₁) в левой части получим r₂. В правой части снова соберем множители у f и у g:

r₂ = (−q₂) · f + (1 + q₁q₂) · g. (γ2)

На третьей итерации из (γ1) вычтем (γ2), умноженное на q₃. Согласно (β₂) в левой част получим r₃. В правой части снова соберем множители у f и у g:

r₃ = (1 + q₂q₃) · f + (−q₁ − q₃ − q₁q₂q₃) · g. (γ3)

Будем выполнять такие преобразования далее. На k-й итерации (k = 1, 2, . . . , s), вычитая из равенства (γk−2) равенство (γk−1), умноженное на q_k, получим

r_k = u_kf + v_kg, (γk)

где u_k, v_k — некоторые многочлены. На s-й итерации получим

d = r_s = u_sf + v_sg. (γs)

Можно считать, что многочлены us и vs ненулевые . Если    deg u_s < deg g и deg v_s < deg f, то u_s и v_s — искомые коэффициенты Безу. В противном случае выполним следующую процедуру.

Пусть, для определенности, deg u_s ≥ deg g. Разделим u_s на g: u_s = qg + r. Теперь из (γs)

получаем

d = rf + (v_s + qf)g.

Обозначим u = r, v = v_s + qf. Имеем uf + vg = d и deg u < deg g. Покажем, что deg v < deg f,

тем самым завершив доказательство теоремы. Предположим противное: deg v ≥ deg f, тогда

deg(uf) < deg g + deg f, но deg(vg) ≥ deg g + deg f, поэтому

deg d = deg(uf + vg) ≥ deg g + deg f,

что противоречит тому, что d — НОД многочленов f и g.

Алгоритм нахождения коэффициентов Безу, описанный при доказательстве теоремы, называется расширенным алгоритмом Евклида

Лемма о старшем члене.

Если α э C и |α| ≥ A+1, то |αⁿ| > |a₁αⁿ⁻¹+. . .+a_n|.

Доказательство.

|a₁αⁿ⁻¹ + a₂αⁿ⁻² + . . . + a_n| ≤ |a₁||α|ⁿ⁻¹ + |a₂||α|ⁿ⁻² + . . . + |a_n| ≤

≤ A(|α|ⁿ⁻¹ + |α|ⁿ⁻² + . . . + 1) = A ·(|α|ⁿ − 1)/(|α| − 1)≤

≤ A ·(|α| − 1)/A= |α|ⁿ − 1,

откуда следует требуемое неравенство.

 

 

Формулы Виета.

Рассмотрим задачу нахождения коэффициентов многочлена по его корням.Раскладывая квадратный многочлен x²+px+1 на линейные множители, раскрывая скобки и приводя подобные, получаем

x² + px + 1 = (x − c₁)(x − c₂) = x² − (c₁ + c₂)x + c₁c₂,откуда

p = −(c₁ + c₂), q = c₁c₂.

Это хорошо известные формулы Виета, связывающие коэффициенты квадратного многочлена и его корни.
То же самое можно проделать с кубическим многочленом (со старшим коэффициентом 1)

x³ + px² + qx + r = (x − c₁)(x − c₂)(x − c₃) =

= x³ − (c₁ + c₂ + c₃)x² + (c₁c₂ + c₁c₃ + c₂c₃)x − c₁c₂c₃,откуда

p = −(c₁ + c₂ + c₃), q = c₁c₂ + c₁c₃ + c₂c₃, r = −c₁c₂c₃.

Рассмотрим теперь многочлен n-й степени со старшим коэффициентом 1:

f = xⁿ + a₁xⁿ⁻¹ + a₂xⁿ⁻² + . . . + a_n−1x + a_n =

= (x − c₁)(x − c₂). . .(x − c_n).

Раскрывая скобки в правой части и собирая коэффициенты при каждой степени, получаем формулы Виета:

 

НОД целых чисел . Алгоритм Евклида .

Если некоторое целое число d является делителем одновременно для каждого из двух заданных чисел a и b, то d называется их общим делителем . Среди всех общих делителей двух заданных целых чисел a и b выберем максимальный. Он называется наибольшим общим делителем этих чисел и обозначается НОД(a, b).

Алгоритм Евклида: пусть a и b - целые числа, не равные нулю. Тогда последовательность чисел a>b>r₁>...>r_n определена тем, что каждое r_k - это остаток от деления предпредыдущего на предыдущее число, а предпоследнее делится на последнее нацело. Последний не нулевой член этой последовательности - НОД.

Теорема. Для любых целых чисел a и b, не равных нулю, алг . Евк . останавливается за конечное число шагов и корректно вычисляет НОД {a, b}.

Док-во: 1) По свойству операции деления с остатком (остаток не меньше нуля и строго меньше модуля делителя) имеем: |b| < r1 < r2 < r3 < . . . ≤ 0 - ч. и т.д.

2) См. алгоритм. r_s-1:d (1). q_s :d и r_s :d => r_{s- 2} :d (2) . Из (1) и (2) : r_s-3:d и т.д. В конце получаем: r₂ :d, r₁:d, b:d, a:d. d - общий делитель. Тогда пусть δ - произвольный общий делитель. Докажем, что если d делится на δ, т.е. на любой общий делитель, то он больший.

b:δ , a:δ = > r₁=a-q₁b:δ, r₂=b-q₂r₁:δ, ...,  r_s=r_s-2-q_sr_s-1:δ ч. и т.д.

Расширенный алгоритм Евклида. Коэффициенты Безу (линейное разложение НОД)

Теорема о линейном разложении НОД: Пусть a, b — целые числа, одновременно не равные нулю, и d= НОД(a, b). Тогда найдутся такие целые u, v, что ua + vb = d.

Числа u и v называются коэффициентами Безу.

Док-во: Применим к a и b алгоритм Евклида. В ходе его работы получим последовательности частных q1, q2, . . . , qs+1 и остатков r1, r2, . . . , rs. На первой итерации запишем два тривиальных равенства: a = 1 ·a + 0·b, b = 0·a + 1·b. Вычтем из первого второе, умноженное на q1. Тогда согласно в левой части получим r1 (из алг. Евклида). В правой части соберем множители у a и у b: r1 = 1·a + (−q1)·b. На второй итерации вычтем из равенства 2 равенство 3, умноженное на q2. Согласно алг. в левой части получим r2. В правой части снова соберем множители у a и у b: r2 = (−q2)·a + (1 + q1q2)·b.

На третьей итерации получим r3 = (1 + q2q3)·a + (−q1 − q3 − q1q2q3)·b. Будем выполнять такие преобразования далее. На k-й итерации (k = 1, 2, . . . , s) получим: r_k = u_ka + v_kb. На s-й итерации получим: d = r_s = u_sa + v_sb. Ч. и т.д..

Алгоритм нахождения коэффициентов Безу, описанный при док-ве теоремы - расширенный алгоритм Евклида.

1234567Следующая ⇒

Поделиться: