67808
АРИФМЕТИКА ЦІЛИХ ЧИСЕЛ
Лабораторная работа
Математика и математический анализ
Якщо для цілих чисел і в кільці цілих чисел існує таке число, що, то кажуть, що ціле число ділиться на ціле число, і пишуть. При цьому число називається діленим або кратним числа, число – дільником числа, число – часткою. Будь-яке ціле число завжди можна розділити з остачею на довільне ціле число.
Украинкский
2014-09-15
416.5 KB
10 чел.
PAGE \* MERGEFORMAT 5
Лабораторна робота № 3
Тема: АРИФМЕТИКА ЦІЛИХ ЧИСЕЛ
Мета роботи – вивчити основні поняття, необхідні для обґрунтування модульної арифметики і операцій в розширеннях скінченних полів.
Короткі теоретичні відомості.
1.Подільність цілих чисел.
Означення. Якщо для цілих чисел і в кільці цілих чисел існує таке число , що , то кажуть, що ціле число ділиться на ціле число , і пишуть . При цьому число називається діленим або кратним числа , число – дільником числа , число – часткою.
Будь-яке ціле число завжди можна розділити з остачею на довільне ціле число .
Теорема (про ділення з остачею). Для будь-яких цілих чисел і , де , завжди існує одна і лише одна пара цілих чисел і таких, що
, де .
Число називається неповною часткою, а – остачею від ділення на .
Означення. Число , що одночасно ділить цілі числа і , називається спільним дільником цих чисел. Найбільше число з такою властивістю називається найбільшим спільним дільником (скорочено НСД) чисел і . Позначення: .
Цілі числа і називаються взаємно простими, якщо .
Означення. Число , що одночасно ділиться на цілі числа і , називається спільним кратним цих чисел. Найменше число з такою властивістю називається найменшим спільним кратним (скорочено НСК) чисел і . Позначення: .
Очевидно, .
Найбільший спільний дільник двох цілих чисел обчислюється за допомогою т.з. алгоритму Евкліда. У цьому алгоритмі основну роль відіграє операція ділення чисел з остачею, тобто представлення вигляду , де . Алгоритм Евкліда задається послідовністю рівностей
, ;
, ;
, ;
........................................... (1)
, ;
, .
Теорема. Для будь-яких цілих чисел і , одночасно не рівних нулю, найбільший спільний дільник завжди існує і дорівнює останній відмінній від нуля остачі алгоритму Евкліда.
Теорема (про лінійне представлення НСД) Для будь-яких цілих чисел і рівняння
,
де – найбільший спільний дільник цілих чисел і , завжди має розв'язок в цілих числах.
Нехай і – розв’язки рівняння . Запис
, (2)
називається лінійним представленням найбільшого спільного дільника цілих чисел і .
При рівняння (2) виражає критерій взаємної простоти чисел і .
Розв'язок рівняння , де , – цілі, можна знайти з допомогою т.з. розширеного алгоритму Евкліда. Очевидно, достатньо розв'язати це рівняння, при додатних і .
Діючи в класичній схемі (1) зворотним ходом від низу до верху, маємо
…
(йдемо по ланцюжку рівностей (1), виражаючи з кожної наступної рівності
остачу і підставляючи її в отриманий до цього моменту вираз)
....
Рівність (2) можна записати у векторній формі, тобто представити найбільший спільний дільник цілих чисел і набором коефіцієнтів розкладу за початковими числами:
.
Для знаходження вектора рівності (1) класичного алгоритму застосовуються до векторів (Арифметичні дії з впорядкованими наборами чисел виконуються покомпонентно). Відзначимо, що самі початкові числа і можна представити такими векторами дуже просто:
, тому що ,
, тому що .
Протокол роботи розширеного алгоритму Евкліда зручно записувати у вигляді таблиці:
|
Остачі |
… |
|||||||
|
Частки |
… |
|||||||
|
1 |
0 |
… |
||||||
|
0 |
1 |
… |
Отримання нових значень компонентів наборів показане в третьому рядку таблиці (клітинки виділені): з числа в першій клітинці віднімається число в другій клітинці, помножене на число, що стоїть праворуч від нього в другому рядку, результат записується в третю клітинку. Аналогічно виконується операція для знаходження компонент в четвертому рядку.
Лінійним діофантовим рівнянням називається рівняння вигляду
, (3)
де – невідомі, .
Нехай . Діофантове рівняння (3) має розв'язок тоді і тільки тоді, коли . При цьому загальний розв'язок визначається формулою:
, , (4)
де – частинний розв'язок рівняння (3), а – довільне ціле число.
Розв'язки рівнянь і можуть відрізнятися тільки знаками.
Алгоритм розв'язування діофантового рівняння наступний:
- За алгоритмом Евкліда знаходимо НСД . Якщо , то рівняння (3) має розв’язки. Якщо , то рівняння (3) розв’язків не має.
- За розширеним алгоритмом Евкліда знаходимо лінійне представлення НСД : . Визначаємо знаки для лінійного представлення.. Частинний розв’язок рівняння (3) має вигляд:
,
- Підставляючи отриманий частинний розв'язок в (4), отримаємо загальний розв'язок рівняння (3).
Простим числом називається натуральне число, в якого є точно два нерівні натуральні дільники: 1 і воно саме.
Властивості простих чисел:
- Найменший відмінний від одиниці дільник натурального числа є простим.
- Найменший простий дільник складеного числа не більший за .
З властивості 2 випливає просте правило перевірки натурального числа на простоту: якщо натуральне число не ділиться на жодне просте число таке, що , то – просте; в іншому випадку – складене.
Основна теорема арифметики: кожне натуральне число єдиним, з точністю до порядку співмножників, чином представляється у вигляді добутку степенів простих чисел.
Канонічним розкладом (канонічною формою) складеного натурального числа називається представлення його у вигляді . Якщо ж враховуються нульові показники степеня, то такий розклад називається узагальненим канонічним розкладом.
Наслідок. Нехай і – довільні натуральні числа, і нехай
,
– їх узагальнені канонічні розклади (,). Тоді найбільший спільний дільник і найменше спільне кратне чисел і відповідно мають вигляд
де ;
де .
Порядок виконання роботи.
- Вивчити короткі теоретичні відомості про арифметику в кільці цілих чисел.
2. За допомогою класичного алгоритму Евкліда знайти НСД і НСК чисел:
1) 3094 и 1235; 13) 1972 и 2873;
2) 4557 и 1209; 14) 2257 и 5217;
3) 1430 и 4774; 15) 6426 и 1593;
4) 3366 и 1326; 16) 7371 и 1386;
5) 1254 и 1794; 17) 4372 и 1356;
6) 1683 и 1326; 18) 2583 и 3403;
7) 2142 и 3468; 19) 2870 и 1353;
8) 1426 и 3657; 20) 5124 и 1612;
9) 4047 и 1539; 21) 2457 и 4998;
10) 3139 и 3870; 22) 4473 и 2508;
11) 6630 и 5199; 23) 2639 и 1911;
12) 1836 и 2210; 24) 4914 и 1426;
25) 3315 и 4620.
3. За допомогою розширеного алгоритму Евкліда знайти лінійне представлення НСД чисел з п.2.
4. Знайти розв'язок діофантового рівняння .
|
№ |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
a |
24 |
52 |
13 |
29 |
29 |
44 |
65 |
18 |
55 |
31 |
|
b |
51 |
73 |
61 |
77 |
94 |
93 |
97 |
47 |
201 |
86 |
|
№ |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
|
a |
27 |
33 |
47 |
17 |
55 |
18 |
115 |
14 |
38 |
31 |
|
b |
43 |
78 |
122 |
76 |
69 |
71 |
41 |
39 |
53 |
87 |
|
№ |
21 |
22 |
23 |
24 |
25 |
|
a |
21 |
48 |
37 |
26 |
45 |
|
b |
79 |
109 |
98 |
67 |
103 |
5. За допомогою канонічного розкладу знайти НСД і НСК чисел з п.2.
6. Перевірити на простоту число:
1) 2293; 13) 1971;
2) 2373; 14) 2087;
3) 1037; 15) 1813;
4) 1119; 16) 1387;
5) 1289; 17) 1553;
6) 1311; 18) 2573;
7) 1459; 19) 1359;
8) 1291; 20) 1273;
9) 1623; 21) 2281;
10) 2013; 22) 2089;
11) 1281; 23) 1723;
12) 1817; 24) 1449;
25) 1543.
7. Скласти звіт, приєднавши отримані результати.
Вимоги до звіту.
У звіті мають бути приведені:
- Короткі відомості про вивчені властивості цілих чисел.
- Розв’язання свого варіанту з необхідними поясненнями.
- Відповіді на контрольні питання.
Контрольні питання:
- Як визначається подільність цілих чисел?
- Що означає поділити число на число з остачею?
- Що таке НСД двох цілих чисел?
- Що таке НСК двох цілих чисел?
- У чому суть класичного алгоритму Евкліда?
- У чому суть розширеного алгоритму Евкліда?
- Що називається діофантовим рівнянням? Як його розв’язати?
- Що називається канонічним розкладом натурального числа? Узагальненим канонічним розкладом?
- Як знайти НСД і НСК двох цілих чисел за допомогою канонічного розкладу?
- Які натуральні числа називаються простими? Складеними?
- Як перевірити натуральногое число на простоту?
