67808

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

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

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

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

Украинкский

2014-09-15

416.5 KB

5 чел.

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.  


 

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

40159. ОПТИМАЛЬНЫЙ РАДИОПРИЕМ КАК СТАТИСТИЧЕСКАЯ ЗАДАЧА 548 KB
  Введение в теорию оптимального радиоприема ОПТИМАЛЬНЫЙ РАДИОПРИЕМ КАК СТАТИСТИЧЕСКАЯ ЗАДАЧА Помехоустойчивость и ее основные задачи Особенность радиоприёма состоит в том что наряду с сигналами через антенную систему в приёмное устройство поступают разнообразные помехи. Количественно помехоустойчивость оценивается с помощью различных показателей использующих вероятностное описание помех и сигнала. Например применяются такие показатели как отношение сигнал шум на входе и выходе приёмного устройства вероятность правильного обнаружения...
40160. ИМПУЛЬСНЫЕ УСИЛИТЕЛИ МОЩНОСТИ 340.5 KB
  Основными определяющими факторами являются длительность фронта и среза импульса коллекторного перехода стокового тока транзистора и тип нагрузки активной и активно – индуктивной. Первый способ применяется когда возможно произвольно варьировать параметрами нагрузки. Тогда параметры нагрузки выбираются таким образом чтобы к моменту коммутации автоматически выполнялось условие Uкл=0 или Iкл=0. Второй способ используется если параметры нагрузки строго заданы и состоит во введении в схему дополнительных цепей искусственно разносящих во...
40161. ЦИФРОВАЯ ЭЛЕКТРОНИКА. МАТЕМАТИЧЕСКОЕ ОПИСАНИЕ ЦИФРОВЫХ УСТРОЙСТВ 295 KB
  2 Основные способы записи функций алгебры логики ФАЛ Функции алгебры логики ФАЛ – зависимость выходных переменных Zi выраженная через совокупность входных переменных х1х2хn. Логические устройства – работа которых описывается с помощью ФАЛ. 1 Описание ФАЛ в виде таблице истинности табл. Описание ФАЛ в виде алгебраического выражения: а логическое сложение ИЛИ – дизъюнкция б логическое умножение И – конъюнкция в отрицание инверсия НЕ если х = 1 то ;если х = 0 то Дизъюнктивная нормальная форма ДНФ –...
40162. ОСНОВНЫЕ ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ 378 KB
  По принципу действия: комбинационные – автоматы без памяти, входные сигналы которых определяются действующей на входе комбинацией переменных; последовательные – автоматы с памятью, выходные сигналы которых определяются не только действующей комбинацией переменных, но и предыдущей.
40163. МИНИМИЗАЦИЯ ЛОГИЧЕСКИХ УСТРОЙСТВ 518 KB
  Минимизация с применением карт Вейча Карты Вейча – это прямоугольная таблица число клеток в которой для ФАЛ n – переменных равно 2n каждой из клеток поставлен в соответствие набор входных переменных причем рядом расположенным клеткам соответствуют соседние наборы входных переменных а в самих клетках записаны значения функции определенные для этих кодов. На карте Вейча ФАЛ n – переменных выделяют прямоугольные области объединяющие выбранные значения функции 0 или 1. Каждой из выделенных областей соответствует k – куб исходной ФАЛ...
40164. КОМБИНАЦИОННЫЕ ЛОГИЧЕСКИЕ УСТРОЙСТВА 587.5 KB
  2 При построении логических устройств на реальной элементной базе возникают следующие задачи: а число входов ЛЭ больше числа переменных входящих в реализуемую с их помощью ФАЛ; б число входов ЛЭ меньше числа переменных входящих в реализуемую с их помощью ФАЛ. Решение задач: а Число входов больше требуемого. Следовательно что уменьшит фактическое число входов ЛЭ можно подавая на неиспользуемые входы сигналы пассивных логических констант: 0 – для элементов ИЛИНЕ 1 – для элементов ИНЕ; б число входов ЛЭ меньше требуемого. Сравнивая...
40165. ПОСЛЕДОВАТЕЛЬНОСТНЫЕ ЛОГИЧЕСКИЕ УСТРОЙСТВА 658.5 KB
  По типу используемых информационных входов триггеры классифицируются: RS D T JK VD и VT – триггеры где R – раздельный вход сброса триггера Q=0; К – вход сброса универсального триггера Q=0; J – вход установки универсального триггера Q=1; Т – счетный вход триггера ; D – информационный вход переключения триггера в состояние соответствующее логическому уровню на этом входе; С – управляющий или синхронизирующий вход; V – вход блокирования работы триггера и он долго сохраняет информацию. Для переключения триггера на его прямой вход...
40166. РЕГИСТРЫ. Параллельный регистр 85.5 KB
  Осуществляет следующие функции: хранение информации сдвиг информации вправо или влево запись информации в последовательной и параллельной формах выдача хранимой информации в последовательной и параллельной формах. Классификация: 1 По способу приема информации: последовательные сдвигающие в которые информация записывается и считывается только в последовательной форме; параллельные статические в которые информация записывается и считывается только в параллельной форме; последовательнопараллельные в которые информация записывается...