1.Легка
Знайдіть найменше спільне кратне lcm(825, 195). Спершу використайте алгоритм Евкліда для НСД.
a = 825b = 195
lcm(825, 195) =
Робочий аркуш «Теорія чисел і арифметика за модулем» з відповідями
2.Легка
Скористайтеся алгоритмом Евкліда, щоб знайти gcd(651, 609).
a = 651b = 609
gcd(651, 609) =
3.Середня
Знайдіть обернений до 36 за модулем 59: число x, де 0 < x < 59 і 36·x ≡ 1 (mod 59).
a = 36n = 59
36−1 mod 59 =
4.Середня
Знайдіть найменше додатне ціле x, де x ≡ 6 (mod 7) і x ≡ 3 (mod 13).
x ≡ 6 (mod 7)x ≡ 3 (mod 13)
x =
5.Складна
Ключ RSA використовує прості числа p = 13 і q = 23 та відкритий показник e = 19. Знайдіть закритий показник d (0 < d < φ(n)).
p = 13q = 23e = 19
d =
6.Складна
Скористайтеся повторним піднесенням до квадрата, щоб знайти 3975 mod 44.
a = 39k = 75n = 44
3975 mod 44 =
Ключ відповідей
- 1. lcm(825, 195) = 10725
- 2. gcd(651, 609) = 21
- 3. 36−1 mod 59 = 41
- 4. x = 55
- 5. d = 139
- 6. 3975 mod 44 = 43
Повні покрокові розв’язки: тренуйте цю тему на examproblems.com.