19.Теорема про ділення з остачею в кільці цілих чисел. Нсд і нск двох чисел і зв’язок між ними. Алгоритм Евкліда.

Теорема про ділення з остачею:

Для б-я цілих a,b (b )існує і при чому єдина пара чисел q і r і виконується рівність: a=bq+r, 0 , r – остача від ділення, і не від’ємне число.

Доведення:

1.Розгл. a/b=q (ціле),a=bq, a=bq+0

2.a/b(дробове), тоді знайдеться таке q, що із врахування 1 випадку: q

Будемо вважати, що b-додатнє

Нехай b–від’ємне, тоді –b>0

Застос. a= a=(-b)(-q)+r, 0<=r<

a=(- )(-q)+r, 0<=r<

Дов. єдиність представлення. Припуст., що є друга пара , тоді

Ліва ч. ділиться націло на b. В силу рівності і права частина також діл. націло на b, але і діл. націло на b, то це можливо лише тоді, коли

Приведе до суперечності.

Очевидно, що з цієї теор.випл.наслідок

коли r=0

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

Розгл. два натуральних числа a та b. Може трапитися так, що a ділиться націло на b, a=b*q очевидно, що тоді множина спільних множників чисел a та b співпадає з множиною дільників b. Отже НСД (a ,b) = b. Якщо а не ділиться націло на b, то існують такі q₁ та r₁, що виконується співвідношення: a = b * q₁ + r, 0≤r₁≤b, ділимо b на r₁: b = r₁* q₂ + r₂, якщо r₂ = 0 , 0≤ r₂≤ r₁

r₁ = r₂* q₃ + r₃ , 0≤ r₃≤ r₂

r₂ = r₃* q₄ + r₄, 0≤ r₄≤ r₃

………………….

r_n-2= r_n-1*q_n + r_n , 0≤ r_n≤ r_n-1

r_n-1= r_n* q_n+1.

цей алгоритм ділення назив. алгоритмом Евкліда.

Т.Евкліда:

Остання відмінна від 0 остача алгоритму Евкліда = найб. спіл. дільнику цих натуральних чисел.

Провед. міркування рухаючись нерівност. алгоритму Евкліда знизу вгору:

НСД( r_n-1, r_n )= r_n

НСД( r_n-2, r_n-1 )= r_n-1

……………..

НСД (a ,b) = r_n

на практиці для знаходження НСД застосов. алгоритм Е. запис. його справа наліво, згори вниз.

Т_1. якщо натур. числа помножити a ,b на натур. m то їх НСД також потрібно помножити на дане ч. m

НСД (a ,b) = d => (для будь – якого m) НСД (am ,bm) = dm.

Помножити кожну з рівностей алг. Е на m

am= b * q₁ m + r m,

b m = r₁* q₂ m + r₂ m ,

r₁ m = r₂* q₃ m + r₃ m ,

………………….

r_n-2 m = r_n-1* q_n m + r_n m ,

r_n-1 m = r_n* q_n+1 m.

Згідно теор. Евкл отримали доведення.

Т_2. для б-я натур. a ,b існ .цілі U,V, для яких викон. рівність:

НСД (a ,b) = а U + b V, тобто НСД (a ,b) є лін.комб. цих чисел.

Доведення:

Для доведення потрібно рухаючись рівностями алгоритму Евкліда знизу вгору визначити r_n через a ,b і так як всі перетворення при цьому будуть лінійними, то ми одержимо доводжувану формулу.

Т_3. якщо натур. δ є спільним дільником чисел a ,b, то його можна винести за знак НСД.

Означення: якщо натур. число δ є спільним дільником a₁ , a₂, a₃,..., a_n ,то δ назив спільним дільником цих чисел.

Означення: найб.із.спіл. дільн. чисел a₁, a₂, a₃,…, a_n назив їх НСД.

НСД (a₁, a₂, a₃,…., a_n ) = НСД(НСД(a₁, a₂, a₃…., a_n-1), a_n ).

Означення: натур. ч. m, яке ділиться одночасно на натур. числа a ,b назив. спільним кратним цих чисел.

Означення: найм. зі спільних кратних назив. їх НСК.

Якщо очевидно про що йде мова ,то [a,b].

Знайдемо формулу для обчислення НСК двох чисел.

Нехай М спільне кратне натур.чисел a,b.

М ділиться націло на а => М=ak

М ділиться націло на b => є N

a=a₁ d, b=b₁ d

НСД (a ,b) = d =>

НСД (a₁ ,b₁) = 1, є N, k=b₁t.

Так як a₁, b₁ взаємнопрості, то => k ділиться націло на b₁, тобто k=b₁t. ; (1).

М – загал. вигляд спільн.кратн. чисел a, b. Очевидно, що із останньої формули НСК

НСК [a,b] = .