Соглашение. Все числа в этом листке предполагаются целыми.

Задача 1. Докажите, что для любых $a$ и $b\ne0$ существуют и единственны $q$ и $r$ такие, что: (1) $a=qb+r$; (2) $0\leqslant r < |b|$. Отправить решение

∆ Определение 1. Такие $q$ и $r$ называются соответственно частным и остатком при делении $a$ на $b$.

Задача 2. Найдите частное и остаток при делении 1) $-17$ на $4$; 2) $23$ на $-7$; 3) $-1$ на $-5$. Отправить решение

Задача 3. Какие частные могут получиться при делении числа $59$? Отправить решение

Задача 4. Найдите частное и остаток при делении 1) $n^2$ на $n+1$; 2) $n^2+n+1$ на $n-1$; 3) $2^{100}-1$ на $2^7-1$; 4*) $2^{m}-1$ на $2^{n}-1$. Отправить решение

Задача 5. * 1) Покажите, что $a^{2k+1}+1$ всегда делится на $a+1$ без остатка. 2) Найдите остаток от деления $a^{2k}+1$ на $a+1$. Отправить решение

∆ Определение 2. Наибольшим общим делителем чисел $a$ и $b$ называется наибольшее из таких чисел $d$, что $a⋮ d$, $b⋮ d$. Обозначение: $НОД(a,b)$.

Задача 6. Докажите, что для любых $a$ и $b$ ($a\ne 0$ или $b\ne 0$) $НОД(a,b)$ существует и единственен. Отправить решение

Задача 7. Докажите, что для любых $a$, $b$ и $c$ ($a\ne0$ или $b\ne0$: 1) $НОД(a,b)\geqslant1$; 2) $НОД(a,b)=|a|\Longleftrightarrow b⋮ a$; 3) $НОД(a,ca+b)=НОД(a,b)$. Отправить решение

Задача 8. (алгоритм Евклида) Рассмотрим следующий процесс. Пусть $(a,b)$ — пара положительных чисел такая, что $a\geqslant b$. Она заменяется на пару $(b,r)$, где $r$ — остаток от деления $a$ на $b$. Пара $(b,r)$ заменяется по тому же правилу, и так далее. Процесс завершается, когда получается пара вида $(d,0)$. Покажите, что 1) процесс всегда завершается; 2) $d=НОД(a,b)$. Отправить решение

Задача 9. Вычислите при помощи алгоритма Евклида 1) $НОД(91,147)$;   2) $НОД(-144,-233)$. Отправить решение

Задача 10. Пусть $0< a< 1000$, $0< b< 1000$. Верно ли, что алгоритм Евклида закончится после не более, чем 1) $14$; 2) $13$ шагов? Отправить решение

Задача 11. Покажите, как при помощи алгоритма Евклида можно по произвольным $a$ и $b$ найти такие $k$ и $l$, что $ak +bl =НОД(a, b)$. Отправить решение

Задача 12. Докажите, что уравнение $ax+by=d$ имеет решение в целых числах тогда и только тогда, когда $d⋮НОД(a,b)$. В частности, $НОД(a,b)$ — это наименьшее натуральное число, представимое в виде $ax+by$. Отправить решение

Задача 13. Пусть $(x_0,y_0)$ — решение уравнения \begin{equation*} ax+by=d. \end{equation*} Пусть $a_0$ и $b_0$ — такие числа, что $НОД(a,b)a_0=a$, $НОД(a,b)b_0=b$. Покажите, что каждое решение уравнения $ax+by=d$ имеет вид \begin{equation*} x=x_0+b_0t,  y=y_0-a_0t, \end{equation*} где $t\in\mathbb Z$. Отправить решение

Задача 14. Решите уравнения: 1) $121x+91y=1$;   2) $-343x+119y=42$;   3) $111x-740y=11$. Отправить решение

Задача 15. Даны углы в $32^\circ$ и $25^\circ$. Постройте угол в $1^\circ$. Отправить решение

Задача 16. Докажите, что если $p$ — простое, то либо $a$ делится на $p$, либо найдутся такие $x$ и $y$, что $ax+py=1$. Отправить решение

Задача 17. Пусть $p$ — простое число. Докажите, что если $ab⋮ p$, то $a⋮ p$ или $b⋮ p$. Отправить решение

Задача 18. Докажите основную теорему арифметики (задача 16-3) листка «Целые числа 1»). Отправить решение

∆ Определение 3. Наименьшим общим кратным чисел $a$ и $b$ называется наименьшее из таких положительных чисел $d$, что $d⋮ a$, $d⋮ b$. Обозначение: $НОК(a,b)$.

Задача 19. Докажите, что для любых $a$ и $b$ ($a^2 + b^2 \ne0$) 1) $НОК(a,b)$ существует и единственен. 2) $НОК(a,b)\cdotНОД(a,b)=ab$. Отправить решение

Задача 20. Найдите $НОК(12,15)$, $НОК(120, 45)$. Отправить решение

Задача 21. * Найдите все пары целых чисел $x$, $y$ такие, что $x^y=y^x$. Отправить решение

Задача 22. * Есть шоколадка в форме равностороннего треугольника со стороной $n$, разделённая бороздками на равносторонние треугольники со стороной $1$. Играют двое. За ход можно отломить от шоколадки треугольный кусок вдоль бороздки, съесть его, а остаток передать противнику. Тот, кто получит последний кусок — треугольник со стороной $1$, — победитель. Тот, кто не может сделать ход, досрочно проигрывает. Кто выигрывает при правильной игре? Отправить решение