67807

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

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

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

Определение. Если для целых чисел и в кольце целых чисел существует такое число, что , то говорят, что целое число делится на целое число, и пишут. При этом число называется делимым или кратным числа, число – делителем числа, число – частным. Любое целое число всегда можно разделить с остатком на произвольное целое число.

Русский

2014-09-15

399.5 KB

2 чел.

PAGE   \* MERGEFORMAT 3

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

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

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

Краткие теоретические сведения.

1. Делимость целых чисел.

Определение. Если для целых чисел  и  в кольце целых чисел  существует такое число , что , то говорят, что целое число  делится на целое число , и пишут . При этом число  называется делимым или кратным числа , число  – делителем числа , число  – частным.

Любое целое число  всегда можно разделить с остатком на произвольное целое число .

Теорема (о делении с остатком). Для любых целых чисел  и , где , всегда существует одна и только одна пара целых чисел и таких, что

, где .

Число  называется неполным частным, а  – остатком от деления  на .

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

Целые числа  и  называются взаимно простыми, если  .

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

Очевидно, .

Наибольший общий делитель двух целых чисел   вычисляется с помощью т.н. алгоритма Евклида. В этом алгоритме основную роль играет операция деления чисел с остатком, т.е. представление вида , где . Алгоритм Евклида задаётся последовательностью равенств

, ;

, ;

, ;

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

, ;

, .

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

Теорема (о линейном представлении НОД) Для любых целых чисел  и  уравнение

,

где  – наибольший общий делитель целых чисел  и , всегда имеет решение в целых числах.

Пусть и – решения уравнения . Запись

,       (2)

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

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

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

Действуя в классической схеме (1) обратным ходом снизу вверх, имеем

(идем по цепочке равенств (1), выражая из каждого следующего равенства

остаток и подставляя его в полученное к этому моменту выражение)

....

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

.

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

, потому что ,

, потому что .

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

Остатки

Частные

1

0

0

1

Получение новых значений компонент  наборов  показано в третьей строке таблицы (клетки выделены): из числа в первой клетке вычитается число во второй клетке, умноженное на число, что стоит справа от него во второй строке, результат записывается в третью клетку. Аналогично выполняется операция для нахождения компонент  в четвёртой строке.

Линейным диофантовым уравнением называется уравнение вида

,             (3)

где  – неизвестные, .

Пусть . Диофантово уравнение (3) имеет решение тогда и только тогда, когда . При этом общее решение определяется формулой:

,   ,       (4)

где  – частное решение уравнения (3), а  – произвольное целое число.

Решения уравнений  и  могут отличаться только знаками.

Алгоритм решения диофантова уравнения следующий:

  1.  По алгоритму Евклида находим НОД . Если , то уравнение (3) имеет решения. Если , то уравнение (3) решений не имеет.
  2.  По расширенному алгоритму Евклида находим линейное представление НОД : . С использованием следствия 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.  Каккпроверить натуральное число на простоту?


 

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

35491. Информационные системы. Шпаргалка 163 KB
  Для информационных систем характерно Многоаспектность Многофункциональность Различные сферы применения Поэтому классифицировать информационные системы сложно. Могут быть системы: автоматизированные слабо автоматизированные и не автоматизированные Уровень интеграции информационных процессов. Могут быть системы: интегрированные процессные информационные системы выполненные на единой информационной базе и обеспечивающие сквозную связь между всеми элементами ИС. Онги поддерживают управление бизнеспроцессами ...
35492. Информационные системы и информационные технологии 93.5 KB
  TPS Транзакционные технологии TPS Trnsctions Processing Systems предназначены для ежедневной обработки поступающих в виде документов сообщений счета акты накладные и т. MIS Технологии поддерживающие управленческие функции MIS Mngement Informtion Systems предназначены для автоматизации планирования деятельности предприятия организации а также для организации контроля над ходом выполнения планов производства и реализации продукции. DSS Технологии аналитической обработки данных DSS Decision Support Systems...
35493. Автоматизированные системы управления (АСУ) 784 KB
  Основные компоненты АСУ ТП предназначена для выработки и реализации управляющего воздействия на ТОУ и представляют собой человекомашинную систему обеспечивающую автоматизированный сбор и обработку информации необходимой для оптимизации управления объектом в соответствии с принятым критерием. Основные компоненты: КТС комплекс технических средств; СПО системное программное обеспечение; ФАУ функциональные алгоритмы управления. Информационное обеспечение информация характеризующая состояние системы управления системы классификации и...
35494. Моделирование информационных систем 702.5 KB
  Модели гидродинамики потоков в аппаратах. Модель идеального смешения Условия физической реализуемости этой модели выполняются если во всем потоке происходит полное смешение частиц потока. Модели идеального перемешивания соответствует апериодическое звено 1го порядка и имеет передаточную функцию. Математическое описание модели: где: с концентрация вещества; τ время пребывания частиц в реакторе; ω линейная скорость потока; х координата.
35495. Системы автоматизированной работы (САР) 5.7 MB
  Разомкнутые САР системы в которых входными воздействиями управляющего устройства являются только внешние задающие и возмущающие воздействия; при этом значение выходной величины ОУ может существенно отклоняться от его заданного значения в силу изменения внутренних свойств ОУ параметров САР. Устойчивость САР свойство системы возвращаться в исходное состояние равновесия после прекращения воздействия выведшего систему из этого состояния. уравнения частотные определяют связь между устойчивостью системы и формой частотных характеристик...
35496. Представление данных в электронных таблицах в виде диаграмм и графиков 1.25 MB
  Что нужно знать: что такое столбчатая линейчатая и круговая диаграмма какую информацию можно получить с каждой из них адрес ячейки в электронных таблицах состоит из имени столбца и следующего за ним номера строки например C15 формулы в электронных таблицах начинаются знаком = равно знаки и ^ в формулах означают соответственно сложение вычитание умножение деление и возведение в степень в заданиях ЕГЭ могут использоваться стандартные функции СУММ сумма СРЗНАЧ среднее значение МИН минимальное...
35497. КУЛЬТУРА СОВЕТСКОЙ ПОВСЕДНЕВНОСТИ И ЕЕ ОТРАЖЕНИЕ В САТИРЕ 1920–х ГОДОВ 209.5 KB
  Анализ специфики репрезентации советской повседневности в сатире. Как известно, в этот период истории происходила, навязываемая сверху, смена отношений к повседневности: «борьба» старого и нового быта. Ключевым вопросом в нашей курсовой работе является осмысление противостояния традиционного уклада жизни и навязываемыми сверху принципами «новой жизни».
35498. Архитектура ЭВМ 175.5 KB
  MOV регистр значение означает: поместить в регистр выбранное значение. MOV AX10 MOV BX5 MOV CX7 MOV DX15 ADD AXBX ADD AXCX SUB AXDX INT 20 Арифметические операции Операции умножить и разделить выполняются только для регистра AX. 100 MOV AX0 103 MOV BX1 106 MOV CXA 109 ADD AXBX 10C INC BX 10E DEC CX 110 JNZ 109 112 INT 20 Сохранение и загрузка файлов 1 Общие сведения. MOV AH01 включение ввода символа.
35499. Основы алгоритмизации и программирования 495.5 KB
  ЧИСЛА Целые числа: SHOPTINT 120127 BYTE 0 255 перечисляемые типы INTEGER 32768 32767 WORD 0: 65535 LONCINT 231 231 Действительные: SINGLE 1038 7 знаков после запятой REAL 1038 11 знаков DOUBLE 100300 19 знаков EXTENDED 104900 19 знаков. USES список библиотек; подключение библиотек или модулей TYPE описание; описание собственных типов данных CONST список постоянных VAR список переменных BEGIN начало программы END. конец программы Обязательными элементами являются только PROGRAM BEGIN END. PROGRAM FIRST;...