ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 04.06.2024
Просмотров: 36
Скачиваний: 0
|
648 |
: |
648 = 261× 2 +126; |
a = bq |
|
+ r , r = 126, 0 < 126 < 261 |
|||
|
|
|
0 |
||||||
261 |
|
|
1 |
1 |
|||||
|
|
|
|
|
|||||
|
261 |
: 261 = 126 × 2 + 9, |
b = r q |
+ r |
r = 9, 0 < 9 < 126 |
||||
|
|
||||||||
126 |
|
|
|
|
1 |
1 |
2 |
2 |
|
|
|
|
|
|
|
|
|
||
|
126 |
: |
126 = 9 ×14 + 0, |
r = 0 |
|
|
|
||
|
|
|
|
||||||
9 |
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
r2 = 9 . Отже, (648,261) = 9 |
|||
Останній ненульовий залишок - |
2. Шукаємо подання НСД лінійною комбінацією:
d = r2 = b - r1q1 ; r1 = a - bq0 d = b - (a - bq0 )q1 = a(- q1 )+ b(1 + q0 q1 ) = -2a + (1+ 4)b = -2a + 5b
Отже x = −2, y = 5
Деякі властивості НСД:
1. |
Якщо (a, b) "m Î Z : (am, bm) = m(a, b) . |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
a b |
|
(a, b) |
|
|
a |
|
b |
|
|
(a, b) |
|
|
|||||||
2. |
Якщо d | a, d | b, "d Î Z |
|
, |
|
|
= |
|
|
, зокрема |
|
|
|
, |
|
|
= |
|
|
= 1 |
, тобто |
|
|
d |
|
|
|
(a, b) |
||||||||||||||
|
d |
|
d |
|
|
(a, b) |
|
(a, b) |
|
|
|
два будь-яких цілих числа, поділених на НСД цих чисел є взаємно простими числами.
3.Якщо (a, b) = 1 (ca, b) = (c, b);
4.Якщо (a, b) = 1. b | ac b | c ;
5.Якщо a1 , a2 ,..., am взаємно прості з кожним з b1 , b2 ,..., bn , то добуток a1 × a2 ×... × am взаємно простий з добутком b1 × b2 ×... × bn
7
Питання 3 Найменше спільне кратне (НСК).
Дані числа a1 , a2 ,..., am . Кожне з чисел, що є кратним кожному з даних чисел, носить
назву спільне кратне (СК). Найменше із усіх кратних називається найменше спільне кратне даних чисел.
Нехай (a, b) = d , тоді a = a1d , |
b = b1d і (a1 , b1 ) = 1 (властивості НСД, 2.) Нехай M - деяке |
|||||||||||||||
кратне a та b , тобто M = ka і |
|
M |
= |
ka |
= |
ka1d |
= |
ka1 |
Î Z . Оскільки (a , b ) = 1 , то k повинно |
|||||||
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
b b b1d |
1 |
1 |
||||||||
|
|
|
|
|
|
|
b1 |
|
||||||||
ділитися на b1 , тобто k = b1t . Для СК буде вірна формула: |
|
|||||||||||||||
M = ka = ak = ab t = |
ab1d |
t = |
a × b |
t |
|
|
|
|
||||||||
|
|
|
|
|
|
|||||||||||
|
|
|
1 |
d |
|
|
|
d |
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
||||||
Найменше значення СК буде за умови, що t |
= 1, тобто для НСК виконується формула: |
|||||||||||||||
[a,b]= m = |
ab |
|
, тоді M = m × t |
|
|
|
|
|||||||||
(a,b) |
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Теореми:
1.Сукупність спільних кратних чисел a та b співпадає з сукупністю кратних для їх НСК.
2.НСК a та b дорівнює відношенню добутку цих чисел до їх НСД.
8
Питання 4 Прості числа. Єдиність розкладання довільного цілого числа на прості множники.
1. Вислови:
1.Число 1 має тільки один додатний дільник – самого себе. Одиниця стоїть осторонь у ряду натуральних чисел.
2.Найменший дільник, що не дорівнює 1, для будь-якого цілого числа є число
просте. (Візьмемо число a і його найменший дільник q ¹ 1 . Допускаємо, що q = q1 × r, q1 £ q, r £ q . Тоді a ділиться на q1 і на r , тобто a має дільник, менший за q , що є протиріччям вихідному посиланню.)
3. Найменший дільник, що не дорівнює 1, для будь-якого складеного цілого числа a
не перевищує значення a . (Нехай a = q × c . Оскільки q - найменший дільник, то c ³ q .
Отже ac ³ q 2 c, a ³ q 2 , або q £ a .
4.Простих чисел безкінечно багато.
5.Решето Ератосфена для вибору простих чисел, які не перевищують даного числа
N.
1)Обираємо перше просте число – p1 = 2 . Викреслюємо всі цілі числа з інтервалу (4, N ), кратні 2.
2)Обираємо наступне найменше просте число p2 = 3 . Викреслюємо всі цілі числа з інтервалу (9, N ), кратні 3.
3)Повторюємо процес з наступним p3 = 5 .
4)Обираючи чергове pk , звертаємо увагу на те, що кандидатів на викреслення
слід розглядати починаючи з числа pk 2 , бо всі менші складені числа викреслені, як такі, що кратні простим числам, меншим за pk .
5)Викреслення можна зупинити, коли pk перевищить N . Усі складені числа на той час будуть викреслені.
2.Єдиність розкладання довільного цілого числа на прості множники.
Базові вислови для складених чисел:
∙Довільне ціле a або взаємно просте з даним простим числом p < a , або ділиться на нього.
∙Якщо добуток декількох множників ділиться на просте число p , то хоча б один з множників теж ділиться на p .
∙Довільне ціле число можна розкласти на добуток простих множників єдиним способом. (враховуючи комутативність множення)
a= p1 × p2 ×... × pn
∙У наведеному розкладанні деякі з множників можуть повторюватися не
один раз. Позначивши через p1 , p2 ,..., pk тільки різні множники, а через a1 , a2 ,..., ak відповідні кратності входження множників до числа a ,
запишемо канонічне розкладання довільного цілого числа a на множники:
a = p1α1 × p2 α2 ×... × pk αk
9
∙
d = p1β1 × p2 β2
Нехай |
a = p α1 × p |
α2 ×... × p |
|
αk |
- канонічне розкладання довільного цілого |
||
|
1 |
|
2 |
|
k |
|
|
числа |
a . Тоді усі дільники цього числа можна подати у канонічному |
||||||
вигляді: |
|
|
|
|
|
|
|
×... × pk βk |
, де 0 £ bi |
£ ai , |
i = |
|
|
||
1, k |
|
∙У відповідності до вищенаведеної формули, кількість дільників τ довільного цілого числа a можна знайти так:
τ= (α1 +1)(α 2 +1)...(α k +1)
∙Розглянемо канонічне розкладання m довільних цілих чисел:
ai = pi1αi1 |
× pi 2 |
αi 2 |
×...× pik αik , |
i = |
|
|
|
|
|
|
|
|
|
|
||||||
1, m |
. |
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
Тоді НСД цих чисел у канонічному вигляді має вигляд: |
|||||||||||||||||||
min (αi1 ) |
|
|
min (αi 2 ) |
|
|
min (αik |
) |
|
|
|
|
|
|
|
|
|||||
|
|
×... |
, i = 1, m |
|
|
|
|
|
||||||||||||
d = pi1i =1,m |
|
× pi 2 i =1,m |
|
× pik i =1,m |
|
|
, |
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
а НСК – |
(αi1 ) |
|
|
(αi 2 ) |
|
|
max (αik |
) |
|
|
|
||||||||
|
|
|
|
max |
|
max |
|
|
|
|
|
|||||||||
|
m = |
|
|
|
, i = 1, m |
|||||||||||||||
|
pi1i=1,m |
|
|
× pi 2 i=1,m |
|
|
×... × pik i =1,m |
|
|
∙Сукупність спільних дільників декількох цілих чисел співпадає з кількістю дільників НСД цих чисел.
∙НСК декількох взаємно простих чисел дорівнює їх добутку, а сукупність кратних декількох чисел співпадає з сукупністю кратних НСК цих чисел.
Приклад:
Дані 2 числа 12348 та 867. Побудувати канонічну форму цих чисел, знайти їх НСД та НСК.
Розв’язання:
а) 12348 за ознаками ділення ділиться на 4(22) і на 9 (32)
12348 = 3087 × 22 = 22 × 32 × 343 = 22 × 32 × 73 - канонічне розкладання числа. Дільників у цього числа буде τ = (2 +1)(2 +1)(3 +1) = 36
б) 867 = 3 ×172 - канонічне розкладання другого числа. Дільників у другого числа буде
τ = (1+1)(2 +1) = 6 : 1, 3, 17, 289, 51 та 867
НСД - d = (12348,867) = 2min (2,0)3min (2,1)7 min (3,0)17min (0,2) = 3
НСК - m = 2max (2,0)3max (2,1)7max (3,0)17max (0,2) = 223273172 = 4235364
10