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), а  – довільне ціле число.

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

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

  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.  


 

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

48168. ФОРМИ МІЖНАРОДНИХ ЕКОНОМІЧНИХ ВІДНОСИН 73 KB
  Інші форми міжнародних економічних відносин Список використаних джерел: Основи економічної теорії: Підручник За ред. Сучасний рівень міждержавних економічних зв'язків характеризується: трансформацією двосторонніх міжнародних економічних відносин у багатосторонні значним поглибленням міжнародного поділу праці у світовому господарстві; зростанням масштабів і якісними змінами характеру традиційної міжнародної торгівлі із суто комерційної вона перетворюється в інструмент обслуговування національних виробничих процесів; інтенсифікацією і...
48169. ЕКОНОМІЧНІ АСПЕКТИ ГЛОБАЛЬНИХ ПРОБЛЕМ 76.5 KB
  Причини виникнення сутність і класифікація глобальних проблем 2. Глобальні проблеми: і шляхи їх розв'язання людством 3. Міжнародне співробітництво в розв'язанні глобальних проблем та розвитку світогосподарства Список використаних джерел: Основи економічної теорії: Підручник За ред.
48170. Політологія як наука 552 KB
  Політологія ж займається переважно інституційним аспектом політики устроєм і діяльністю держави усього механізму політичної влади а також процесів які характеризують боротьбу за цю владу. Термін політика politics означає швидше процес повязаний із реалізацією і завоюванням державної влади в окремому суспільстві. Емпіричні науки про організацію влади прийняття рішень роботи апарату. Політика як відповідна форма що забезпечує отримання використання та реалізацію влади.
48171. ПОЛІТОЛОГІЯ ЯК НАУКА І НАВЧАЛЬНА ДИСЦИПЛІНА 1.08 MB
  Витоки політичної думки сягають своїм корінням у найдавніші часи у IV III тис. Періодизація визрівання і розвитку світової політичної думки включає в себе чотири основних етапи. Грецькі філософи започаткували вивчення політичної мови й термінології досліджували такі політичні соціальні моральні цінності як свобода справедливість добро та ін. Початок звільнення політичної думки від релігійноетичної форми повязаний з поглядами видатного італійського мислителя епохи Відродження Нікколо Макіавеллі 1469 1527 котрі були...
48173. Понятие и предмет предпринимательского права 107 KB
  Понятие предпринимательской деятельности Принципы предпринимательской деятельности РФ ФЗ о лицензировании отдельных видов деятельности Классификация юридических лиц Отношения возникающие в процессе государственного регулирования предпринимательской деятельности государственный контроль в виде налогового контроля финансового контроля сертификации стандартизации и тд Отношения организационно-имущественного характера которые создают условия для осуществления бизнеса создание реорганизация ликвидация.
48174. Правознавство. Курс лекцій 1.38 MB
  Курс лекцій МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ ЧЕРКАСЬКИЙ ДЕРЖАВНИЙ БІЗНЕСКОЛЕДЖ Н. Основи Конституційного права України 30 4. Загальна характеристика Конституції України її місце в системі законодавства 30 4. Громадянство України як один із інститутів конституційного права 32 4.
48175. Механизмы, лежащие в основе законов Г. Менделя 895 KB
  Отсутствие взаимодействия генов. Отсутствие сцепления генов. Гены отвечающие за развитие разных признаков например А и В не сцеплены между собой в группе сцепления генов а сочетания их аллелей образуются случайным образом в равных соотношениях. Расположение генов отвечающих за изучаемые признаки в разных парах хромосом несцепленность.
48176. Прибуток та рентабельність 58 KB
  Рентабельність це відносний показник прибутковості який характеризує ефективність витрат підприємства загалом або ефективність виробництва окремих видів продукції. Для їх розрахунку використовуються показники чистого доходу виручки від реалізації валового прибутку прибутку від операційної діяльності від звичайної діяльності а також чистого прибутку які співвідносяться із загальною сумою витрат на виробництво та реалізацію собівартістю виробленої реалізованої продукції собівартістю одиниці продукції тощо. Розрізняють наступні...