The Division Algorithm

Proposition

This is trivial to prove, but we use it in the next proposition

Bounds by Divisibility (BBD)

Proposition

For all integers and , if divides and is not , then

Proof

Let and be arbitrary integers, and assume .
Since , then .
Since , then and
Therefore,
Then we have
Which gives
Which gives

Proposition

For all integers , and for all positive integers , there exists unique integers and such that:

Proof of Uniqueness

Let be an arbitrary integer, and be an arbitrary positive integer

Assume and are integers such that with , and and are integers such that . with

Adding the inequalities gives:

We also have

This means , so by definition of divisibility, there exists an integer such that

Substituting (1) gives

Dividing through by (which is positive) gives:

Since is an integer,
This gives
Hence
Then we also have , and since we have