67808

АРИФМЕТИКА ЦІЛИХ ЧИСЕЛ

Лабораторная работа

Математика и математический анализ

Якщо для цілих чисел і в кільці цілих чисел існує таке число, що, то кажуть, що ціле число ділиться на ціле число, і пишуть. При цьому число називається діленим або кратним числа, число – дільником числа, число – часткою. Будь-яке ціле число завжди можна розділити з остачею на довільне ціле число.

Украинкский

2014-09-15

416.5 KB

9 чел.

PAGE   \* MERGEFORMAT 5

Лабораторна робота № 3

Тема: АРИФМЕТИКА ЦІЛИХ ЧИСЕЛ

Мета роботи – вивчити основні поняття, необхідні для обґрунтування модульної арифметики і операцій в розширеннях скінченних полів.

Короткі теоретичні відомості.

1.Подільність цілих чисел.

Означення. Якщо для цілих чисел  і  в кільці цілих чисел  існує таке число , що , то кажуть, що ціле число  ділиться на ціле число , і пишуть . При цьому число  називається діленим або кратним числа , число  – дільником числа , число  – часткою.

Будь-яке ціле число  завжди можна розділити з остачею на довільне ціле число .

Теорема (про ділення з остачею). Для будь-яких цілих чисел  і , де , завжди існує одна і лише одна пара цілих чисел  і  таких, що

, де .

Число  називається неповною часткою, а  – остачею від ділення  на  .

Означення. Число , що одночасно ділить цілі числа  і , називається спільним дільником цих чисел. Найбільше число  з такою властивістю називається найбільшим спільним дільником (скорочено НСД) чисел  і . Позначення: .

Цілі числа  і  називаються взаємно простими, якщо .

Означення. Число , що одночасно ділиться на цілі числа  і , називається спільним кратним цих чисел. Найменше число  з такою властивістю називається найменшим спільним кратним (скорочено НСК) чисел  і . Позначення: .

Очевидно,  .

Найбільший спільний дільник двох цілих чисел  обчислюється за допомогою т.з. алгоритму Евкліда. У цьому алгоритмі основну роль відіграє операція ділення чисел з остачею, тобто представлення вигляду , де . Алгоритм Евкліда задається послідовністю рівностей

, ;

, ;

, ;

...........................................        (1)

, ;

, .

Теорема. Для будь-яких цілих чисел і , одночасно не рівних нулю, найбільший спільний дільник завжди існує і дорівнює останній відмінній від нуля остачі алгоритму Евкліда.

Теорема (про лінійне представлення НСД) Для будь-яких цілих чисел і рівняння

,

де  – найбільший спільний дільник цілих чисел і , завжди має розв'язок в цілих числах.

Нехай  і  – розв’язки рівняння . Запис

,       (2)

називається лінійним представленням найбільшого спільного дільника цілих чисел і .

При  рівняння (2) виражає критерій взаємної простоти чисел  і .

Розв'язок рівняння , де , – цілі, можна знайти з допомогою т.з. розширеного алгоритму Евкліда. Очевидно, достатньо розв'язати це рівняння, при додатних  і .

Діючи в класичній схемі (1) зворотним ходом від низу до верху, маємо

(йдемо по ланцюжку рівностей (1), виражаючи з кожної наступної рівності

остачу і підставляючи її в отриманий до цього моменту вираз)

....

Рівність (2) можна записати у векторній формі, тобто представити найбільший спільний дільник цілих чисел  і  набором коефіцієнтів розкладу за початковими числами:

.

Для знаходження вектора  рівності (1) класичного алгоритму застосовуються до векторів (Арифметичні дії з впорядкованими наборами чисел виконуються покомпонентно). Відзначимо, що самі початкові числа  і  можна представити такими векторами дуже просто:

, тому що ,

, тому що .

Протокол роботи розширеного алгоритму Евкліда зручно записувати у вигляді таблиці:

Остачі

Частки

1

0

0

1

Отримання нових значень компонентів  наборів  показане в третьому рядку таблиці (клітинки виділені): з числа в першій клітинці віднімається число в другій клітинці, помножене на число, що стоїть праворуч від нього в другому рядку, результат записується в третю клітинку. Аналогічно виконується операція для знаходження компонент  в четвертому рядку.

Лінійним діофантовим рівнянням називається рівняння вигляду 

,             (3)

де  – невідомі,  .

Нехай . Діофантове рівняння (3) має розв'язок тоді і тільки тоді, коли . При цьому загальний розв'язок визначається формулою:

,    ,        (4)

де  – частинний розв'язок рівняння (3), а  – довільне ціле число.

Розв'язки рівнянь  і  можуть відрізнятися тільки знаками.

Алгоритм розв'язування діофантового рівняння наступний:

  1.  За алгоритмом Евкліда знаходимо НСД . Якщо , то рівняння (3) має розв’язки. Якщо , то рівняння (3) розв’язків не має. 
  2.  За розширеним алгоритмом Евкліда знаходимо лінійне представлення НСД : . Визначаємо знаки для лінійного представлення.. Частинний розв’язок рівняння (3) має вигляд:

,  

  1.  Підставляючи отриманий частинний розв'язок в (4), отримаємо загальний розв'язок рівняння (3).

Простим числом називається натуральне число, в якого є точно два нерівні натуральні дільники: 1 і воно саме.

Властивості простих чисел:

  1.  Найменший відмінний від одиниці дільник натурального числа  є простим.
  2.  Найменший простий дільник складеного числа  не більший за .

З властивості 2 випливає просте правило перевірки натурального числа на простоту: якщо натуральне число  не ділиться на жодне просте число  таке, що , то  – просте; в іншому випадку – складене.

Основна теорема арифметики: кожне натуральне число єдиним, з точністю до порядку співмножників, чином представляється у вигляді добутку степенів простих чисел.

Канонічним розкладом (канонічною формою) складеного натурального числа  називається представлення його у вигляді . Якщо ж враховуються нульові показники степеня, то такий розклад називається узагальненим канонічним розкладом.

Наслідок. Нехай  і  – довільні натуральні числа, і нехай

,  

– їх узагальнені канонічні розклади (,). Тоді найбільший спільний дільник і найменше спільне кратне чисел  і  відповідно мають вигляд

де ;

де .

Порядок виконання роботи.

  1.  Вивчити короткі теоретичні відомості про арифметику в кільці цілих чисел.

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. Скласти звіт, приєднавши отримані результати.

Вимоги до звіту.

У звіті мають бути приведені:

  1.  Короткі відомості про вивчені властивості цілих чисел.
  2.  Розв’язання свого варіанту з необхідними поясненнями.
  3.  Відповіді на контрольні питання.

Контрольні питання:

  1.  Як визначається подільність цілих чисел?
  2.  Що означає поділити число на число з остачею?
  3.  Що таке НСД двох цілих чисел?
  4.  Що таке НСК двох цілих чисел?
  5.  У чому суть класичного алгоритму Евкліда?
  6.  У чому суть розширеного алгоритму Евкліда?
  7.  Що називається діофантовим рівнянням? Як його розв’язати?
  8.  Що називається канонічним розкладом натурального числа? Узагальненим канонічним розкладом?
  9.  Як знайти НСД і НСК двох цілих чисел за допомогою канонічного розкладу?
  10.  Які натуральні числа називаються простими? Складеними?
  11.  Як перевірити натуральногое число на простоту?
  12.  


 

А также другие работы, которые могут Вас заинтересовать

4226. Україна у ХIХ – першій половині ХХ століття: боротьба за державність 290 KB
  Вступ Цей конспект-довідник є черговою працею авторського колективу кафедри українознавства УДУВГП, якому передували видання Україна давня і середньовічна та Україна козацька. Третій випуск присвячується подіям, пов...
4227. Практична робота на тему Масив 20.25 KB
  Масив Мета РГР: побудова схеми алгоритму для рішення задачі, обробки одновимірного масиву у відповідності з варіантом написати програму на мові Pascal, згідно з алгоритмом. Записка до РГР повинна містити: титульний лист текс...
4228. Особливості психології управління 412 KB
  Предмет психології управління. Розгляд процесу формулювання предмета психології управління не тільки в хронологічному, а й у хронологічно-концептуальному аспекті дає змогу дослідити його і в часі, і в межах різних наукових підходів...
4229. Практикум по химии для судентов 1.27 MB
  Введение Под химией нефти и газа подразумевается область знаний, охватывающая изучение химического состава нефти и газов, ее отдельных фракций или индивидуальных веществ, выделенных из нефтяных и газовых фракций. Задачей химии нефти и газа является...
4230. Створення форм засобами MS Access 97.5 KB
  Створення форм засобами MSAccess Мета роботи: Вивчення основ створення форм за допомогою Майстра форм Завдання: Створити форми для відображення даних з створених таблиць бази даних. Форми повинні дозволяти редагувати дані з таблиць та відображ...
4231. Знайомство з сервером бази даних Access та створення тестової бази даних 236.5 KB
  Знайомство з сервером бази даних Access та створення тестової бази даних Мета роботи: Вивчення основ побудови бази даних засобами середовища Access Завдання: Створити структуру бази даних, модифікувати її, ввести дані у таблицю. Перша таблиця бази д...
4232. Економічна теорія опорний конспект лекцій 858 KB
  В курсі лекцій висвітлюються загальні основи економічного життя суспільства розкриваються закономірності розвитку суспільного виробництва з’ясовується механізм дії ряду економічних законів та механізм використання їх людьми у процесі господар...
4233. Економіка будівельної сфери. Курс лекцій 446.5 KB
  Тема №1. Вступ. Предмет і завдання. Зміст і роль курсу Економіка будівництва План. 1. Поняття економіка. 2. Предмет і завдання курсу. 3. Зміст і роль курсу. Поняття економіка вперше ввів великий мислитель Стародавньої Греції Аристотель (384 – 3...
4234. Введение в экономику. Рыночная экономка и ее законы 64.19 KB
  Введение в экономику Слово экономика можно рассматривать с двух точек зрения: во-первых, как род занятий (в переводе с греч. означает умение вести хозяйство) во-вторых, как науку. Все науки, известные человеку делятся на естественные, о...