ПРАКТИЧЕСКОЕ ЗАНЯТИЕ №13

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

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

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

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

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

Теоретические сведения

Целые числа а и 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.    Почему операции над вычетами находят широкое применение в криптографии?

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