Division Algorithm
From AoPSWiki
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.
