Деление с остатком

Разделить с остатком целое неотрицательное число а на натуральное в- это значит найти такие целые неотрицательные числа q и r, что а=в*q + r, где 0≤ r<в. Особенности остатка: при делении а на в остаток есть число меньше делителя в. Поэтому при делении на в могут получаться в различных остатков: 1, 2, 3, …, в-1. П: разобъем мн.чисел {1,2,3,4,5,…,19,20} на классы по признаку «иметь один и тот же остаток при делении на 3». Т.к.при делении на 3 может получиться три различных остатка: 0,1,2, то данное мн.можно разбить на три класса. А0={3,6,9,12,15,18}- класс чисел, дающих при делении на 3 остаток 0; А1={1,4,7,10,13,16,19}- остаток 1; А2={2,5,8,11,14,17,20}- остаток 2. Теорема: Для любого целого неотриц.числа а и натурального в существуют целые неотриц.числа q и r такие, что

а = b*q + r и 0 ≤r<b, причём пара (q ,r)- единственная. Док-во: существование- если а=0, то пара (0,0) существует и удовлетворяет условию а=в*q + r и 0≤ r<в. Пусть а>0 и М- мн.чисел, кратных в, больших чем а: М={вп|п∈N, вп>а}, где вп>0,т.к.а>0. Поскольку М сN, то по принципу наименьшего числа мн.М содержит наименьшее число вk, удовлетворяющее условию вk>а. Так как k∈N, то (k-1)∈N0. Это значит, что в*( k-1) есть целое неотриц.число, кратное в. По св-ву монотонности умножения в*( k-1)< в*k. Значит, в*( k-1)∉М, следовательно, в*( k-1)≤а. Обозначим числа (k-1)= q, а а-в q= r, причём r∈N0,т.к.а≥в q. Существование доказано. Докажем, что r<в. Предположим, что r≥в. Получим а-в*q≥в,т.е.а≥в*q+в= в*(q+1). Так как q+1=k, то а≥вk, что противоречит тому, что вк наименьшее и вк>а. Значит, а=в q+r и r<в. Единственность- докажем, что если а=в*q1 +r1 и а=в* q2+r2,то q1=q2 и r1= r2. Доказательство проведём методом от противного. Предположим, что для чисел а и в существуют две пары чисел (q1,r1) и (q2,r2) такие, что а=в q1+ r1 и а=в q2+r2, где r1<в и r2<в. Причём q1≠ q2 и r1≠ r2. Тогда получим: в* q1+ r1= в* q2+r2. Пусть r1≥ r2. Тогда r1- r2=в* q2-в* q1= в(q2- q1) и r1- r2∈N0. Значит, (r1- r2) делится на в. Но r1- r2<в, т.к. r1<в. Значит, r1- r2=0, следовательно, r1-=r2. Но q2-q1=( r1- r2):в. Так как r1- r2=0, то q2-q1 тоже равно 0, следовательно, q2=q1. Получили противоречие с предположением о том, что q1≠q2 и r1≠ r2, доказывающее единственность пары (q,r). Частные случаи деления с остатком: 1.если а=в, то q=1, r=0. Действительно, а=в*1+0, а=в. 2.если а<в, то q=0, r=а. Действительно, а=в*0+а, а=а.