Бойко Є А 3 вар
Практична робота № 12
Тема: Алгоритм Евкліда НСД. Ознаки подільності чисел.
Мета: Навчитися виконувати НСД за алгоритмом Евкліда. Знаходити подільність чисел за методами подільності.
Виконання роботи
Завдання 1. Раціональне число а / b задане ланцюжком неповних часток. Побудувати відповідне найменше раціональне число а / b і знайти розв’язок рівняння ах + b у = 1. Виконати свій варіант і варіант свій+13.
3) a/b=[0,3,1,2,7,1]
i |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
q |
|
0 |
3 |
1 |
2 |
7 |
1 |
Pi |
1 |
0 |
3*0+1=1 |
1*1+0=1 |
2*1+1=3 |
7*3+1=22 |
1*22+3=25 |
Qi |
0 |
1 |
3*1+0=3 |
1*3+1=4 |
2*4+3=11 |
7*11+4=81 |
1*81+11=92 |
X=25 Y=92
Ax-by=1
A=81 b=22
25*81-22*92=1
Відповідь A=81 b=22
a/b=[1,25,1,2,3,1,1]
i |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
q |
|
1 |
25 |
1 |
2 |
3 |
1 |
1 |
Pi |
1 |
1 |
25*1+1=26 |
1*26+1=27 |
2*27+26=80 |
3*80+27=267 |
1*267+80=347 |
347+267=614 |
Qi |
0 |
1 |
25*1+0=25 |
1*25+1=26 |
2*26+25=77 |
3*77+26=257 |
1*257+77=334 |
334+257=591 |
непарна кількість ітерацій : x- y+
Х=614 У=591
by - Ax=1
А=334 В=347
591*347-614*334=1
Відповідь А=334 В=347
Контрольні питання
1. Дати визначення простого числа, складеного числа, неповної частки, залишку.
2. Сформулювати основні властивості подільності чисел.
3. Сформулювати теорему про ділення з залишком.
4. В чому полягає різниця між взаємно простими і попарно простими числами?
5. Дати визначення спільного дільника довільного набору цілих чисел d c b a , , , .
6. Дати означення найбільшого спільного дільника b a, .
7. Спираючись на властивості подільності чисел довести, що якщо числа b a,
можна зв’язати рівністю r q b a , то r b b a , , .
8. Сформулювати алгоритм Евкліда для знаходження b a, .
9. Відомо, що a - довільне число, а p - просте число. Які можливі варіанти p a, ?
10. Дати визначення найменшого спільного кратного b a, . Який існує зв’язок між
b a, та b a, ?
11. Яке обмеження існує на найменший дільник числа a ?
12. Сформулювати теорему про єдиність канонічного розкладання довільного цілого
числа a на прості множники.
13. Що таке неперервний дріб?
14. Довести, що неперервний дріб для раціонального числа завжди має скінчену
довжину. Чи вірно це для ірраціональних чисел? Обґрунтуйте свою думку.
15. Що таке підходящий дріб. Якщо взяти два сусідніх підходящих дроба, то де буде
розташоване вихідне число?
16. Сформулюйте самостійно схему обчислення підходящих дробів для довільного
нескорочуваного раціонального дробу.
17. Які властивості мають підходящі дроби?
18. Використовуючи схему розкладання раціонального числа на неперервні дроби знайти для двох чисел 197 та 23 розв’язок рівняння 1 23 197 y x .