🍫
Из жизниРаздели $23$ шоколадные дольки поровну между $5$ друзьями. Каждому достанется по $4$ дольки, а $3$ дольки останутся лишними — их нельзя разделить поровну дальше. Записывают так: $23 = 5\cdot4+3$. Число $4$ здесь — неполное частное, а $3$ — остаток. Такое деление «с остатком» работает для любых целых чисел, а его частный случай, когда остаток равен нулю, — обычная делимость.
Делимость натуральных чисел
Натуральное $n$ делится нацело на натуральное $m$, если существует натуральное $q$ такое, что $n=mq$; оба числа $m$ и $q$ называют делителями $n$. У каждого $n>1$ есть делители $1$ и $n$; если других делителей нет — число называют простым, если есть — составным (число $1$ не относится ни к тем, ни к другим).
🧱
Основная теорема арифметикиКаждое натуральное число $n>1$ можно единственным образом представить в виде произведения простых чисел, например $36 = 2^2\cdot3^2$.
Деление с остатком
Разделить с остатком целое $a$ на $b\ne0$ — значит найти целые $q$ (неполное частное) и $r$ (остаток), такие что
$$a = bq + r, \qquad 0 \le r < |b|$$
Если $r=0$, говорят, что $a$ делится на $b$ нацело.
1
Существование: перебирая числа $b\cdot0,\,b\cdot1,\,b\cdot2,\ldots$, по архимедову свойству найдётся такое $k$, что $bk \le a < b(k{+}1)$ — тогда $q=k$, $r=a-bk$.
2
Единственность: если бы существовали два представления $a=bq_1+r_1=bq_2+r_2$, то $r_1-r_2=b(q_2-q_1)$ — а так как $0\le r_1,r_2
На интерактиве справа подвигай $a$ и $b$ — увидишь, как число $a$ раскладывается на полные группы по $b$ (неполное частное $q$) и остаток $r$.
Классы остатков
При делении на натуральное $m$ возможны только $m$ разных остатков: $0,1,\ldots,m-1$, поэтому множество $\mathbb{Z}$ разбивается на $m$ непересекающихся классов чисел с одинаковым остатком. Например, все числа, дающие остаток $2$ при делении на $3$ и остаток $1$ при делении на $2$, — это в точности числа вида $6n+5$.
Запомни
🧠
Делимость целых чисел
- $a = bq + r$, $0 \le r < |b|$ — деление с остатком, пара $(q,r)$ всегда существует и единственна;
- $r=0$ означает, что $a$ делится на $b$ нацело;
- каждое $n>1$ раскладывается в произведение простых чисел единственным способом;
- при делении на $m$ бывает ровно $m$ разных остатков.