Math Notes - Divisibility Properties

Introduction

The division of two integers results in a quotient and a remainder.  Divisibility properties describe when, under certain circumstances an integer divides evenly into another.  Divisibility proofs often rely on the well-ordering principle to determine if an integer is positive, negative, or zero.

Well-Ordering Principle

The well-ordering principle states:

Every nonempty subset S of the positive integers has a least element.

Basic Theorem for Division of Integers

Theorem 1: The Division Algorithm. For any b > 0 and any a, there exist unique integers q and r with 0 ≤ r < b such that a = b ⋅ q + r.

Let a and b > 0 be distinct integers. 
This is a multi-part proof.
Part 1: prove the existence of q and 0 ≤ r < b such that a = b ⋅ q + r.

r = a - b ⋅ q | Solve for r.
Let C = {i | a - b ⋅ i ≥ 0 : a - b ⋅ i} | Set of possible solutions for r.
| Prove that the least value for r is the solution for r.
a ≥ 0 ⇒ a + 0 = a + b ⋅ 0 ≥ 0 | Show that set C is non-empty.
(a + b ⋅ 0) ∈ C | Criteria for set C satisfied
C is non-empty | C has at least 1 member
Show that 0 ≤ r < b |
it suffices to show that r < b | r ∈ C, 0 ≤ r
q + 1 > q | property of numbers
b ⋅ (q + 1) > b ⋅ q | multiplying by number > 0 maintains inequality
b ⋅ q + b > b ⋅ q | algebra
- b ⋅ q - b < - b ⋅ q | Multiplying by -1 changes inequality
a - b ⋅ q - b < a - b ⋅ q | adding maintains inequality
a - b ⋅ q - b < r | substitution
a - b ⋅ q – b ∉ C    | r is the least element of C,
| by the well-ordering principle,
| any integer less than r is not an element of C:
a - b ⋅ q – b = a - b ⋅ (q + 1) | algebra
a - b ⋅ q – b ∈ C ∨ a - b ⋅ q – b < 0 | a - b ⋅ q – b has the form of elements of C
a - b ⋅ q – b ∉ C ∧
(a - b ⋅ q – b ∈ C ∨ a - b ⋅ q – b < 0) 		| combine previous lines
a - b ⋅ q – b ∉ C ∧
(a - b ⋅ q – b ∉ C ⇒ a - b ⋅ q – b < 0) 		| (p ⇒ q) ≡ (not p ⇒ q)
a - b ⋅ q – b < 0 | p ∧ (p ⇒ q) ⇒ q (modus ponens)
r – b < 0 | r = (a - b ⋅ q)
r < b | add b doesn't change inequality
| end of part I

Part 2: In the equation a = b ⋅ q + r, show that r and q are unique.  Suppose that r′ and q′ are two integers such that r′ = a - b ⋅ q′ and  0 ≤ r′ < b.  Must show that q = q′.

Suppose that q < q′ ∨ q > q′ | Assume ¬(q = q′)
q < q′ ≡ q + 1 ≤ q′ ∧ q > q′ ≡ q – 1 ≥ q′ | q < q + 1
q + 1 ≤ q′ ∨ q – 1 ≥ q′ | substitute equivalences in given
q ≤ q′ - 1 ∨ q ≥ q′ + 1 | add 1 to both sides preserves the inequality
|
for q ≤ q′ – 1: |
q ≤ q′ – 1 | given
b ⋅ q ≤ b ⋅ (q′ – 1) | order preserved, b > 0
- b ⋅ q ≥ - b ⋅ (q′ – 1) | negating changes order
a - b ⋅ q ≥ a - b ⋅ (q′ – 1) | adding preserves order
a - b ⋅ q ≥ a - b ⋅ q′ + b | algebra
r ≥ r′ + b | substitution
r ≥ b | r′ ∈ C ⇒ r′ > 0
b > r ≥ b | 0 < r < b
false | order violation
|
for q ≥ q′ + 1 |
q ≥ q′ + 1 | given
b ⋅ q ≥ b ⋅ (q′ + 1) | order preserved, b > 0
- b ⋅ q ≤ - b ⋅ (q′ + 1) | negating changes order
a - b ⋅ q ≤ a - b ⋅ (q′ + 1) | adding preserves order
a - b ⋅ q ≤ a - b ⋅ q′ - b | algebra
r ≤ r′ - b | substitution
r < 0 | r′ - b < 0
0 ≤ r < 0 | r ∈ C, 0 ≤ r
false | order violation
|
q < q′ ∨ q > q′ ⇒ false |
q = q′ | a ≤ b ∨ a = b ∨ a ≥ b
End of Proof

References:

Long, Calvin T., 1965, Elementary Introduction to Number Theory, Boston, MA: D. C. Heath and Company

Gries, David and Schneider, Fred B., 1993, A Logical Approach to Discrete Math, New York, NY: Springer-Verlag