ЛАБОРАТОРНАЯ РАБОТА №5

Тема:         Основы теории чисел

Цель:         изучить основные понятия теории чисел.

Оборудование: персональный компьютер, ОС Windows 7.

Вид работы: групповой

Время выполнения: 2 часа

Теоретический материал

Целые числа а и b сравнимы по модулю n (целому числу, неравному нулю), если выполняется условие

а=b+kn

для некоторого целого числа k. В этом случае обычно используется следующая запись:

а = b {mod n}.

Сравнимость а и b по модулю и означает, что n делит (а - b) нацело:

n | (а-b).

Если b>=0,a = b {mod n} и |b|<n, то b называют вычетом числа а по модулю n. Вычет равен остатку от целочисленного деления числа а на число n. Операцию нахождения вычета числа а по модулю n называют приведением числа а по модулю n.

Очевидно, что

-a {mod n} =-а + n {mod n};

n = 0 {mod n}.

Примеры:

3 + 10 {mod 12} = 1 {mod 12} («арифметика» часов);

-5 {mod 7} = 2 {mod 7}.

Полным набором вычетов по модулю n называется множество целых чисел от нуля до n - 1:

{0, 1, 2, ...,«- 1}.

Вычеты по модулю n с применением операций сложения и умножения образуют коммутативное кольцо, в котором справедливы законы ассоциативности, коммутативности и дистрибутивности. Операции над вычетами обладают также свойствами:

• аддитивности

(а + b) {mod n) = (a {mod n) + b {mod n}) {mod n);

• мультипликативности

(ab) {mod n} = (a {mod n}b {mod n}) {mod n};

• сохранения степени

a^b {mod n) = {a {mod n})^b {mod n}.

Данные свойства операций над вычетами позволяют либо сначала вычислять вычеты, а затем выполнять операцию, либо сначала выполнять операцию, а затем вычислять вычеты. Операция вычисления вычета является гомоморфным отображением кольца целых чисел в кольцо вычетов по модулю n.

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

Например: НОД(56, 98) = 14 и НОД(150, 19) = 1.

Простым числом называется целое число, которое делится без остатка только на единицу и на себя. Например: 7, 13, 139.

Целые числа а и b называются взаимно простыми, если выполняется условие НОД(a, b) = 1.

Целое число у называется мультипликативно обратным целому числу х по модулю n, если выполняется условие ху {mod n} = 1. Мультипликативно обратное целое число существует только тогда, когда х и n — взаимно простые числа. Если целые числа а и n не являются взаимно простыми, то сравнение а^-1 = х {mod n} не имеет решения. Если из полного набора вычетов по модулю n выделить подмножество вычетов, взаимно простых с n, то получим приведенный набор вычетов. Например:

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10} — полный набор вычетов по модулю 11. Приведенным набором вычетов будет то же подмножество целых чисел, за исключением нуля;

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} — полный набор вычетов по модулю 10. Приведенным набором вычетов будет подмножество целых чисел {1, 3, 7, 9}.

Очевидно, что если n является простым числом, то приведенный набор вычетов по модулю n всегда содержит (n - 1) элемент (все целые числа от единицы до n - 1).

Значением функции Эйлера φ(n) будет число элементов в приведенном наборе вычетов по модулю n. Если n — простое число, то φ(n) = n - 1 и φ(n²) = n(n - 1). Если n - pq (р и q — простые числа и р ≠ q), то φ(n) = (р - 1)(q - 1).

В соответствии с малой теоремой Ферма, если а — целое число, n — простое число и НОД (а, n) = 1, то

a ^n-l= 1 {mod n}.

Обобщением малой теоремы Ферма является теорема Эйлера: если целые числа а и n являются взаимно простыми (НОД(a, n) = 1), то

a ^φ(n) = 1 {mod n}.

Пример 1. Найти НОД чисел 420, 126, 525.

I способ: Найдем НОД чисел 420 и 126, используя алгоритм Евклида. 

Получим 420=126*3+42.

126=42*3.

Следовательно, (420, 126)=42. Теперь найдем (42, 525).

525=42*12+21

42=2*21.

Следовательно, (420, 126, 525) =21. 

II способ: Вычислим НОД с помощью канонического разложения на простые числа.

Имеем

420|2          126|2           525|5

210|2           63 |3           105|5

105|5           21 |3            21 |3

21  |3             7 |7              7 |7

7    |7              1                 1

1

Таким образом 420 = ,  126 = ,  525 = , следовательно (420, 126, 525) = =21, [420, 126, 525] = =6300.

Ответ: 21.

Задания

1.       Найти наибольшее целое число, дающее при делении на 13 частное 17.

2.       Доказать, что: 1) квадрат нечетного натурального числа при делении на 8 дает остаток 1; 2) сумма квадратов двух последовательных натуральных чисел при делении на 4 дает остаток 1.

3.       Доказать теорему: если каждое из двух целых чисел при делении на натуральное число  дает остаток 1, то их произведение при делении на дает остаток 1.

4.       Доказать: если сумма двух трехзначных чисел делится на 37, то и шестизначное число, составленное приписыванием одного из них к другому, также делится на 37.

5.       Найти НОД И НОК чисел 187, 153, 221.

Контрольные вопросы:

1.       Что называется вычетом целого числа по некоторому модулю?

2.       Что называют наибольшим общим делителем целых чисел?

3.       Каким образом выполняются операции над вычетами7

4.       Почему операции над вычетами находят широкое применение в криптографии?

Скачано с www.znanio.ru