9.1 Divisibility, Congruence, and Euclid's Algorithm: The Fundamental Structure of Integers

Circular buffers, periodic tasks, and sharded indexing all fold integers back into finite ranges. To correctly handle negative numbers, reduction, and modular inverses, we must begin with divisibility and remainder arithmetic, rather than treating the language's % as a complete definition of mathematics.

Divisibility

For integers a,b, if there exists an integer k such that:

b = a*k

then a divides b, denoted as a|b. When discussing divisors, it is typically required that a≠0 be non-zero.

Basic properties:

If a|b and a|c, then a|(x*b + y*c) for any x, y ∈ ℤ
If a|b and b|c, then a|c
If a|b and b|a, then |a| = |b|

Divisibility is antisymmetric on positive integers and gives a partial order there. On all integers, both 2|-2 and -2|2 hold although 2≠-2, so antisymmetry fails. Identifying a with -a gives a partial order on the resulting classes; antisymmetry is an exact property, not an approximation.

Remainder Arithmetic

Given integers a and a positive integer m, there exists a unique integer pair (q,r) such that:

a = q × m + r
0 ≤ r < m

r is the commonly used non-negative least remainder in mathematics.

For example:

-1 = (-1) × 5 + 4

Thus, -1 mod 5=4.

Language-based remainder operations may use truncated division toward zero. In Java, -1 % 5 == -1; if a floor modulus corresponding to a positive modulus is required, use:

public class RemainderDemo {
    public static void main(String[] args) {
        System.out.println(-1 % 5);               // -1
        System.out.println(Math.floorMod(-1, 5)); // 4
        int x = Integer.MAX_VALUE - 1;
        int m = Integer.MAX_VALUE;
        System.out.println(((x % m) + m) % m);    // -3: addition overflow
        System.out.println(Math.floorMod(x, m));  // 2147483646
    }
}

General ((x % m)+m)%m must also account for addition overflow in some languages and fixed-width integers. Prefer explicit APIs provided by standard libraries.

Save as RemainderDemo.java and compile with Java 21. A floorMod result has the divisor’s sign or is zero; this lesson uses positive moduli. A zero divisor throws ArithmeticException.

Congruence is an equivalence relation

a≡b (mod m) ⇔ m|(a-b)

Equivalently, the non-negative remainder of a,b divided by the positive integer m is the same.

Congruence is reflexive, symmetric, and transitive, so it divides integers into m residue classes:

[0],[1],...,[m-1]

Integers modulo m are denoted as ℤ/mℤ. Elements are not individual integers but equivalence classes; during computation, 0...m-1 is typically chosen as a representative.

Greatest Common Divisor

For (a,b)≠(0,0), gcd(a,b) is the largest positive integer that divides both a,b; by convention:

gcd(a,0) = |a|
gcd(0,0) = 0   // Common convention; specific API behavior should be verified

If gcd(a,b)=1, then a,b are coprime. Coprimality does not require that either number be prime. For example, 8 and 15 are coprime.

Euclid Algorithm

If:

a = qb + r

then:

gcd(a, b) = gcd(b, r)

because any number that divides a,b also divides a-qb=r; the reverse is equally true.

Algorithm:

gcd(a, b):
  a = |a|, b = |b|
  while b ≠ 0:
    (a, b) = (b, a mod b)
  return a

Each remainder is smaller than the positive divisor, so the process terminates. For a≥b>0, it takes O(1+log b) remainder operations; consecutive Fibonacci numbers attain the worst asymptotic growth. This counts operations, without treating arbitrary-length division as constant time. Fixed-width implementations must also handle the minimum negative value when taking absolute values.

Example:

gcd(252, 105)
= gcd(105, 42)
= gcd(42, 21)
= gcd(21, 0)
= 21

Bézout's Identity

If d=gcd(a,b), then there exist integers x,y such that:

ax + by = d

The extended Euclidean algorithm computes the greatest common divisor (gcd) of two numbers and simultaneously finds the coefficients that satisfy this equation.

Working backwards through the previous example:

21 = 105 - 2·42
  = 105 - 2·(252 - 2·105)
  = 5·105 - 2·252

Thus, one solution is x=-2,y=5.

This Python 3 implementation uses arbitrary-precision integers. Each current remainder stays a linear combination of the original absolute inputs; the final coefficients restore their signs:

def extended_gcd(a, b):
    r0, r1 = abs(a), abs(b)
    x0, x1, y0, y1 = 1, 0, 0, 1
    while r1:
        q = r0 // r1
        r0, r1 = r1, r0 - q * r1
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return r0, x0 if a >= 0 else -x0, y0 if b >= 0 else -y0

for a, b in [(252, 105), (-252, 105), (0, 0)]:
    d, x, y = extended_gcd(a, b)
    assert a * x + b * y == d
    print((d, x, y))
# (21, -2, 5)
# (21, 2, 5)
# (0, 1, 0)

Bézout also provides a condition for the linear Diophantine equation:

ax + by = c

For (a,b)≠(0,0), integer solutions exist exactly when gcd(a,b)|c. If both coefficients are zero, solutions exist exactly when c=0. Since gcd(18,30)=6 does not divide 7, 18x+30y=7 has no integer solution.

Least Common Multiple

For non-zero integers:

lcm(a,b) = |a × b| / gcd(a,b)

A program implementation should perform the division before the multiplication:

|a / gcd(a,b) × b|

This reduces the risk of intermediate product overflow, though the final result may still exceed the range of the data type.

If either input is zero, lcm is conventionally zero. Handle that branch first to avoid 0/gcd(0,0) when both inputs are zero.

Two tasks have positive periods a and b units of time. If both tasks start at the same point in time, the shortest positive period until they coincide again is lcm(a,b). If their starting phases differ, the problem must be solved using a system of congruences, this will be covered in the next lesson.

Completion Checklist

1. Compute gcd(123456,789012) and write out the Euclidean steps;
2. Use the extended algorithm to find a Bézout coefficient set;
3. Determine whether 18x+30y=7 has integer solutions;
4. Compare the results of Java % and Math.floorMod when handling negative numbers;
5. Prove the transitivity of congruence relations;
6. Formulate congruence conditions for two periodic tasks with different phases.

References

• MIT Mathematics for Computer Science
• Java SE 21: Math.floorMod