Теория чисел и модульная арифметика: лист заданий с ответами

Бесплатный лист заданий для печати по теме «Теория чисел и модульная арифметика»: 6 задач от простых до экзаменационного уровня, с ответами. Распечатайте его или сохраните как PDF.

Новый лист заданийЗаниматься онлайн с подсказками

Для преподавателей: можно бесплатно печатать, копировать и использовать на занятиях. Каждый новый лист содержит новые значения и собственные ответы. Будем благодарны за ссылку на ExamProblems на странице вашего курса.

Имя: ____________________   Дата: ____________

1.Лёгкая
01234567891011mod 12

Найдите (−66) mod 12, остаток r, для которого 0 ≤ r < 12.

a = −66n = 12
(−66) mod 12 =
2.Лёгкая
aqbr87=?·30+??=?·?+??=?·?+?

Используйте алгоритм Евклида, чтобы найти gcd(87, 30).

a = 87b = 30
gcd(87, 30) =
3.Средняя

Найдите функцию Эйлера φ(49), число целых чисел от 1 до 49, взаимно простых с 49.

n = 49 = 72
φ(49) =
4.Средняя

Найдите функцию Эйлера φ(45), число целых чисел от 1 до 45, взаимно простых с 45.

n = 45 = 32·5
φ(45) =
5.Сложная

97 — простое число. Используйте малую теорему Ферма, чтобы найти 304161 mod 97.

p = 97k = 4161
304161 mod 97 =
6.Сложная

Используйте многократное возведение в квадрат, чтобы найти 761 mod 69.

a = 7k = 61n = 69
761 mod 69 =

Ответы

  1. 1. (−66) mod 12 = 6
  2. 2. gcd(87, 30) = 3
  3. 3. φ(49) = 42
  4. 4. φ(45) = 24
  5. 5. 304161 mod 97 = 30
  6. 6. 761 mod 69 = 19

Полные пошаговые решения: занимайтесь этой темой на examproblems.com.