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

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

Для б-я цілих 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 = rn-1}* q_n m + r_n m,

r_{n-1 m = rn}* 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] = .

Поиск по сайту: