Unit 3: Principles of Integer Properties

Table of Contents

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.

Common Mistake: When `a` is negative, like `a = -29, b = 5`, saying `q = -5, r = -4` is wrong, because the remainder `r` must be non-negative (0 ≤ r < b).

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:

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.

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:

Properties of Congruences

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

Real-world Application: This is the basis of "clock arithmetic" (e.g., 5 hours after 10:00 is 3:00, because `10 + 5 = 15 ≡ 3 (mod 12)`). It is also fundamental to modern cryptography, such as the RSA algorithm.