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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая
aqbr118=?·50+??=?·?+??=?·?+??=?·?+??=?·?+?

Найдите наименьшее общее кратное lcm(118, 50). Сначала найдите НОД по алгоритму Евклида.

a = 118b = 50
lcm(118, 50) =
2.Лёгкая
aqbr459=?·279+??=?·?+??=?·?+??=?·?+??=?·?+??=?·?+?

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

a = 459b = 279
gcd(459, 279) =
3.Средняя

Найдите обратный к 17 по модулю 47: число x, для которого 0 < x < 47 и 17·x ≡ 1 (mod 47).

a = 17n = 47
17−1 mod 47 =
4.Средняя

Найдите обратный к 14 по модулю 41: число x, для которого 0 < x < 41 и 14·x ≡ 1 (mod 41).

a = 14n = 41
14−1 mod 41 =
5.Сложная
mc = me​ mod ncm = cd​ mod nm(n, e) = (1517, 13)d = ?

В ключе RSA используются простые числа p = 37 и q = 41 и открытый показатель e = 13. Найдите закрытый показатель d (0 < d < φ(n)).

p = 37q = 41e = 13
d =
6.Сложная

Сколько решений, N, имеет сравнение 14x ≡ 2 (mod 20) среди {0, 1, …, 19}?

14x ≡ 2 (mod 20)
N =

Ответы

  1. 1. lcm(118, 50) = 2950
  2. 2. gcd(459, 279) = 9
  3. 3. 17−1 mod 47 = 36
  4. 4. 14−1 mod 41 = 3
  5. 5. d = 997
  6. 6. N = 2

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