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

The last non-zero remainder is 21. Therefore, gcd(1071, 462) = 21.

Prime Number

A positive integer p > 1 is called a prime number if its only positive divisors are 1 and p.

A positive integer greater than 1 that is not prime is called composite.

• Prime examples: 2, 3, 5, 7, 11, 13, 17, ... (Note: 2 is the only even prime)
• Composite examples: 4, 6, 8, 9, 10, 12, ...
• The number 1 is neither prime nor composite; it is a "unit".

Fundamental Theorem of Arithmetic

The Fundamental Theorem of Arithmetic states:
Every integer n > 1 can be expressed as a product of primes. This factorization is unique, apart from the order of the factors.

This theorem is the "holy grail" of number theory. It means every number has a unique "fingerprint" of prime factors.

Example: `720`

720 = 72 × 10 = (8 × 9) × (2 × 5) = (2³ × 3²) × (2 × 5) = 2⁴ × 3² × 5¹

No matter how you start factoring (e.g., 720 = 12 x 60), you will always end up with four 2s, two 3s, and one 5.

Congruence Relation and Properties

Congruence Relation

Let m be a positive integer (called the modulus). Two integers a and b are said to be congruent modulo m if m divides their difference (a - b).
We write this as: a ≡ b (mod m)

An equivalent (and often more useful) way to think about it is:
"a ≡ b (mod m)" means "a and b have the same remainder when divided by m."

Examples:

• 17 ≡ 2 (mod 5)
  Reason 1: `(17 - 2) = 15`, and `5 | 15`.
  Reason 2: 17 ÷ 5 gives remainder 2. And 2 ÷ 5 gives remainder 2.
• 14 ≡ 0 (mod 7) (This is the same as saying `7 | 14`)
• 10 ≡ -1 (mod 11) (because `(10 - (-1)) = 11`, which is divisible by 11)

Properties of Congruences

Congruence acts very much like equality. If a ≡ b (mod m) and c ≡ d (mod m), then:

• Addition: a + c ≡ b + d (mod m)
• Subtraction: a - c ≡ b - d (mod m)
• Multiplication: a · c ≡ b · d (mod m)
• Power: aᵏ ≡ bᵏ (mod m) for any positive integer k.