Определение:
Пусть a- целое неотрицательное число, а b- число натуральное.
Разделить a на b с остатком – это значит найти такие целые неотрицательные числа p и g, что a=bg+r, при чем 0≤r<b
Из определения деления с остатком следует:
Если при делении a на b с остатком, оказывается, что r=0, то говорят, что a кратно b.
Теорема о делении с остатком.
Для любого целого неотрицательного числа a и натурального числа b существуют целые неотрицательные числа g и r, такие, что a=bg+r, при чем 0≤r<b.
Эта пара чисел g и r единственная для заданных чисел a и b.
Доказательство существования:
Пусть М- множество целых неотрицательных чисел, кратных b и не превосходящих a:
M={x| x=by, x≤a}
Значит, множество М имеет наибольший элемент.
Обозначим это наибольшее число-x0.
X0 =bg, тогда следующее за ним число b(g+1)>a.
Следовательно, найдено число g, такое, что bg≤a<b∙(g+1).
Преобразуем данное неравенство:
bg≤a<bg+b
0≤a- bg <b
Обозначим выражение a- bg =r.
Из данного равенства a- bg =r выразим a.
Имеем a=bg+r и 0≤r<b.
Это и означает, что существуют такие целые неотрицательные числа, g и r.
Доказательство его единственности:
Предположим, что такая пара чисел не единственная.
Пусть a=bg+r , 0≤r<b и
a=bg1+r1, 0≤r1<b
Условимся, что r>r1.
Тогда имеем: bg+r=bg1+r1
r-r1 =bg1-bg=b(g1-g).
Согласно условию: 0≤r1<r<b, r1-r<b,но с другой стороны r-r1 =b(g1-g).
Значит (r-r1) >b. Противоречие.
Это противоречие и доказывает, что такая пара чисел единственная.
ч.т.д.