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

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

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

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

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

1.Легка
aqbr495=?·374+??=?·?+??=?·?+?

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

a = 495b = 374
gcd(495, 374) =
2.Легка
aqbr372=?·300+??=?·?+??=?·?+?

Знайдіть найменше спільне кратне lcm(372, 300). Спершу використайте алгоритм Евкліда для НСД.

a = 372b = 300
lcm(372, 300) =
3.Середня

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

n = 931 = 72·19
φ(931) =
4.Середня

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

n = 1521 = 32·132
φ(1521) =
5.Складна

83 — просте. Скористайтеся малою теоремою Ферма, щоб знайти 2098308 mod 83.

p = 83k = 98308
2098308 mod 83 =
6.Складна

Скористайтеся повторним піднесенням до квадрата, щоб знайти 33127 mod 95.

a = 33k = 127n = 95
33127 mod 95 =

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

  1. 1. gcd(495, 374) = 11
  2. 2. lcm(372, 300) = 9300
  3. 3. φ(931) = 756
  4. 4. φ(1521) = 936
  5. 5. 2098308 mod 83 = 31
  6. 6. 33127 mod 95 = 52

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