Unit 3: Principles of Integer Properties

Well-Ordering Property of Positive Integers

The Well-Ordering Property states:
Every non-empty set of positive integers contains a least (smallest) element.

This property seems obvious, but it's a fundamental axiom of the integers. It's what allows mathematical induction to work.

Example: The set S = {5, 12, 3, 29} is non-empty and contains positive integers. It has a least element, 3.

Non-Example: This property does not hold for the set of positive rational numbers. The set S = {1/2, 1/3, 1/4, ...} has no least element (it approaches 0, but 0 is not in the set).

Division Algorithm

The Division Algorithm states:
For any two integers a (the dividend) and b (the divisor), with b > 0, there exist unique integers q (the quotient) and r (the remainder) such that:
a = bq + r
and 0 ≤ r < b

This is just the formal statement of elementary school long division.

• Example: If a = 29 and b = 5, then:
  29 = 5(5) + 4
  Here, q = 5 and r = 4. The condition `0 ≤ 4 < 5` is satisfied.
• Example (with negative 'a'): If a = -29 and b = 5, then:
  -29 = 5(-6) + 1
  Here, q = -6 and r = 1. The condition `0 ≤ 1 < 5` is satisfied.

Divisibility of Integers

An integer b is said to divide an integer a if there exists some integer k such that a = bk.

We write this as b | a (read as "b divides a").

This is the same as saying that `a` is a multiple of `b`, or that the remainder `r` from the division algorithm is 0.

Examples:

• 4 | 20 because `20 = 4(5)`.
• 7 | -21 because `-21 = 7(-3)`.
• 5 | 0 because `0 = 5(0)`.
• 3 ∤ 10 (3 does not divide 10) because there is no integer `k` such that `10 = 3k`.

Euclidean Algorithm and GCD

Greatest Common Divisor (GCD)

The Greatest Common Divisor (GCD) of two integers `a` and `b` (not both zero) is the largest positive integer that divides both `a` and `b`. It is denoted gcd(a, b).

Example: The divisors of 12 are {1, 2, 3, 4, 6, 12}. The divisors of 18 are {1, 2, 3, 6, 9, 18}. The *common* divisors are {1, 2, 3, 6}. The *greatest* of these is 6. So, gcd(12, 18) = 6.

Euclidean Algorithm

This is a fast and efficient algorithm to find the GCD of two integers by repeatedly applying the Division Algorithm.

Method: To find `gcd(a, b)` (assume `a > b > 0`):

1. Divide `a` by `b` to get remainder `r₁`: a = bq₁ + r₁
2. Divide `b` by `r₁` to get remainder `r₂`: b = r₁q₂ + r₂
3. Divide `r₁` by `r₂` to get remainder `r₃`: r₁ = r₂q₃ + r₃
4. ...continue this process until the remainder is 0.
5. The last non-zero remainder is the GCD.

Example: Find `gcd(1071, 462)`

 1071 = 462(2) + 147 462 = 147(3) + 21 147 = 21(7) + 0