67808

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

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

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

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

Украинкский

2014-09-15

416.5 KB

8 чел.

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.  


 

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

13264. Исследование разветвлённой цепи переменного тока 1.04 MB
  Лабораторная работа № 5 Исследование разветвлённой цепи переменного тока. Цель работы: Исследование зависимостей параметров разветвлённой цепи переменного тока от частоты. Исследование резонанса токов.
13265. Измерение мощностей цепей переменного тока 2.52 MB
  Лабораторная работа №6. Измерение мощностей цепей переменного тока. Цель работы: изучение методов измерения активной реактивной полной мощности и коэффициента мощности в цепях содержащих R C и L.. Приборы: 1. Универсальный стенд; 2. Ваттметр; ...
13266. Ознакомление с устройством и принципом работы трансформатора 1.49 MB
  Лабораторная работа № 7 Исследование однофазного трансформатора. Цель: Ознакомление с устройством и принципом работы трансформатора. Получение основных характеристик трансформатора. Приборы: 1. Амперметр 2. Вольтметр ...
13267. ИССЛЕДОВАНИЕ ДИОДОВ 361.5 KB
  ЛАБОРАТОРНАЯ РАБОТА № 8 ЭТ ИССЛЕДОВАНИЕ ДИОДОВ Цель работы: Изучение полупроводниковых диодов и стабилитронов снятие их вольтамперных характеристик. Приборы: 1.Универсальный стенд.
13268. Изучение выпрямителей 307.5 KB
  Лабораторная работа №9 Изучение выпрямителей Цель работы: Изучение различных схем выпрямления переменного тока. Определение основных характеристик выпрямителей. Приборы и принадлежности: 1. Универсальный стенд. 2. Осциллограф. 3. Амперметр. 4. Вольтм
13269. Изучение различных схем сглаживающих фильтров 335 KB
  Цель работы: Изучение различных схем сглаживающих фильтров определение основных характеристик. Изучение параметрического стабилизатора на стабилитроне. Приборы:1. Универсальный стенд. Амперметр. Вольтметр. Осциллограф. 10.1Теоретическое введени...
13270. Исследование тиристора 99.5 KB
  Лабораторная работа №11 Исследование тиристора. Цель работы: ознакомление с вольтамперными характеристиками и основными параметрами переключающих диодовтиристоров. Приборы:1.Универсальный стенд. 2.Авометр. 3.Амперметр. 4.Электронный вольтметр. 11.1Теоритич
13271. Опытное определение параметров трёхфазного синхронного генератора 92.5 KB
  Лабораторная работа C1 по дисциплине Электрические машины Опытное определение параметров трёхфазного синхронного генератора Цель работы: Изучение методов экспериментального определения параметров установившихся и переходных режимов работы синхронного ген
13272. Ознакомление со свойствами синхронного двигателя, его угловыми и рабочими характеристиками 240.5 KB
  Лабораторная работа С4. Исследование трехфазного синхронного двигателя. Цель работы: ознакомление со свойствами синхронного двигателя его угловыми и рабочими характеристиками. Параметры двигателя: nн = 1000 об/мин Pн = 1 кВт Sн = 1.25 кВА cosн = 08 U1н = 127 В I1н = 35 А ...