Робочий аркуш «Теорія чисел і арифметика за модулем» з відповідями

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

Новий робочий аркушТренуватися онлайн з підказками

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

Ім’я: ____________________   Дата: ____________

1.Легка
aqbr47=?·32+??=?·?+??=?·?+??=?·?+?

Скористайтеся алгоритмом Евкліда, щоб знайти gcd(47, 32).

a = 47b = 32
gcd(47, 32) =
2.Легка

Знайдіть (999·909 + 318) mod 5, не перемножуючи великих чисел: спершу зведіть.

n = 5
(999·909 + 318) mod 5 =
3.Середня

Знайдіть обернений до 26 за модулем 29: число x, де 0 < x < 29 і 26·x ≡ 1 (mod 29).

a = 26n = 29
26−1 mod 29 =
4.Середня

Знайдіть функцію Ейлера φ(1573), кількість цілих чисел від 1 до 1573, взаємно простих з 1573.

n = 1573 = 112·13
φ(1573) =
5.Складна
mc = me​ mod n200m = cd​ mod n?(n, e) = (301, 11)d

Ключ RSA використовує p = 7, q = 43 і e = 11. Розшифруйте шифротекст c = 200: знайдіть повідомлення m.

p = 7q = 43e = 11c = 200
m =
6.Складна

Розв’яжіть 6x ≡ 2 (mod 16). Дайте найменший додатний розв’язок x.

6x ≡ 2 (mod 16)
x =

Ключ відповідей

  1. 1. gcd(47, 32) = 1
  2. 2. (999·909 + 318) mod 5 = 4
  3. 3. 26−1 mod 29 = 19
  4. 4. φ(1573) = 1320
  5. 5. m = 205
  6. 6. x = 3

Повні покрокові розв’язки: тренуйте цю тему на examproblems.com.