Полная версия

Главная arrow Математика, химия, физика arrow Дискретная математика. Сборник задач

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

ЭЛЕМЕНТЫ ТЕОРИИ КОДИРОВАНИЯ

Алгебра вычетов

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

В основу модулярной арифметики положена операция «деление по модулю», которая дает возможность бесконечное множество целых чисел отобразить в конечное множество классов эквивалентности (классов вычетов по модулю). Модулярная арифметика нашла широкое применение в криптографии.

При заданных целых числах х и п > 0 операция х (mod п) «деление по модулю» возвращает г — остаток от деления числа х на число п (г е [0, п - 1] и удовлетворяет условию х = кп + г, где к — целое число).

Теорема 5.1. Свойства операции «деление по модулю»

Пусть х, у и п> 0 — целые числа, причем НОД(у, п) = 1 (НОД — наибольший общий делитель; если НОД (у, п)-,тоу и п называют взаимно простыми числами). Тогда:

  • 1) (x + y)mod/7 = [(x)modtf + (y)mod/7](mod/7);
  • 2) (-x)modtf = (n -x) mod я = n - (xmodw);
  • 3) (xxy)mod/7 = [(x)mod«x(y)mod/7](modtf);
  • 4) обозначим через у-1 mod я величину, обратную к у по модулю п. Она является единственным числом из интервала [ 1, п - 1 ], удовлетворяющим условию (y_lxy)mod/7 = 1.

Как и при делении рациональных чисел, деление чисел по модулю можно заменить на умножение делимого на число, обратное делителю (если оно существует). Для любого у, если НОД(у, п) = 1, выражение (xxy-1)modtf можно заменить на (х/у) mod п.

В операции «деление по модулю» xmod« величина к не важна. Следовательно, в тождестве xmod/7 = у mod я числа х и у могут отличаться на величину, кратную п. Тогда это уравнение можно записать так х = у mod п или у = xmod«. Эта операция называется сравнение чисел по модулю, а числа х и у называют сравнимыми по модулю.

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

  • а) коммутативны (перестановка операндов не меняет результата);
  • б) ассоциативны (изменение последовательности выполнения операций результата не меняет).

Отношение сравнимости по произвольному модулю т есть отношение эквивалентности на множестве целых чисел. Это отношение эквивалентности индуцирует разбиение множества целых чисел на классы эквивалентных между собой элементов, т.е. в один класс объединяются числа, дающие при делении на т одинаковые остатки. Число классов эквивалентности в точности равно т.

Любое число из класса эквивалентности будем называть вычетом по модулю т. Совокупность вычетов, взятых по одному из каждого класса эквивалентности т, называется полной системой вычетов по модулю т (в полной системе вычетов, таким образом, всего т чисел). Непосредственно сами остатки при делении на т называются наименьшими неотрицательными вычетами и, конечно, образуют полную систему вычетов по модулю т. Вычет г называется абсолютно наименьшим, если г — наименьший среди модулей вычетов данного класса.

Любые т штук попарно несравнимых по модулю т чисел образуют полную систему вычетов по модулю т. Если а и т взаимно просты, ах пробегает полную систему вычетов по модулю т, то значения линейной формы ах + Ь, где Ь — любое целое число, тоже пробегают полную систему вычетов по модулю т.

Поскольку все числа из данного класса эквивалентности получаются из одного числа данного класса прибавлением числа, кратного т, то все числа из данного класса имеют с модулем т один и тот же наибольший общий делитель.

Приведенной системой вычетов по модулю т называется совокупность всех вычетов из полной системы, взаимно простых с модулем т.

Теорема 5.2

Для вычетов имеют место следующие утверждения:

  • 1) если а = Ь{хподт) ике2,ток-а = к- Ь(тодт);
  • 2) если к ? а = к ? Ь(тобт) и числа к, т взаимно просты, то а = Ь(тодт)',
  • 3) если а = 6(тос1 т) и к є N, то к ? а = к ? 6(тос1 к • т);
  • 4) если к ? а = к ? 6(тос1 к ? т) и к,т є N, то а = 6(тос1 т)
  • 5) если а = /Чтоб т) и с = сі(тод т), то а ± с = Ь ± г/(тос1 т);
  • 6) если а = b(modm) и с = c/(modm), то а ? с = b ? ci(modm);
  • 7) если а = Z>(modw)w/7 є іУ, шоа'1 = Z>"(modm).

Задачи

Задача 5.1. Найти результат следующих операций:

a) 27mod5;

b) -18mod 14.

Решение.

  • а) Разделим 27 на 5 — результат г- 2. Это означает, что 27mod5 = 2.
  • б) Разделим (-18) на 14 — результат г - -4. Однако мы должны прибавить модуль (14), чтобы сделать остаток неотрицательным. Мы имеем г = -4 + 14= 10. Это означает, что -18 mod 14= 10.

Задача 5.2. Составить классы вычетов по модулю 8.

Решение.

По модулю 8 имеется всего 8 классов вычетов:

  • 0, 1,2, 3, 4, 5, 6, 7 — полная система наименьших неотрицательных вычетов;
  • 1, 2, 3, 4, 5, 6, 7, 8 — полная система наименьших положительных вычетов;
  • 0, ±1, ±2, ±3, 4 — полная система абсолютно наименьших вычетов.

Задача 5.3. Верны ли следующие числовые сравнения?

  • а) 39 = 15(mod 14);
  • б) 17 = 21(mod2);
  • в) -4 = 35(mod 13);
  • г) -17 = 29(mod23).

Задача 5.4. Указать наименьшее положительное число, с которым сравнимо число а по модулю т:

  • а) а = 73, т - 8;
  • б) а - -59, т- 13;
  • в) а = 112, т = 15;
  • г) а = 75, т = 25.

Задача 5.5. Как можно охарактеризовать наименьшее неотрицательное число, сравнимое с числом а по модулю m2

Задача 5.6. Указать наименьшее по абсолютной величине число, с которым сравнимо число а по модулю т:

  • а) а = 17, т = 3;
  • б) а = 28, т = 17;
  • в) а = 67, т = 9.

Задача 5.7. Используя свойства числовых сравнений, найти наименьшее положительное х, удовлетворяющее условию:

  • а) 5х= 35(тос113);
  • б) 7х = 42(тос115);
  • в) Зх = 5(тос17);
  • г) 9х = 2(тос120).

Задача 5.8. Найти остаток от деления на т выражения 3x9 + + 3 - 4г5:

  • а) т = 14, х= 7(тос114), у = 9(тос114), г = -3(тос114);
  • б) т- 31,х = 2(тос131), у = -28(тос131), і = 25(тос131).

Задача 5.9. Показать, что по модулю 8 числа-64, -14, 38, -1,4, 11, 25, -3 составляют полную систему вычетов.

Задача 5.10. Показать, что числа 36, -11,-10, 9, -2, 11 составляют полную систему вычетов по модулю 6.

Задача 5.11. Записать полную систему вычетов по модулю 7, наименьших по абсолютной величине.

Задача 5.12. Для каких модулей числа а и -а попадают в один и тот же класс вычетов?

Задача 5.13. Доказать, что если а{, а2, ..., а5 приведенная система вычетов по модулю т > 3, то а{ + а2 + ... + = 0(тос1 т).

Задача 5.14. Доказать, что если р — простое число, то (р - 1)! = = -1(тос1 р) (теорема Вильсона).

Задача 5.15. Доказать, что если р — простое число и р = 1(шоб4), то найдется такое целое число п, что п2 + 1 делится на р.

Задача 5.16. Доказать, что если п — целое число и р — нечетный простой делитель числа п2 + 1, то р = 1(тоб4).

Задача 5.17. Доказать, что если а{, а2, ..., а$ приведенная система вычетов по модулю т > 3, то а{а2...а5 = ±1(тос1/77).

Задача 5.18. Доказать, что если аь а2, ..., ах приведенная система вычетов по модулю т > 3 и существует х ф ±1(шос1т) такое, что

х2 = ±1(шос1т), то а]а2...а!! = 1(тос1/77).

Задача 5.19. Найти остатки отделения 22000 на 13, 25, 30.

Задача 5.20. Доказать, что если а, Ь, с — целые числа и а + Ь + с делится на 30, то а5 + Ь5 + с5 делится на 30.

Задача 5.21. Доказать, что если а, Ь, с — целые числа и р — простое число, то (а + Ь)р = ар + бДтосІ р).

Задача 5.22. р и q — различные простые числа. Доказать, что рс'~1 + = 1(тос1 /?#).

Задача 5.23. Доказать, что при всех п > 1 число 2" - 1 не делится на п.

 
<<   СОДЕРЖАНИЕ   >>