67808

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

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

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

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

Украинкский

2014-09-15

416.5 KB

6 чел.

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.  


 

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

31168. Назовите характеристики коммуникатора, повышающие убедительность сообщения 22 KB
  2 прием: Надежным считается альтернативные коммуникаторы когда передается инфа кот замалчивают либо противоположная той кот передают в офиц СМИ 3 прием: Независимость координатора. 4 прием: Использование нескольких ораторов. 5прием: ускорение речи зритель не успевает продумать сообщение Суще понятие эффект спящего: Влияние кредитного коммуникатора сохрся в течение 1 месяца затем резко падает.
31169. Перечислите характеристики убедительного сообщения 21.5 KB
  Также эмоция радости может вызывать положит ассоциации с темой сообщения анекдоты веселые истории. лучше всего запоминаются сообщения в кот речь идет о трагических ситуациях. В случае использования эмоции страха можно столкнуться с эффектом бумеранга: последствием кот может быть забывание сообщения.
31170. Что такое когнитивный диссонанс 23 KB
  Практически не случается ни того ни другого процесс затухает не добравшись даже до стадии дискомфорта в головах 95 населения прекрасно уживаются полностью противоречивые факты и представления о них и ничего. Также возможен вариант с безусловным рефлекторным отторжением вызывающей такой дискомфорт инфы.
31175. ЯЗЫКОВЫЕ ОСОБЕННОСТИ АНГЛИЙСКИХ ГАЗЕТ 20.52 KB
  Язык газеты, безусловно, обладает определенной спецификой, отличающей его от языка художественной или научной литературы, от разговорной речи. Это является следствием длительного отбора языковых, выразительных средств.
31176. Каковы особенности массовой коммуникации 21.5 KB
  2 сообщение имеет ряд свв: соц актуальность соц значимость модность вечные темы быстрая забываемость периодичность регулярное возвращение к некотор темам доступность занимательность эмоциональность имеет игровой харакр коммерциализация. :оперативность эмоциональность возможность использ в фоновом режиме. :оперативность эмоциональность заразительность эффект присутствия. эмоциональность слаб оперативность.