Является ли система чисел 19, 23, 25, -19 приведенной системой вычетов по модулю 12?

Привет! Давай разберем задачи по теории чисел и арифметике. ### 1. Является ли система чисел 19, 23, 25, -19 приведенной системой вычетов по модулю 12? Приведенная система вычетов по модулю $m$ состоит из чисел, взаимно простых с $m$, количество которых равно функции Эйлера $\phi(m)$. Для $m=12$: $\phi(12) = 12(1 - 1/2)(1 - 1/3) = 12(1/2)(2/3) = 4$. Проверим числа: $19 \equiv 7 \pmod{12}$, $gcd(7, 12) = 1$ (взаимно просты) $23 \equiv 11 \pmod{12}$, $gcd(11, 12) = 1$ (взаимно просты) $25 \equiv 1 \pmod{12}$, $gcd(1, 12) = 1$ (взаимно просты) $-19 \equiv -7 \equiv 5 \pmod{12}$, $gcd(5, 12) = 1$ (взаимно просты) Все числа взаимно просты с 12, их 4 штуки, все они дают различные остатки (7, 11, 1, 5). **Ответ: Да.** ### 2. Найдите остаток от деления $5^{80} + 7^{100}$ на 13. По малой теореме Ферма $a^{12} \equiv 1 \pmod{13}$ для $a$, не кратных 13. $80 = 12 \cdot 6 + 8 \Rightarrow 5^{80} \equiv 5^8 \pmod{13}$. $5^2 = 25 \equiv -1 \pmod{13} \Rightarrow 5^8 = (5^2)^4 \equiv (-1)^4 = 1 \pmod{13}$. $100 = 12 \cdot 8 + 4 \Rightarrow 7^{100} \equiv 7^4 \pmod{13}$. $7^2 = 49 = 3 \cdot 13 + 10 \equiv -3 \pmod{13}$. $7^4 = (-3)^2 = 9 \pmod{13}$. $1 + 9 = 10$. **Ответ: 10.** ### 3. Найдите последнюю цифру числа $17^{500}$. Последняя цифра — это остаток от деления на 10. $17 \equiv 7 \pmod{10}$. Ищем $7^{500} \pmod{10}$. Циклы степеней 7: $7^1=7, 7^2=49 \equiv 9, 7^3 \equiv 3, 7^4 \equiv 1 \pmod{10}$. Цикл длины 4: $500$ делится на 4 нацело ($500 = 125 \cdot 4$). Значит, $7^{500} \equiv 7^4 \equiv 1 \pmod{10}$. **Ответ: 1.** ### 4. Зная, что число $N$ делится на $m$, найдите $x, y$, если $N=xy2, m=28$. Число $N = 100x + 10y + 2$ должно делиться на 28. $N$ должно делиться на 4 и на 7. Делимость на 4: число $y2$ должно делиться на 4. $y2 \in \{12, 32, 52, 72, 92\}$. $N = 100x + 10y + 2 = 28k$. Перебор для $y$: 1) $y=1, N=100x+12$. $100x+12 \equiv 2x+12 \equiv 2x \equiv 0 \pmod{7} \Rightarrow x=0, 7$. Если $x=7, N=712$. $712/28 = 25.4$ (нет). Если $x=0, N=12$ (нет). 2) $y=3, N=100x+32 \equiv 2x+4 \equiv 0 \pmod{7} \Rightarrow 2x \equiv -4 \equiv 3 \Rightarrow 2x \equiv 10 \Rightarrow x=5$. $N=532$. $532/28 = 19$. **Ответ: x=5, y=3.** (Есть и другие решения, например, $x=2, y=6 \Rightarrow 262$ нет, $x=7, y=9 \Rightarrow 792/28$ нет, $x=0, y=9 \Rightarrow 92/28$ нет). ### 5. Исследовать и решить сравнение 1-й степени $8x = 20 \pmod{12}$. $gcd(8, 12) = 4$. Так как 20 делится на 4 ($20/4=5$), решения есть (ровно 4 решения). Сократим на 4: $2x \equiv 5 \pmod{3}$. $2x \equiv 2 \pmod{3} \Rightarrow x \equiv 1 \pmod{3}$. Решения: $x = 1, 4, 7, 10$. **Ответ: 1, 4, 7, 10.** ### 6. Трубы 3 м и 4.5 м, длина 105 м, минимальное количество швов. Чтобы минимизировать швы, нужно использовать как можно больше длинных труб (4.5 м). Пусть $x$ — кол-во труб 4.5 м, $y$ — кол-во труб 3 м. $4.5x + 3y = 105$. $1.5(3x + 2y) = 105 \Rightarrow 3x + 2y = 70$. Нужно максимизировать $x$. $3x = 70 - 2y$. Так как $3x$ делится на 3, то $(70 - 2y)$ должно делиться на 3. $70 - 2y = 70 - 2(35 - k) = 2k$ (не совсем так, проще подбором). При $y=2, 3x=66, x=22$. (Всего труб $22+2=24$). При $y=5, 3x=60, x=20$. (Всего труб $20+5=25$). Максимальное $x$ при $y=2$. Количество труб 24, значит, количество швов $24-1=23$. **Ответ: 23 шва.**