Задание 1
Найдите остаток от деления числа:
1) 8^30 на 55;
2)5^21 на 77;
3)6^43 на 44.
задание 2
Доказать, что если
50a+8b+c≡0 (mod 21), то a+b+8c≡0 (mod 21)

Предыдущий
вопрос Следующий
вопрос

Задание 1
1) Для нахождения остатка от деления числа 8^30 на 55 можно воспользоваться теоремой Эйлера. Найдем остаток от деления 8^30 на 11 (т.к. 55 = 5*11):

8^30 mod 11 = 8^10 mod 11 8^10 mod 11 8^10 mod 11 = 8^10 mod 11 8^10 mod 11 8^10 mod 11

По малой теореме Ферма:

8^10 mod 11 = 8^(11-1) mod 11 = 8^10 mod 11 = 1

Таким образом:

8^30 mod 11 = 1 1 1 = 1

Теперь найдем остаток от деления 8^30 на 5:

8^30 mod 5 = (8 mod 5)^30 mod 5 = 3^30 mod 5

3^30 mod 5 = 4

Таким образом, 8^30 ≡ 1 (mod 11) и 8^30 ≡ 4 (mod 5). Составим систему уравнений:

8^30 ≡ 1 (mod 11)
8^30 ≡ 4 (mod 5)

Используя КТО (Китайскую теорему об остатках), найдем остаток от деления 8^30 на 55:

x ≡ 1 (mod 11)
x ≡ 4 (mod 5)

Чтобы свести задачу к решению системы линейных сравнений, запишем 5k + 4 = 11m + 1:

5k≡7(mod11)
k≡7*5^-1(mod11)
k≡2(mod11)

Подставим k=2 в уравнение x=5k+4:

x=5*2+4
x=14
x≡14(mod55)

Ответ: остаток от деления 8^30 на 55 равен 14.

2) Аналогично посчитаем:

5^21 mod 77 = 5^(11+10) mod 77 = 5^11 mod 77 * 5^10 mod 77

5^11 mod 77 = 5^1 mod 77 = 5
5^10 mod 77 = (5^5)^2 mod 77 = 18^2 mod 77 = 324 mod 77 = 46

Итак, 5^21 mod 77 = 5 * 46 = 230 mod 77 = 76

Ответ: остаток от деления 5^21 на 77 равен 76.

3) Найдем остаток от деления 6^43 на 44:

6^43 mod 44 = 6^(22+21) mod 44 = 6^22 mod 44 * 6^21 mod 44

По малой теореме Ферма:

6^22 mod 11 = 6^(44-1) mod 44 = 6^43 mod 44 = -1

Таким образом:

6^43 mod 44 = -1 * 6 ≡ 38 (mod 44)

Ответ: остаток от деления 6^43 на 44 равен 38.

Задание 2
Доказательство:

Из условия имеем:

50a + 8b + c ≡ 0 (mod 21)

Умножим обе части на 8:

8(50a + 8b + c) ≡ 8 * 0 (mod 21)

400a + 64b + 8c ≡ 0 (mod 21)

Учитывая, что 400 ≡ 19 (mod 21) и 64 ≡ 1 (mod 21), получим:

19a + b + 8c ≡ 0 (mod 21)

Таким образом, a + b + 8c ≡ 0 (mod 21)

Доказано.