∆ Определение 1. Числа $a$ и $b$ сравнимы по модулю $m\ne0$, если $a-b⋮ m$. Обозначение: $a\equiv b\pmod m$.

Задача 1. Докажите, что $a$ сравнимо с $b$ по модулю $m$ тогда и только тогда, когда остаток от деления $a$ на $m$ равен остатку от деления $b$ на $m$. Отправить решение

Задача 2. Докажите, что сравнимость по модулю $m$ является отношением эквивалентности. Отправить решение

Задача 3. Докажите, что для любых $a_1$, $a_2$, $b_1$, $b_2$, $c$, $m$ 1) $a_1\equiv b_1\pmod m,\;a_2\equiv b_2\pmod m \Longrightarrow a_1+a_2\equiv b_1+b_2\pmod m$; 2) $a_1\equiv b_1\pmod m \Longrightarrow ca_1\equiv cb_1\pmod m$; 3) $a_1\equiv b_1\pmod m,\;a_2\equiv b_2\pmod m \Longrightarrow a_1a_2\equiv b_1b_2\pmod m$. Отправить решение

Задача 4. Докажите, что если $a\equiv b\pmod m$, то 1) $a^n\equiv b^n\pmod m$ для любого неотрицательного $n$; 2*) для любого многочлена $f(x)$ с целыми коэффициентами $f(a)\equiv f(b)\pmod m$. Отправить решение

Задача 5. Верно ли, что если $a\equiv b\pmod m$ и $a,b\geqslant0$, то $2^a\equiv 2^b\pmod m$? Отправить решение

Задача 6. Пусть $\overline{\mathstrut a_na_{n-1}\ldots a_1a_0}$ — десятичная запись числа $x$. Докажите, что 1) $x\equiv a_0+\ldots+a_n\pmod3$, $x\equiv a_0+\ldots+a_n\pmod9$; 2) $x\equiv a_0\pmod2$, $x\equiv a_0\pmod5$; 3) $x\equiv a_0-a_1+\ldots+(-1)^n a_n\pmod{11}$. Отправить решение

Задача 7. Если $x$ нечётно, то $x^2\equiv1\pmod 8$. Отправить решение

Задача 8. * Докажите, что следующие уравнения не имеют ненулевых решений в целых числах 1) $x^2 + y^2 = 3z^2$;  2) $x^2 + y^2 + z^2 = 4t^2$. Отправить решение

Задача 9. * Докажите, что существует бесконечно много натуральных чисел, не представимых в виде суммы трёх 1) квадратов; 2) кубов натуральных чисел. Отправить решение

Задача 10. Решите сравнения: а) 3x ≡ 1 (mod 7); б) 6x ≡ 5 (mod 9); в) 4x ≡2 (mod 10). Отправить решение

Задача 11. Сравнение $ax\equiv b\pmod m$ имеет решение тогда и только тогда, когда $b⋮НОД(a,m)$. Отправить решение

Задача 12. Пусть $p$ — простое число, $a\not\equiv0\pmod p$, тогда сравнение $ax\equiv b\pmod p$ имеет решение, причём любые два решения этого сравнения сравнимы по модулю $p$. Отправить решение

Задача 13. * (Китайская теорема об остатках) Пусть числа $a_1$, $a_2$, ..., $a_n$ попарно взаимно просты. Тогда для любых $x_1$, $x_2$, ..., $x_n$ найдётся $x$ такое, что \begin{equation*} x\equiv x_i\pmod {a_i}   i=1,\ldots,n, \end{equation*} причём любые два числа, удовлетворяющие этому условию, сравнимы по модулю $a_1 a_2 \ldots a_n$. Отправить решение

Задача 14. * Найдите все решения системы сравнений \begin{equation*} \left\{ \begin{aligned} x&\equiv3\pmod5 \\ x&\equiv1\pmod7 \\ x&\equiv4\pmod9. \end{aligned} \right. \end{equation*} Отправить решение

Задача 15. Пусть $p$ — простое число, докажите, что 1) $C_p^k⋮ p$ при $0< k< p$; 2) $(a+b)^p\equiv a^p+b^p\pmod p$; 3) (малая теорема Ферма)  $ (a^p-a ) ⋮ p$. Отправить решение

Задача 16. * (теорема Вильсона) Пусть $p$ — простое число, тогда $(p-1)!\equiv-1\pmod p$. Отправить решение

Задача 17. Какими правильными многоугольниками можно замостить плоскость? Отправить решение

Задача 18. Докажите, что имеется бесконечное количество простых чисел вида 1) $4n+3$;  2*) $4n+1$;  3**) $an+b$, где $НОД(a,b)=1$. Отправить решение

Задача 19. * Найдите количество решений сравнения $x^2\equiv1\pmod n$ при 1) простом $n>2$;  2) $n=2$;  3) произвольном $n$. Отправить решение