Division Algorithm
For any integer and positive integer
, there exist unique integers
and
such that
and
.
Proof
Existence: Let The intersection of the sets
and
is non-empty and has a positive element (take
). By the Well Ordering Principle , it contains a least element. Let
equal the value of the least element and let
equal the respective value of
. Therefore,
. Now we prove that
by contradiction. Let
. Then
. However, this leads to a contradiction (
is supposed to be the smallest positive value that can be expressed in the form
, but
is smaller, positive, and can also be expressed in this manner). Therefore,
.
Uniqueness: Let . Then
. Then
is a multiple of
. However, since
and
, then
. The only multiple of
that
can equal is
. Therefore,
. Since
,
.
Divisibility
If and
, then we say
or "
divides
". Note that every integer divides
.
This article is a stub. Help us out by expanding it.