Самостоятельная работа по теме:

«Теория сравнений по модулю»

Вариант 1

Задание 1. Решите сравнения: а) 7х ≡ 5 (𝑚𝑜𝑑 12)

б) 7𝑥 ≡ 9 (𝑚𝑜𝑑 10)

в) 29𝑥 ≡ 1 (𝑚𝑜𝑑 17)

Задание 2. Найти остаток от деления числа 5⁴⁰³на 101.

Задание 3. Доказать, что 43²³ + 23⁴³ кратно 66.

Вариант 2

Задание 1. Решите сравнения: а) 7х ≡ 1 (𝑚𝑜𝑑 11)

б) 5𝑥 ≡ 3 (𝑚𝑜𝑑 17)

в) 12𝑥 ≡ 7 (𝑚𝑜𝑑 13).

Задание 2. Найти остаток от деления числа 112¹⁰ на 5.

Задание 3. Докажите, что 30⁹⁹+61¹⁰⁰ делится на 31.

Задание 1.

Ответы

а) 𝑥 ≡ 8 (𝑚𝑜𝑑11)        б) 𝑥 ≡ 4 (𝑚𝑜𝑑17)        в) 𝑥 ≡ 6 (𝑚𝑜𝑑13)

Задание 2. Нам надо указать число от 0 до 4, которое сравнимо с 112¹⁰ по модулю

5. Известно, что 112 ≡ 2(𝑚𝑜𝑑 5), (112 = 5 · 22 + 2). Мы можем возводить в одну и ту же степень левую и правую части:

112¹⁰≡2¹⁰(𝑚𝑜𝑑 5), где 2¹⁰= (2⁵)² = 32²

Знаем, 32 ≡ 2(𝑚𝑜𝑑 5), (32 = 5 · 6 + 2)

Возведем в квадрат обе части:

32²≡2²(𝑚𝑜𝑑 5)

По свойству транзитивности:

11210 ≡ 4(𝑚𝑜𝑑 5)

Ответ: 4.

Задание 3. 30⁹⁹≡ (−1)⁹⁹ ≡ – 1 (𝑚𝑜𝑑 31) 61¹⁰⁰≡ (−1)¹⁰⁰ ≡ 1 (𝑚𝑜𝑑 31).

Задание 1.

а) 𝑥 ≡ 11 (𝑚𝑜𝑑12)          б) 𝑥 ≡ 7 (𝑚𝑜𝑑10)          в) 𝑥 ≡ 10 (𝑚𝑜𝑑17)

Задание 2. 101 – простое число. Числа 5 и 101 взаимно простые, а поэтому 5¹⁰⁰ ≡ 1(𝑚𝑜𝑑101). Возведем это сравнение почленно в четвертую степень. Получим: 5⁴⁰⁰ ≡ 1(𝑚𝑜𝑑101)

Кроме того, 5³ ≡ 24(mod101). Перемножим эти сравнения:

5⁴⁰³ ≡ 1(𝑚𝑜𝑑101)

Из последнего сравнения получается, что искомым остатком будет число 24.

Задание 3. 43²³ + 23⁴³ : (2 · 3 · 11)

1. 43²³ + 23⁴³ ≡ 1²³ + 1⁴³ ≡ 2 ≡ 0 (𝑚𝑜𝑑 2)

2. 43²³ + 23⁴³ ≡ 1²³ + 1⁴³ ≡ 1²³ + (−1)⁴³ ≡ 1 − 1 = 0 (𝑚𝑜𝑑 3)

3. 43²³ + 23⁴³ ≡ (−1)²³ + 1⁴³ ≡ −1 + 1 ≡ 0 (𝑚𝑜𝑑 11)