АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. S-M-N-теорема, приклади її використання
  2. SALVATOR - это переход физического явления в семантико-нейронный алгоритм (инструкцию) освобождения человека от негативных последствий этого явления.
  3. XII. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ
  4. Алгебраическая и тригонометрическая формы записи комплексных чисел.
  5. Алгебраїчна замкненість поля комплексних чисел. Канонічний розклад многочленна над полем комплексних чисел та його єдиність.
  6. Алгебраїчна форма запису комплексних чисел та дії над комплексними числами, записаними у цій формі
  7. Алгоритм
  8. Алгоритм
  9. Алгоритм
  10. Алгоритм
  11. Алгоритм 65 «Кровотечение в послеродовом периоде»
  12. Алгоритм 72 «Ожоги и травмы глаза, века, конъюнктивы»

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

Для б-я цілих 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, то існують такі q1 та r1, що виконується співвідношення: a = b * q1 + r, 0≤r1≤b, ділимо b на r1: b = r1* q2 + r2, якщо r2 = 0 , 0≤ r2≤ r1

r1 = r2* q3 + r3 , 0≤ r3≤ r2

r2 = r3* q4 + r4, 0≤ r4≤ r3

………………….

rn-2= rn-1*qn + rn , 0≤ rn≤ rn-1

rn-1= rn* qn+1.

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

Т.Евкліда:

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

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

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

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

……………..

НСД (a ,b) = rn

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

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

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

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

am= b * q1 m + r m,

b m = r1* q2 m + r2 m ,

r1 m = r2* q3 m + r3 m ,

………………….

rn-2 m = rn-1* qn m + rn m ,

rn-1 m = rn* qn+1 m.

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

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

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



Доведення:

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

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

Означення: якщо натур. число δ є спільним дільником a1 , a2, a3,..., an ,то δ назив спільним дільником цих чисел.

Означення: найб.із.спіл. дільн. чисел a1, a2, a3,…, an назив їх НСД.

НСД (a1, a2, a3,…., an ) = НСД(НСД(a1, a2, a3…., an-1), an ).

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

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

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

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

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

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

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

a=a1 d, b=b1 d

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

НСД (a1 ,b1) = 1, є N, k=b1t.

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

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

 

НСК [a,b] = .

 

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 |


При использовании материала, поставите ссылку на Студалл.Орг (0.008 сек.)