Learning Objectives

• State the Quotient–Remainder Theorem and explain its uniqueness.
• Compute quotients and remainders by hand and in Java.
• Connect Java's / and % operators to the mathematical definitions.
• Prove the existence and uniqueness of $q$ and $r$.
• Identify how remainder arithmetic appears in hashing, cyclic buffers and indexing.

Concept Overview

The Quotient–Remainder Theorem (also called the Division Algorithm, though it is a theorem, not an algorithm) is one of the foundational results in number theory:

Theorem. For any integers $n$ and $d$ with $d > 0$, there exist unique integers $q$ (the quotient) and $r$ (the remainder) such that

$n = d \cdot q + r \qquad \text{and} \qquad 0 \leq r < d.$

This simple result is the engine behind modular arithmetic, hashing, cyclic structures, and much of what programmers do with the % operator.

Why this matters in CS:

• Hashing: hash(key) % tableSize maps keys to buckets.
• Cyclic buffers: (index + 1) % capacity wraps around.
• Round-robin scheduling: task assignment cycles through processors.
• Clock arithmetic: hours, minutes, and seconds all wrap around.

Formal Notation

• $n$ is the dividend, $d$ is the divisor (with $d > 0$).
• $q = \lfloor n / d \rfloor$ is the quotient.
• $r = n \bmod d = n - d \cdot q$ is the remainder, satisfying $0 \leq r < d$.
• We write $n \bmod d$ (or $n \mod d$) for the remainder.
• The congruence $a \equiv b \pmod{m}$ means $m \mid (a - b)$, i.e., $a$ and $b$ leave the same remainder when divided by $m$.

Common pitfall: In Java, n % d can return a negative value when n is negative (e.g., (-7) % 3 == -1 in Java, but mathematically $-7 \bmod 3 = 2$). To get the mathematical remainder:

int mathMod(int n, int d) {
    int r = n % d;
    return (r < 0) ? r + d : r;
}

Worked Examples

Example 1: Basic Computation — Discrete Math

Problem: Find $q$ and $r$ when $n = 137$ and $d = 5$.

Solution:

Check: $5 \cdot 27 = 135$, and $137 - 135 = 2$. Since $0 \leq 2 < 5$, we have $q = 27$ and $r = 2$. $\blacksquare$

Example 2: Java Translation — QuotientRemainder Demo

Problem: Implement a method that returns the quotient and remainder as a pair.

public class QuotRemDemo {

    /**
     * Returns {quotient, remainder} for n divided by d.
     * Mathematical definition: n = d*q + r, 0 <= r < d.
     */
    public static int[] quotRem(int n, int d) {
        if (d <= 0) throw new IllegalArgumentException("d must be positive");
        // Java's / truncates toward zero, not toward negative infinity.
        // For non-negative n, this matches floor division.
        int q = Math.floorDiv(n, d);   // floor(n / d)
        int r = Math.floorMod(n, d);   // n - d * floor(n / d), always in [0, d)
        return new int[]{q, r};
    }

    public static void main(String[] args) {
        int[][] tests = {{137, 5}, {13, 5}, {0, 7}, {-7, 3}, {-20, 6}, {100, 10}};
        for (int[] t : tests) {
            int[] qr = quotRem(t[0], t[1]);
            System.out.printf("%4d = %d × %d + %d   (0 ≤ %d < %d)%n",
                t[0], t[1], qr[0], qr[1], qr[1], t[1]);
        }
    }
}

Sample output:

 137 = 5 × 27 + 2   (0 ≤ 2 < 5)
  13 = 5 × 2 + 3   (0 ≤ 3 < 5)
   0 = 7 × 0 + 0   (0 ≤ 0 < 7)
  -7 = 3 × -3 + 2   (0 ≤ 2 < 3)
 -20 = 6 × -4 + 4   (0 ≤ 4 < 6)
 100 = 10 × 10 + 0   (0 ≤ 0 < 10)

Key code ↔ math connection:

Example 3: Combined — Proving and Verifying Negative Operands

Problem: Show that Math.floorMod(n, d) always satisfies $0 \leq r < d$ and $n = d \cdot q + r$.

Proof sketch: Math.floorDiv(n, d) computes $\lfloor n/d \rfloor$. Setting $r = n - d \cdot \lfloor n/d \rfloor$:

• By definition, $n/d - 1 < \lfloor n/d \rfloor \leq n/d$.
• Multiply by $-d$: $-n \leq -d \cdot \lfloor n/d \rfloor < -n + d$.
• Add $n$: $0 \leq n - d \cdot \lfloor n/d \rfloor < d$.
• So $0 \leq r < d$. $\blacksquare$

Java verification:

public static void verifyFloorMod() {
    for (int n = -1000; n <= 1000; n++) {
        for (int d = 1; d <= 20; d++) {
            int q = Math.floorDiv(n, d);
            int r = Math.floorMod(n, d);
            assert n == d * q + r : "Equation failed for n=" + n + ", d=" + d;
            assert r >= 0 && r < d : "Range failed for n=" + n + ", d=" + d;
        }
    }
    System.out.println("FloorMod verified for n in [-1000,1000], d in [1,20]");
}

Example 4: Existence Proof

Problem: Prove that for any $n \in \mathbb{Z}$ and $d > 0$, there exist $q, r \in \mathbb{Z}$ with $n = dq + r$ and $0 \leq r < d$.

Proof. Consider the set $S = \{n - dk \mid k \in \mathbb{Z},\, n - dk \geq 0\}$.

$S$ is non-empty: If $n \geq 0$, take $k = 0$ to get $n \in S$. If $n < 0$, take $k = n$ (note $n - dn = n(1 - d) \geq 0$ since $n < 0$ and $1 - d \leq 0$).

By the Well-Ordering Principle, $S$ has a smallest element. Call it $r = n - dq$ for some $q$.

$r < d$: Suppose for contradiction that $r \geq d$. Then $r - d = n - d(q + 1) \geq 0$, so $r - d \in S$. But $r - d < r$, contradicting the minimality of $r$.

So $0 \leq r < d$ and $n = dq + r$. $\blacksquare$

Example 5: Uniqueness Proof

Problem: Prove that $q$ and $r$ are unique.

Proof. Suppose $n = dq_1 + r_1 = dq_2 + r_2$ with $0 \leq r_1, r_2 < d$.

Then $d(q_1 - q_2) = r_2 - r_1$. Since $|r_2 - r_1| < d$ (both remainders are in $[0, d)$), and $d \mid (r_2 - r_1)$, we must have $r_2 - r_1 = 0$, so $r_1 = r_2$.

Then $d(q_1 - q_2) = 0$, and since $d > 0$, $q_1 = q_2$. $\blacksquare$

Proof Techniques Spotlight

The Well-Ordering Principle in Existence Proofs

The existence proof above uses a powerful technique:

1. Define a set of "candidate" values.
2. Show the set is non-empty.
3. Invoke the Well-Ordering Principle (every non-empty set of non-negative integers has a least element).
4. Show the least element satisfies the required bounds.

Template:

Proof. Define S = { [expression involving unknowns] : [conditions] }.
1. S is non-empty because [specific element is in S].
2. By the Well-Ordering Principle, S has a minimum element r.
3. r satisfies [lower bound] because [definition of S].
4. r satisfies [upper bound] because [contradiction if not].
Therefore q and r exist. □

Common mistakes:

• Forgetting to prove $S$ is non-empty (especially for negative $n$).
• Confusing "least element" arguments with induction.
• Not handling the edge case $n = 0$ (where $q = 0, r = 0$).

Java Deep Dive

import java.util.*;

public class QuotientRemainderLibrary {

    // --- Core Methods ---

    /** Mathematical floor division: q = floor(n / d) */
    public static int floorDiv(int n, int d) {
        return Math.floorDiv(n, d);
    }

    /** Mathematical mod: r in [0, d), satisfying n = d*q + r */
    public static int mathMod(int n, int d) {
        return Math.floorMod(n, d);
    }

    /** Returns {quotient, remainder} satisfying n = d*q + r, 0 <= r < d */
    public static int[] divMod(int n, int d) {
        return new int[]{floorDiv(n, d), mathMod(n, d)};
    }

    // --- Applications ---

    /** Cyclic increment: wraps index around a buffer of given capacity */
    public static int cyclicNext(int index, int capacity) {
        // (index + 1) mod capacity — always in [0, capacity)
        return (index + 1) % capacity;
    }

    /** Maps a value to a bucket in a hash table */
    public static int hashBucket(int value, int numBuckets) {
        // Ensure non-negative bucket index
        return Math.floorMod(value, numBuckets);
    }

    /**
     * Converts total seconds to hours:minutes:seconds.
     * Uses repeated application of the quotient-remainder theorem.
     */
    public static String toHMS(int totalSeconds) {
        int hours = totalSeconds / 3600;
        int remaining = totalSeconds % 3600;
        int minutes = remaining / 60;
        int seconds = remaining % 60;
        return String.format("%02d:%02d:%02d", hours, minutes, seconds);
    }

    /**
     * Extracts the k-th digit (from the right, 0-indexed) of n in base b.
     * digit_k = (n / b^k) mod b
     */
    public static int digit(int n, int base, int k) {
        n = Math.abs(n);
        for (int i = 0; i < k; i++) n /= base;
        return n % base;
    }

    /**
     * Converts n to its representation in the given base.
     * Repeatedly applies the quotient-remainder theorem.
     */
    public static String toBase(int n, int base) {
        if (n == 0) return "0";
        StringBuilder sb = new StringBuilder();
        boolean negative = n < 0;
        n = Math.abs(n);
        while (n > 0) {
            sb.append(n % base);
            n /= base;
        }
        if (negative) sb.append('-');
        return sb.reverse().toString();
    }

    // --- Demonstration ---

    public static void main(String[] args) {
        System.out.println("=== Quotient-Remainder Theorem ===\n");

        // Basic division
        int[][] tests = {{137, 5}, {13, 5}, {0, 7}, {-7, 3}, {-20, 6}};
        System.out.println("Division with mathematical remainder:");
        for (int[] t : tests) {
            int[] qr = divMod(t[0], t[1]);
            System.out.printf("  %4d = %d × %2d + %d%n", t[0], t[1], qr[0], qr[1]);
        }

        // Java % vs mathematical mod for negative numbers
        System.out.println("\nJava % vs Math.floorMod for negative n:");
        for (int n : new int[]{-7, -13, -20}) {
            System.out.printf("  n=%3d, d=5: Java %% → %2d,  floorMod → %d%n",
                n, n % 5, Math.floorMod(n, 5));
        }

        // Cyclic buffer demo
        System.out.println("\nCyclic buffer (capacity 5):");
        int idx = 0;
        for (int i = 0; i < 12; i++) {
            System.out.printf("  step %2d: index = %d%n", i, idx);
            idx = cyclicNext(idx, 5);
        }

        // Time conversion
        System.out.println("\nTime conversion:");
        for (int sec : new int[]{0, 3661, 86399, 7200}) {
            System.out.printf("  %6d seconds = %s%n", sec, toHMS(sec));
        }

        // Base conversion
        System.out.println("\nBase conversion:");
        for (int n : new int[]{42, 255, 1000}) {
            System.out.printf("  %4d in base 2:  %s%n", n, toBase(n, 2));
            System.out.printf("  %4d in base 16: %s%n", n, toBase(n, 16));
        }
    }
}

Sample output:

=== Quotient-Remainder Theorem ===

Division with mathematical remainder:
   137 = 5 × 27 + 2
    13 = 5 ×  2 + 3
     0 = 7 ×  0 + 0
    -7 = 3 × -3 + 2
   -20 = 6 × -4 + 4

Java % vs Math.floorMod for negative n:
  n= -7, d=5: Java % → -2,  floorMod → 3
  n=-13, d=5: Java % → -3,  floorMod → 2
  n=-20, d=5: Java % →  0,  floorMod → 0

Cyclic buffer (capacity 5):
  step  0: index = 0
  step  1: index = 1
  step  2: index = 2
  step  3: index = 3
  step  4: index = 4
  step  5: index = 0
  ...

Time conversion:
       0 seconds = 00:00:00
    3661 seconds = 01:01:01
   86399 seconds = 23:59:59
    7200 seconds = 02:00:00

Base conversion:
    42 in base 2:  101010
    42 in base 16: 2a
   255 in base 2:  11111111
   255 in base 16: ff
  1000 in base 2:  1111101000
  1000 in base 16: 3e8

Historical Context

The idea of dividing with remainder is ancient — Euclid described it implicitly in his algorithm for computing the GCD. The formal statement of the Division Algorithm as a theorem (existence and uniqueness) was sharpened during the 19th century as mathematicians sought rigorous foundations for number theory.

The notation $a \bmod m$ and the systematic study of modular arithmetic were formalized by Carl Friedrich Gauss in his 1801 masterwork Disquisitiones Arithmeticae. Gauss introduced the congruence notation $a \equiv b \pmod{m}$ and showed that arithmetic within equivalence classes is consistent — a result that underlies everything from clock arithmetic to RSA encryption.

The Chinese Remainder Theorem, which concerns simultaneous congruences, dates back to the 3rd-century Chinese mathematician Sunzi. His original problem: "Find a number that leaves remainder 2 when divided by 3, remainder 3 when divided by 5, and remainder 2 when divided by 7."

Slide-Ready Problem Sets

Slide Set A: Conceptual Questions

A1. True or false: For any integer $n$ and positive integer $d$, the remainder $r = n \bmod d$ satisfies $0 \leq r \leq d$.

A2. What are the quotient and remainder when $n = -17$ is divided by $d = 5$? (Use the mathematical definition where $r \geq 0$.)

A3. In Java, what is the value of (-17) % 5? How does this differ from the mathematical remainder?

A4. A circular buffer has capacity 8. If the current index is 6, what is the next index? What about after 5 more steps?

Slide Set B: Proof Problems

B1. Prove: If $a = dq_1 + r_1$ and $a = dq_2 + r_2$ with $0 \leq r_1, r_2 < d$, then $q_1 = q_2$ and $r_1 = r_2$.

B2. Prove: For any positive integers $a$ and $b$, $a \bmod b < a$ if and only if $a \geq b$.

B3. Prove: For any integers $a, b$ and positive integer $d$, $(a + b) \bmod d = ((a \bmod d) + (b \bmod d)) \bmod d$.

Slide Set C: Java Coding Problems

C1. Write a method boolean isLeapYear(int year) using the quotient-remainder theorem (a year is a leap year if divisible by 4, except centuries, except centuries divisible by 400).

C2. Write a method int dayOfWeek(int dayNumber) that takes a day number (0 = Sunday) and returns the day of the week after advancing by any number of days (including negative).

C3. Write a method String toBaseN(int n, int base) that converts a non-negative integer $n$ to its string representation in the given base (2 through 36).

Full Problem Set

Discrete Math Problems

DM1. Find the quotient and remainder when $n = 2023$ is divided by $d = 17$.

DM2. Prove that for any integer $n$, $n^2 \bmod 4 \in \{0, 1\}$. (That is, perfect squares leave remainder 0 or 1 when divided by 4.)

DM3. Prove: If $a \bmod d = 0$ and $b \bmod d = 0$, then $(a + b) \bmod d = 0$.

DM4. Prove the existence of $q$ and $r$ in the quotient-remainder theorem using the Well-Ordering Principle.

DM5. Prove: For any positive integers $a, b, c$ with $c > 0$, $\lfloor \lfloor a/b \rfloor / c \rfloor = \lfloor a / (bc) \rfloor$.

DM6. Let $n$ be a positive integer. Prove that among any $n + 1$ integers from $\{1, 2, \ldots, 2n\}$, at least two have the same remainder when divided by $n$.

DM7. Prove that the last digit of $n^2$ (i.e., $n^2 \bmod 10$) can only be one of $\{0, 1, 4, 5, 6, 9\}$.

Java Programming Problems

JP1. Write a method int[] quotRem(int n, int d) that returns the mathematical quotient and remainder (not Java's truncation-toward-zero). Test with positive and negative inputs.

JP2. Write a method int extractDigit(int n, int position) that returns the digit at the given position (0 = ones, 1 = tens, etc.).

JP3. Write a method int sumOfDigits(int n) that computes the sum of digits of $n$ using repeated division. Prove (informally) that the loop terminates.

JP4. Implement a circular buffer class with methods add(int item), get(int index), and isFull(). Use % for wrap-around.

JP5. Write a method boolean isPerfectSquare(int n) that uses the fact that $n^2 \bmod 4 \in \{0, 1\}$ to quickly reject non-squares before checking with Math.sqrt.

JP6. Write a program that reads integers from the user and groups them by their remainder modulo 7. Print each group.

Bridge Problems

BR1. Prove that the sum of digits of a number $n$ has the same remainder as $n$ when divided by 9 (i.e., $n \equiv \text{digitSum}(n) \pmod{9}$). Then write a Java method that verifies this for all $n$ from 1 to 10000.

BR2. A hash table uses h(key) = key % tableSize. Prove that if tableSize divides key1 - key2, then key1 and key2 collide. Write Java code that demonstrates this.

BR3. Write a Java method int[] toMixedRadix(int seconds) that converts a number of seconds to days, hours, minutes, seconds. This uses the quotient-remainder theorem three times in sequence. State and prove the invariant at each step.

Solutions

Discrete Math Solutions

DM1. $2023 = 17 \times 119 + 0$. Check: $17 \times 119 = 2023$. So $q = 119, r = 0$.

DM2. Any integer $n$ satisfies $n \bmod 2 \in \{0, 1\}$.

• If $n = 2k$: $n^2 = 4k^2$, so $n^2 \bmod 4 = 0$.
• If $n = 2k + 1$: $n^2 = 4k^2 + 4k + 1 = 4(k^2 + k) + 1$, so $n^2 \bmod 4 = 1$. $\blacksquare$

DM3. If $a = dq_1$ and $b = dq_2$, then $a + b = d(q_1 + q_2)$. Since $q_1 + q_2 \in \mathbb{Z}$, $d \mid (a + b)$. $\blacksquare$

DM4. (See Example 4 above for the full proof using the Well-Ordering Principle.)

DM5. Let $a = bq_1 + r_1$ with $0 \leq r_1 < b$, and $q_1 = cq_2 + r_2$ with $0 \leq r_2 < c$. Then $a = b(cq_2 + r_2) + r_1 = bcq_2 + (br_2 + r_1)$. We need $0 \leq br_2 + r_1 < bc$: since $r_2 < c$ and $r_1 < b$, $br_2 + r_1 < bc$, and both are non-negative. So $\lfloor a/(bc) \rfloor = q_2 = \lfloor q_1/c \rfloor = \lfloor \lfloor a/b \rfloor / c \rfloor$. $\blacksquare$

DM6. By the Pigeonhole Principle: there are $n$ possible remainders modulo $n$ (namely $0, 1, \ldots, n-1$). With $n + 1$ integers, at least two must share the same remainder. $\blacksquare$

DM7. Compute $k^2 \bmod 10$ for $k = 0, 1, \ldots, 9$: $0, 1, 4, 9, 6, 5, 6, 9, 4, 1$. Since $n \bmod 10 \in \{0,\ldots,9\}$, $n^2 \bmod 10$ is determined by $n \bmod 10$, and the only possible values are $\{0, 1, 4, 5, 6, 9\}$. $\blacksquare$

Java Solutions

JP1.

public static int[] quotRem(int n, int d) {
    int q = Math.floorDiv(n, d);
    int r = Math.floorMod(n, d);
    return new int[]{q, r};
}

JP2.

public static int extractDigit(int n, int position) {
    n = Math.abs(n);
    for (int i = 0; i < position; i++) n /= 10;
    return n % 10;
}

JP3.

public static int sumOfDigits(int n) {
    n = Math.abs(n);
    int sum = 0;
    // Variant function: n (decreases by factor of 10 each iteration)
    while (n > 0) {
        sum += n % 10;   // extract last digit
        n /= 10;         // remove last digit
    }
    return sum;
}
// Termination: n is non-negative and n /= 10 strictly decreases n
// toward 0 (since n >= 1 implies n/10 < n for integer division).

JP4.

public class CircularBuffer {
    private int[] data;
    private int head, size, capacity;

    public CircularBuffer(int capacity) {
        this.capacity = capacity;
        data = new int[capacity];
        head = 0;
        size = 0;
    }

    public void add(int item) {
        if (size == capacity) throw new IllegalStateException("Buffer full");
        data[(head + size) % capacity] = item;  // wrap-around
        size++;
    }

    public int get(int index) {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException();
        return data[(head + index) % capacity];  // wrap-around
    }

    public boolean isFull() { return size == capacity; }
}

JP5.

public static boolean isPerfectSquare(int n) {
    if (n < 0) return false;
    // Quick reject: n^2 mod 4 ∈ {0,1}, so if n mod 4 ∈ {2,3}, not a square
    int r = n % 4;
    if (r == 2 || r == 3) return false;
    // Full check
    int s = (int) Math.round(Math.sqrt(n));
    return s * s == n;
}

JP6.

public static void groupByRemainder(int[] nums, int mod) {
    Map<Integer, List<Integer>> groups = new TreeMap<>();
    for (int n : nums) {
        int r = Math.floorMod(n, mod);
        groups.computeIfAbsent(r, k -> new ArrayList<>()).add(n);
    }
    for (var entry : groups.entrySet()) {
        System.out.printf("  Remainder %d: %s%n", entry.getKey(), entry.getValue());
    }
}

Bridge Solutions

BR1. Write $n$ in decimal: $n = a_k \cdot 10^k + \cdots + a_1 \cdot 10 + a_0$. Since $10 \equiv 1 \pmod{9}$, we have $10^i \equiv 1 \pmod{9}$ for all $i$. So $n \equiv a_k + \cdots + a_1 + a_0 \pmod{9}$.

public static void verifyCastingOutNines() {
    for (int n = 1; n <= 10000; n++) {
        assert Math.floorMod(n, 9) == Math.floorMod(sumOfDigits(n), 9)
            : "Failed for n=" + n;
    }
    System.out.println("Casting out nines verified for 1..10000");
}

BR2. If $\text{tableSize} \mid (k_1 - k_2)$, then $k_1 \equiv k_2 \pmod{\text{tableSize}}$, so $k_1 \bmod \text{tableSize} = k_2 \bmod \text{tableSize}$, meaning they hash to the same bucket.

public static void demonstrateCollisions() {
    int tableSize = 7;
    // keys that differ by multiples of 7 collide
    int[] keys = {3, 10, 17, 24, 31};
    for (int k : keys) {
        System.out.printf("  hash(%d) = %d%n", k, k % tableSize);
    }
    // All print 3, confirming collisions
}

BR3.

public static int[] toMixedRadix(int totalSeconds) {
    // Step 1: totalSeconds = 86400*days + rem1,  0 <= rem1 < 86400
    int days = totalSeconds / 86400;
    int rem1 = totalSeconds % 86400;
    // Invariant: totalSeconds = 86400*days + rem1

    // Step 2: rem1 = 3600*hours + rem2,  0 <= rem2 < 3600
    int hours = rem1 / 3600;
    int rem2 = rem1 % 3600;
    // Invariant: totalSeconds = 86400*days + 3600*hours + rem2

    // Step 3: rem2 = 60*minutes + seconds,  0 <= seconds < 60
    int minutes = rem2 / 60;
    int seconds = rem2 % 60;
    // Invariant: totalSeconds = 86400*days + 3600*hours + 60*minutes + seconds

    return new int[]{days, hours, minutes, seconds};
}

Learning Objectives

• Define congruence modulo $m$ and explain its meaning as an equivalence relation.
• Prove that congruence is reflexive, symmetric, and transitive.
• Prove that addition and multiplication respect congruence.
• Translate congruence operations into Java using % and Math.floorMod.
• Apply modular arithmetic to cyclic structures, hashing, and cryptography.

Concept Overview

Congruence modulo $m$ captures the idea that two integers "behave the same" with respect to division by $m$.

Definition. Let $m$ be a positive integer. We say $a$ is congruent to $b$ modulo $m$, written

$a \equiv b \pmod{m},$

if $m \mid (a - b)$, i.e., there exists $k \in \mathbb{Z}$ such that $a - b = mk$.

Equivalently: $a$ and $b$ leave the same remainder when divided by $m$.

Congruence classes (equivalence classes): The set of all integers congruent to $a$ modulo $m$ is denoted $[a]_m$:

The integers modulo $m$ partition into exactly $m$ congruence classes: $[0]_m, [1]_m, \ldots, [m-1]_m$.

Why this matters in CS:

• Hashing: Keys mapped to buckets via key % tableSize — all keys in the same congruence class collide.
• Cyclic data structures: Circular buffers, ring buffers, round-robin schedulers.
• Cryptography: RSA, Diffie-Hellman, and other protocols operate in $\mathbb{Z}_n$.
• Checksums: ISBN, credit card (Luhn), and network checksums use modular arithmetic.

Formal Notation

Key properties of congruence:

1. Reflexive: $a \equiv a \pmod{m}$ because $m \mid 0$.
2. Symmetric: If $a \equiv b \pmod{m}$, then $b \equiv a \pmod{m}$.
3. Transitive: If $a \equiv b \pmod{m}$ and $b \equiv c \pmod{m}$, then $a \equiv c \pmod{m}$.

Together these make congruence an equivalence relation.

Arithmetic compatibility:

1. Addition: If $a \equiv b \pmod{m}$ and $c \equiv d \pmod{m}$, then $a + c \equiv b + d \pmod{m}$.
2. Multiplication: If $a \equiv b \pmod{m}$ and $c \equiv d \pmod{m}$, then $ac \equiv bd \pmod{m}$.

Worked Examples

Example 1: Verifying Congruences — Discrete Math

Problem: Show that $38 \equiv 14 \pmod{8}$ and that $38 \not\equiv 14 \pmod{5}$.

Solution:

• $38 - 14 = 24 = 8 \times 3$. Since $8 \mid 24$, $38 \equiv 14 \pmod{8}$. ✓
• $38 - 14 = 24$. Is $5 \mid 24$? No ($24 / 5 = 4.8$). So $38 \not\equiv 14 \pmod{5}$. ✓

Example 2: Java Translation — Congruence Checker

public class CongruenceDemo {

    /** Checks whether a ≡ b (mod m), i.e., m | (a - b) */
    public static boolean isCongruent(int a, int b, int m) {
        // (a - b) is divisible by m iff (a - b) % m == 0
        // Use Math.floorMod to handle negative differences correctly
        return Math.floorMod(a - b, m) == 0;
    }

    /** Returns the canonical representative of [a]_m, i.e., a mod m in [0, m) */
    public static int canonical(int a, int m) {
        return Math.floorMod(a, m);
    }

    /** Groups integers by their congruence class mod m */
    public static Map<Integer, List<Integer>> groupByClass(int[] nums, int m) {
        Map<Integer, List<Integer>> classes = new TreeMap<>();
        for (int n : nums) {
            int rep = canonical(n, m);
            classes.computeIfAbsent(rep, k -> new ArrayList<>()).add(n);
        }
        return classes;
    }

    public static void main(String[] args) {
        // Check congruences
        System.out.println("38 ≡ 14 (mod 8)? " + isCongruent(38, 14, 8));
        System.out.println("38 ≡ 14 (mod 5)? " + isCongruent(38, 14, 5));

        // Group numbers by congruence class mod 4
        int[] nums = {-7, -3, 0, 1, 4, 5, 8, 9, 12, 13, 16, 17};
        var classes = groupByClass(nums, 4);
        for (var entry : classes.entrySet()) {
            System.out.printf("  [%d]_4 = %s%n", entry.getKey(), entry.getValue());
        }
    }
}

Sample output:

38 ≡ 14 (mod 8)? true
38 ≡ 14 (mod 5)? false
  [0]_4 = [0, 4, 8, 12, 16]
  [1]_4 = [1, 5, 9, 13, 17]
  [2]_4 = [-7, -3]       (since floorMod(-7,4) = 1... wait)

Actually, let's be precise: Math.floorMod(-7, 4) = 1 and Math.floorMod(-3, 4) = 1. So $-7$ and $-3$ go into class $[1]_4$. This is correct: $-7 \equiv 1 \pmod{4}$ because $-7 - 1 = -8 = 4 \times (-2)$.

Example 3: Proving Addition Respects Congruence — Combined

Problem: Prove: If $a \equiv b \pmod{m}$ and $c \equiv d \pmod{m}$, then $a + c \equiv b + d \pmod{m}$.

Proof. By hypothesis, $m \mid (a - b)$ and $m \mid (c - d)$. Write $a - b = mk_1$ and $c - d = mk_2$.

Then $(a + c) - (b + d) = (a - b) + (c - d) = mk_1 + mk_2 = m(k_1 + k_2)$.

Since $k_1 + k_2 \in \mathbb{Z}$, $m \mid ((a+c) - (b+d))$, so $a + c \equiv b + d \pmod{m}$. $\blacksquare$

Java verification:

public static void verifyAdditionCompat() {
    for (int m = 2; m <= 20; m++) {
        for (int a = -50; a <= 50; a++) {
            for (int c = -50; c <= 50; c++) {
                int b = canonical(a, m);  // b ≡ a (mod m)
                int d = canonical(c, m);  // d ≡ c (mod m)
                // (a + c) mod m should equal (b + d) mod m
                assert canonical(a + c, m) == canonical(b + d, m);
            }
        }
    }
    System.out.println("Addition compatibility verified.");
}

Example 4: Proving Multiplication Respects Congruence

Problem: Prove: If $a \equiv b \pmod{m}$ and $c \equiv d \pmod{m}$, then $ac \equiv bd \pmod{m}$.

Proof. Write $a = b + mk_1$ and $c = d + mk_2$. Then:

So $ac - bd = m(bk_2 + k_1 d + mk_1 k_2)$, and since the expression in parentheses is an integer, $m \mid (ac - bd)$. $\blacksquare$

Example 5: Circular Buffer Index Cycling

Problem: Prove that starting from index 0 and repeatedly computing $(i + 1) \bmod n$ visits every index $0, 1, \ldots, n-1$ exactly once before returning to 0.

Proof. After $k$ steps, the index is $k \bmod n$. For $0 \leq k < n$, these are $0, 1, \ldots, n-1$ — all distinct (since $0 \leq k_1 < k_2 < n$ implies $k_2 - k_1 < n$, so $k_1 \not\equiv k_2 \pmod{n}$). After $n$ steps, the index is $n \bmod n = 0$. $\blacksquare$

Proof Techniques Spotlight

Equivalence Relation Proofs

To prove congruence is an equivalence relation, verify three properties:

Template for reflexivity: "$a - a = 0 = m \cdot 0$, so $m \mid (a - a)$."

Template for symmetry: "If $a - b = mk$, then $b - a = m(-k)$, and $-k \in \mathbb{Z}$."

Template for transitivity: "If $a - b = mk_1$ and $b - c = mk_2$, add: $a - c = m(k_1 + k_2)$."

Modular Arithmetic in Proofs

A powerful technique: reduce expressions modulo $m$ to simplify.

To find the last digit of $7^{100}$:

• $7^1 \equiv 7 \pmod{10}$
• $7^2 \equiv 49 \equiv 9 \pmod{10}$
• $7^3 \equiv 63 \equiv 3 \pmod{10}$
• $7^4 \equiv 21 \equiv 1 \pmod{10}$
• The pattern repeats with period 4. Since $100 = 4 \times 25$, $7^{100} \equiv 1 \pmod{10}$.

Java Deep Dive

import java.util.*;

public class ModularArithmeticLibrary {

    // --- Core Modular Operations ---

    /** Canonical representative: a mod m, always in [0, m) */
    public static int mod(int a, int m) {
        return Math.floorMod(a, m);
    }

    /** Modular addition: (a + b) mod m */
    public static int modAdd(int a, int b, int m) {
        return mod(mod(a, m) + mod(b, m), m);
    }

    /** Modular multiplication: (a * b) mod m */
    public static int modMul(int a, int b, int m) {
        // Use long to avoid overflow for large a, b
        return (int) (((long) mod(a, m) * mod(b, m)) % m);
    }

    /** Modular exponentiation: a^exp mod m (fast, using repeated squaring) */
    public static int modPow(int base, int exp, int m) {
        long result = 1;
        long b = mod(base, m);
        while (exp > 0) {
            if (exp % 2 == 1) {
                result = (result * b) % m;
            }
            b = (b * b) % m;
            exp /= 2;
        }
        return (int) result;
    }

    // --- Congruence Checks ---

    /** Returns true if a ≡ b (mod m) */
    public static boolean congruent(int a, int b, int m) {
        return mod(a - b, m) == 0;
    }

    /**
     * Builds the addition table for Z_m.
     * Entry [i][j] = (i + j) mod m.
     */
    public static int[][] additionTable(int m) {
        int[][] table = new int[m][m];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < m; j++)
                table[i][j] = (i + j) % m;
        return table;
    }

    /**
     * Builds the multiplication table for Z_m.
     * Entry [i][j] = (i * j) mod m.
     */
    public static int[][] multiplicationTable(int m) {
        int[][] table = new int[m][m];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < m; j++)
                table[i][j] = (i * j) % m;
        return table;
    }

    /**
     * Finds all units (invertible elements) in Z_m.
     * a is a unit if gcd(a, m) = 1.
     */
    public static List<Integer> units(int m) {
        List<Integer> result = new ArrayList<>();
        for (int a = 1; a < m; a++) {
            if (gcd(a, m) == 1) result.add(a);
        }
        return result;
    }

    /** Finds the multiplicative inverse of a mod m, if it exists. */
    public static int modInverse(int a, int m) {
        int[] r = extendedGcd(mod(a, m), m);
        if (r[0] != 1) throw new ArithmeticException(a + " has no inverse mod " + m);
        return mod(r[1], m);
    }

    // --- Helper: GCD ---

    public static int gcd(int a, int b) {
        a = Math.abs(a); b = Math.abs(b);
        while (b != 0) { int r = a % b; a = b; b = r; }
        return a;
    }

    public static int[] extendedGcd(int a, int b) {
        if (b == 0) return new int[]{a, 1, 0};
        int[] r = extendedGcd(b, a % b);
        return new int[]{r[0], r[2], r[1] - (a / b) * r[2]};
    }

    // --- Printing ---

    public static void printTable(int[][] table, String label) {
        int m = table.length;
        System.out.println(label + " table for Z_" + m + ":");
        System.out.printf("  %s |", "");
        for (int j = 0; j < m; j++) System.out.printf(" %2d", j);
        System.out.println();
        System.out.print("  ---+");
        for (int j = 0; j < m; j++) System.out.print("---");
        System.out.println();
        for (int i = 0; i < m; i++) {
            System.out.printf("  %2d |", i);
            for (int j = 0; j < m; j++) System.out.printf(" %2d", table[i][j]);
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {
        System.out.println("=== Modular Arithmetic Library ===\n");

        // Addition and multiplication tables for Z_5
        printTable(additionTable(5), "Addition");
        printTable(multiplicationTable(5), "Multiplication");

        // Units of Z_12
        System.out.println("Units of Z_12: " + units(12));
        // Expected: [1, 5, 7, 11] — those coprime to 12

        // Modular inverse
        System.out.println("Inverse of 5 mod 12 = " + modInverse(5, 12));
        // 5 * 5 = 25 ≡ 1 (mod 12) ✓

        // Modular exponentiation: last digit of 7^100
        System.out.println("7^100 mod 10 = " + modPow(7, 100, 10));
        // Expected: 1

        // Verify: (a+b) mod m = ((a mod m) + (b mod m)) mod m
        System.out.println("\nVerifying modular arithmetic properties...");
        for (int m = 2; m <= 15; m++) {
            for (int a = -50; a <= 50; a++) {
                for (int b = -50; b <= 50; b++) {
                    assert mod(a + b, m) == modAdd(a, b, m);
                    assert mod(a * b, m) == modMul(a, b, m);
                }
            }
        }
        System.out.println("All properties verified.");
    }
}

Historical Context

Carl Friedrich Gauss (1777–1855) formalized modular arithmetic in his Disquisitiones Arithmeticae (1801), introducing the notation $a \equiv b \pmod{m}$. He showed that congruence classes form a consistent arithmetic system — you can add, subtract, and multiply congruence classes and get well-defined results.

The Chinese Remainder Theorem (next class) was discovered by Sunzi in the 3rd century CE. It states that a system of simultaneous congruences with pairwise coprime moduli has a unique solution. This was used for calendar calculations and later became foundational in cryptography.

Euler's theorem ($a^{\phi(m)} \equiv 1 \pmod{m}$ for $\gcd(a,m) = 1$) and Fermat's little theorem ($a^{p-1} \equiv 1 \pmod{p}$ for prime $p$) are key results that power modern cryptography, including RSA.

Slide-Ready Problem Sets

Slide Set A: Conceptual Questions

A1. True or false: $25 \equiv 4 \pmod{7}$.

A2. List all elements of the congruence class $[3]_5$ that lie between $-15$ and $20$.

A3. How many distinct congruence classes are there modulo $m$?

A4. If today is Wednesday (day 3), what day will it be 100 days from now? Express using congruence.

Slide Set B: Proof Problems

B1. Prove that congruence modulo $m$ is transitive.

B2. Prove that if $a \equiv b \pmod{m}$, then $a^2 \equiv b^2 \pmod{m}$.

B3. Prove or disprove: If $ac \equiv bc \pmod{m}$, then $a \equiv b \pmod{m}$.

Slide Set C: Java Coding Problems

C1. Write a method that builds and prints the multiplication table for $\mathbb{Z}_m$.

C2. Write a method List<Integer> congruenceClass(int a, int m, int lo, int hi) that returns all integers in $[a]_m$ between lo and hi.

C3. Write a method that finds all elements in $\mathbb{Z}_m$ that are their own multiplicative inverse (i.e., $a^2 \equiv 1 \pmod{m}$).

Full Problem Set

Discrete Math Problems

DM1. Determine whether $123 \equiv 42 \pmod{9}$.

DM2. Prove that $a \equiv b \pmod{m}$ if and only if $a \bmod m = b \bmod m$.

DM3. Prove: For any integer $n$, $n^2 \equiv 0$ or $1 \pmod{3}$.

DM4. Find the last two digits of $3^{100}$ (i.e., compute $3^{100} \bmod 100$).

DM5. Prove that if $\gcd(c, m) = 1$ and $ac \equiv bc \pmod{m}$, then $a \equiv b \pmod{m}$. (This is the cancellation law.)

DM6. Prove that $[a]_m$ has a multiplicative inverse in $\mathbb{Z}_m$ if and only if $\gcd(a, m) = 1$.

DM7. How many units (invertible elements) are there in $\mathbb{Z}_{30}$? List them.

Java Programming Problems

JP1. Write a method boolean isCongruent(int a, int b, int m) that correctly handles negative inputs.

JP2. Implement modular exponentiation using repeated squaring: int modPow(int base, int exp, int mod).

JP3. Write a method that reads a list of integers and partitions them into congruence classes modulo $m$, printing each class.

JP4. Implement a method int modInverse(int a, int m) that returns the modular inverse using the extended Euclidean algorithm. Throw an exception if the inverse doesn't exist.

JP5. Write a program that verifies Fermat's Little Theorem: for prime $p$ and $1 \leq a < p$, $a^{p-1} \equiv 1 \pmod{p}$. Test for all primes $p \leq 50$.

JP6. Implement a simple clock class where the time wraps around using modular arithmetic. Support advance(int hours), retreat(int hours), and toString().

Bridge Problems

BR1. Prove that in $\mathbb{Z}_m$, the number of units equals Euler's totient $\phi(m)$. Write a Java method int eulerTotient(int m) and verify that units(m).size() == eulerTotient(m) for $m = 1, \ldots, 100$.

BR2. A circular array of size $n$ starts at index 0. Prove that after $n$ increments of $(i + 1) \bmod n$, the index returns to 0 and every position has been visited exactly once. Write Java code that verifies this for $n = 1, \ldots, 1000$.

BR3. Implement a Luhn checksum verifier for credit card numbers using modular arithmetic. Explain how each step relates to congruence modulo 10.

Solutions

Discrete Math Solutions

DM1. $123 - 42 = 81 = 9 \times 9$. Since $9 \mid 81$, $123 \equiv 42 \pmod{9}$. ✓

DM2. ($\Rightarrow$) If $a \equiv b \pmod{m}$, then $m \mid (a - b)$. Write $a = mq_1 + r$ and $b = mq_2 + r'$ with $0 \leq r, r' < m$. Then $a - b = m(q_1 - q_2) + (r - r')$. Since $m \mid (a - b)$, $m \mid (r - r')$. But $|r - r'| < m$, so $r = r'$.

($\Leftarrow$) If $a \bmod m = b \bmod m = r$, then $a = mq_1 + r$ and $b = mq_2 + r$, so $a - b = m(q_1 - q_2)$, giving $m \mid (a - b)$. $\blacksquare$

DM3. Any integer $n$ satisfies $n \equiv 0, 1, \text{ or } 2 \pmod{3}$.

• $n \equiv 0$: $n^2 \equiv 0 \pmod{3}$.
• $n \equiv 1$: $n^2 \equiv 1 \pmod{3}$.
• $n \equiv 2$: $n^2 \equiv 4 \equiv 1 \pmod{3}$. $\blacksquare$

DM4. Using repeated squaring modulo 100:

• $3^1 = 3$
• $3^2 = 9$
• $3^4 = 81$
• $3^8 = 6561 \equiv 61$
• $3^{16} \equiv 61^2 = 3721 \equiv 21$
• $3^{32} \equiv 21^2 = 441 \equiv 41$
• $3^{64} \equiv 41^2 = 1681 \equiv 81$
• $3^{100} = 3^{64} \cdot 3^{32} \cdot 3^{4} \equiv 81 \cdot 41 \cdot 81 \pmod{100}$
• $81 \cdot 41 = 3321 \equiv 21$
• $21 \cdot 81 = 1701 \equiv 1$

So $3^{100} \equiv 1 \pmod{100}$.

DM5. If $ac \equiv bc \pmod{m}$, then $m \mid c(a - b)$. Since $\gcd(c, m) = 1$, by Euclid's Lemma, $m \mid (a - b)$, so $a \equiv b \pmod{m}$. $\blacksquare$

DM6. ($\Rightarrow$) If $[a]_m$ has an inverse $[b]_m$, then $ab \equiv 1 \pmod{m}$, so $ab = 1 + mk$ for some $k$. Then $ab - mk = 1$, which is a Bézout expression, so $\gcd(a, m) = 1$.

($\Leftarrow$) If $\gcd(a, m) = 1$, by the extended Euclidean algorithm, find $x, y$ with $ax + my = 1$. Then $ax \equiv 1 \pmod{m}$, so $[x]_m$ is the inverse. $\blacksquare$

DM7. The units of $\mathbb{Z}_{30}$ are those $a$ with $\gcd(a, 30) = 1$: $\{1, 7, 11, 13, 17, 19, 23, 29\}$. There are 8 units. (This equals $\phi(30) = 30 \cdot (1 - 1/2)(1 - 1/3)(1 - 1/5) = 8$.)

Java Solutions

JP1.

public static boolean isCongruent(int a, int b, int m) {
    return Math.floorMod(a - b, m) == 0;
}

JP2.

public static int modPow(int base, int exp, int mod) {
    long result = 1;
    long b = Math.floorMod(base, mod);
    while (exp > 0) {
        if (exp % 2 == 1) result = (result * b) % mod;
        b = (b * b) % mod;
        exp /= 2;
    }
    return (int) result;
}

JP3.

public static void partitionByCongruence(int[] nums, int m) {
    Map<Integer, List<Integer>> classes = new TreeMap<>();
    for (int n : nums) {
        int r = Math.floorMod(n, m);
        classes.computeIfAbsent(r, k -> new ArrayList<>()).add(n);
    }
    for (var entry : classes.entrySet()) {
        System.out.printf("  [%d]_%d = %s%n", entry.getKey(), m, entry.getValue());
    }
}

JP4.

public static int modInverse(int a, int m) {
    a = Math.floorMod(a, m);
    int[] r = extendedGcd(a, m);
    if (r[0] != 1) throw new ArithmeticException(a + " not invertible mod " + m);
    return Math.floorMod(r[1], m);
}

JP5.

public static void verifyFermatsLittle() {
    for (int p = 2; p <= 50; p++) {
        if (!isPrime(p)) continue;
        for (int a = 1; a < p; a++) {
            assert modPow(a, p - 1, p) == 1 :
                "Fermat failed for a=" + a + ", p=" + p;
        }
    }
    System.out.println("Fermat's Little Theorem verified for primes ≤ 50.");
}

JP6.

public class ModularClock {
    private int hour;  // 0..23

    public ModularClock(int hour) { this.hour = Math.floorMod(hour, 24); }

    public void advance(int hours) { hour = Math.floorMod(hour + hours, 24); }
    public void retreat(int hours) { advance(-hours); }

    public String toString() { return String.format("%02d:00", hour); }
}

Bridge Solutions

BR1.

public static int eulerTotient(int m) {
    int count = 0;
    for (int a = 1; a < m; a++) {
        if (gcd(a, m) == 1) count++;
    }
    return count;
}

public static void verifyTotient() {
    for (int m = 1; m <= 100; m++) {
        assert units(m).size() == eulerTotient(m);
    }
    System.out.println("Totient = #units verified for m=1..100");
}

BR2.

public static void verifyCyclicTraversal() {
    for (int n = 1; n <= 1000; n++) {
        boolean[] visited = new boolean[n];
        int idx = 0;
        for (int step = 0; step < n; step++) {
            assert !visited[idx] : "Revisited index " + idx;
            visited[idx] = true;
            idx = (idx + 1) % n;
        }
        assert idx == 0 : "Did not return to 0";
        for (int i = 0; i < n; i++) assert visited[i];
    }
    System.out.println("Cyclic traversal verified for n=1..1000");
}

BR3.

public static boolean luhnCheck(String cardNumber) {
    // Luhn: from right, double every second digit.
    // If doubled > 9, subtract 9. Sum all. Valid if sum ≡ 0 (mod 10).
    int sum = 0;
    boolean doubleNext = false;
    for (int i = cardNumber.length() - 1; i >= 0; i--) {
        int d = cardNumber.charAt(i) - '0';
        if (doubleNext) {
            d *= 2;
            if (d > 9) d -= 9;  // equivalent to d mod 9 for d in [10,18]
        }
        sum += d;
        doubleNext = !doubleNext;
    }
    return sum % 10 == 0;  // congruence check: sum ≡ 0 (mod 10)
}

Learning Objectives

• State the Fundamental Theorem of Arithmetic and prove existence by strong induction.
• Implement trial division for prime factorization in Java.
• State and apply the Chinese Remainder Theorem (CRT).
• Implement a constructive CRT solver using Bézout coefficients.
• Explain how prime factorization and CRT apply to RSA and multi-modulus computation.

Concept Overview

The Fundamental Theorem of Arithmetic

Theorem. Every integer $n > 1$ can be written as a product of primes:

$n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$

and this factorization is unique up to the order of the factors.

The existence part follows by strong induction. The uniqueness part requires Euclid's Lemma: if $p$ is prime and $p \mid ab$, then $p \mid a$ or $p \mid b$.

The Chinese Remainder Theorem (CRT)

Theorem. If $m$ and $n$ are coprime (i.e., $\gcd(m, n) = 1$), then the system

$x \equiv a \pmod{m}, \qquad x \equiv b \pmod{n}$

has a unique solution modulo $mn$.

Constructive solution: Find Bézout coefficients $s, t$ with $ms + nt = 1$. Then $x = a \cdot nt + b \cdot ms$.

Why this matters in CS:

• RSA cryptography: Encryption and decryption rely on modular exponentiation and CRT for efficient computation.
• Multi-modulus arithmetic: CRT allows computing with large numbers by splitting into smaller moduli.
• Error detection: Residue number systems use CRT for fault-tolerant computation.
• Hash functions: Prime factorization analysis helps understand collision behavior.

Formal Notation

Relationship between GCD and LCM:

Worked Examples

Example 1: Prime Factorization by Trial Division — Discrete Math

Problem: Factor $n = 2520$ into primes.

Solution: Divide by the smallest prime possible at each step:

• $2520 / 2 = 1260$
• $1260 / 2 = 630$
• $630 / 2 = 315$
• $315 / 3 = 105$
• $105 / 3 = 35$
• $35 / 5 = 7$
• $7 / 7 = 1$

So $2520 = 2^3 \cdot 3^2 \cdot 5 \cdot 7$. $\blacksquare$

Example 2: Java Translation — Prime Factorization

import java.util.*;

public class PrimeFactorizationDemo {

    /**
     * Returns the prime factorization of n as a map: prime -> exponent.
     * E.g., 2520 -> {2:3, 3:2, 5:1, 7:1}
     *
     * Algorithm: trial division.
     * Mathematical basis: every composite n has a factor ≤ sqrt(n).
     */
    public static Map<Integer, Integer> factorize(int n) {
        Map<Integer, Integer> factors = new TreeMap<>();
        // Try each possible divisor d starting from 2.
        // Only need d <= sqrt(n) because if n has no factor ≤ sqrt(n), n is prime.
        for (int d = 2; (long) d * d <= n; d++) {
            while (n % d == 0) {
                factors.merge(d, 1, Integer::sum);  // increment exponent
                n /= d;
            }
        }
        // If n > 1 at this point, n itself is a prime factor.
        if (n > 1) factors.merge(n, 1, Integer::sum);
        return factors;
    }

    /** Converts a factorization map to a readable string like "2^3 × 3^2 × 5 × 7" */
    public static String factorString(Map<Integer, Integer> factors) {
        StringBuilder sb = new StringBuilder();
        for (var entry : factors.entrySet()) {
            if (sb.length() > 0) sb.append(" × ");
            sb.append(entry.getKey());
            if (entry.getValue() > 1) sb.append("^").append(entry.getValue());
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        int[] testNums = {2, 12, 84, 100, 2520, 97, 1000, 7919};
        for (int n : testNums) {
            var factors = factorize(n);
            System.out.printf("  %5d = %s%n", n, factorString(factors));
        }
    }
}

Sample output:

      2 = 2
     12 = 2^2 × 3
     84 = 2^2 × 3 × 7
    100 = 2^2 × 5^2
   2520 = 2^3 × 3^2 × 5 × 7
     97 = 97
   1000 = 2^3 × 5^3
   7919 = 7919

Example 3: Existence Proof by Strong Induction — Combined

Problem: Prove that every integer $n > 1$ has a prime factorization.

Proof (Strong Induction).

Base case: $n = 2$ is prime, so its factorization is just $\{2\}$. ✓

Inductive step: Assume every integer $k$ with $2 \leq k < n$ has a prime factorization. Consider $n$:

• Case 1: $n$ is prime. Then its factorization is $\{n\}$.
• Case 2: $n$ is composite. Then $n = a \cdot b$ with $2 \leq a, b < n$. By the inductive hypothesis, $a = p_1^{e_1} \cdots p_j^{e_j}$ and $b = q_1^{f_1} \cdots q_k^{f_k}$. Combining these gives a prime factorization of $n$.

By strong induction, every $n > 1$ has a prime factorization. $\blacksquare$

Example 4: CRT — Solving Simultaneous Congruences

Problem: Solve $x \equiv 2 \pmod{3}$ and $x \equiv 3 \pmod{5}$.

Solution:

Step 1: Verify $\gcd(3, 5) = 1$. ✓

Step 2: Find Bézout coefficients: $3s + 5t = 1$. By inspection (or extended GCD), $s = 2, t = -1$: $3(2) + 5(-1) = 1$. ✓

Step 3: Compute $x = a \cdot nt + b \cdot ms = 2 \cdot 5 \cdot (-1) + 3 \cdot 3 \cdot 2 = -10 + 18 = 8$.

Step 4: Reduce: $x \equiv 8 \pmod{15}$.

Verification: $8 \bmod 3 = 2$ ✓ and $8 \bmod 5 = 3$ ✓. $\blacksquare$

Example 5: CRT Correctness Proof

Problem: Prove that $x = a \cdot nt + b \cdot ms$ solves the system when $ms + nt = 1$.

Proof. Check the first congruence:

(since $m \mid ms$, the term $b \cdot ms \equiv 0 \pmod{m}$).

Now $nt = 1 - ms$, so $nt \equiv 1 \pmod{m}$. Therefore $x \equiv a \cdot 1 = a \pmod{m}$. ✓

By symmetry, $x \equiv b \pmod{n}$. ✓

Uniqueness: If $x_1$ and $x_2$ both solve the system, then $m \mid (x_1 - x_2)$ and $n \mid (x_1 - x_2)$. Since $\gcd(m, n) = 1$, $mn \mid (x_1 - x_2)$, so $x_1 \equiv x_2 \pmod{mn}$. $\blacksquare$

Proof Techniques Spotlight

Strong Induction vs. Ordinary Induction

Why strong induction for FTA: When $n$ is composite ($n = ab$), the factors $a$ and $b$ may be much less than $n - 1$. Ordinary induction gives us only $P(n-1)$, but strong induction gives us $P(a)$ and $P(b)$.

Constructive Proofs

The CRT proof is constructive: it doesn't just assert a solution exists; it gives an explicit formula. This is directly translatable to code — the mathematical construction is the algorithm.

Java Deep Dive

import java.util.*;

public class CRTandFactorization {

    // --- Prime Factorization ---

    public static Map<Integer, Integer> factorize(int n) {
        Map<Integer, Integer> factors = new TreeMap<>();
        for (int d = 2; (long) d * d <= n; d++) {
            while (n % d == 0) { factors.merge(d, 1, Integer::sum); n /= d; }
        }
        if (n > 1) factors.merge(n, 1, Integer::sum);
        return factors;
    }

    /** Reconstructs n from its factorization: product of p^e */
    public static int fromFactors(Map<Integer, Integer> factors) {
        int product = 1;
        for (var entry : factors.entrySet()) {
            for (int i = 0; i < entry.getValue(); i++) product *= entry.getKey();
        }
        return product;
    }

    /**
     * Computes LCM from prime factorizations:
     * lcm(a,b) uses max exponent of each prime.
     */
    public static int lcmFromFactors(int a, int b) {
        var fa = factorize(a);
        var fb = factorize(b);
        Map<Integer, Integer> merged = new TreeMap<>(fa);
        for (var entry : fb.entrySet()) {
            merged.merge(entry.getKey(), entry.getValue(), Math::max);
        }
        return fromFactors(merged);
    }

    // --- GCD and Extended GCD ---

    public static int gcd(int a, int b) {
        a = Math.abs(a); b = Math.abs(b);
        while (b != 0) { int r = a % b; a = b; b = r; }
        return a;
    }

    public static int[] extendedGcd(int a, int b) {
        if (b == 0) return new int[]{a, 1, 0};
        int[] r = extendedGcd(b, a % b);
        return new int[]{r[0], r[2], r[1] - (a / b) * r[2]};
    }

    // --- Chinese Remainder Theorem ---

    /**
     * Solves: x ≡ a (mod m) and x ≡ b (mod n), where gcd(m,n) = 1.
     * Returns x in [0, m*n).
     *
     * Algorithm: Find s,t with ms + nt = 1 (Bézout).
     *            x = a*n*t + b*m*s
     */
    public static int crt(int a, int m, int b, int n) {
        if (gcd(m, n) != 1)
            throw new IllegalArgumentException("Moduli must be coprime");
        int[] bezout = extendedGcd(m, n);
        int s = bezout[1]; // m*s + n*t = 1
        int t = bezout[2];
        // x = a*n*t + b*m*s
        long x = (long) a * n * t + (long) b * m * s;
        return Math.floorMod((int) (x % ((long) m * n)), m * n);
    }

    /**
     * Generalized CRT for multiple congruences:
     * x ≡ a[0] (mod m[0]), x ≡ a[1] (mod m[1]), ..., x ≡ a[k-1] (mod m[k-1])
     * All m[i] must be pairwise coprime.
     */
    public static int crtMultiple(int[] remainders, int[] moduli) {
        int x = remainders[0];
        int mod = moduli[0];
        for (int i = 1; i < remainders.length; i++) {
            x = crt(x, mod, remainders[i], moduli[i]);
            mod *= moduli[i];
        }
        return Math.floorMod(x, mod);
    }

    // --- Simple RSA Demo ---

    /** Modular exponentiation: base^exp mod m */
    public static long modPow(long base, long exp, long mod) {
        long result = 1;
        base = ((base % mod) + mod) % mod;
        while (exp > 0) {
            if (exp % 2 == 1) result = (result * base) % mod;
            base = (base * base) % mod;
            exp /= 2;
        }
        return result;
    }

    /**
     * Simplified RSA demonstration with small primes.
     * NOT for real cryptography — uses small numbers for illustration.
     */
    public static void rsaDemo() {
        System.out.println("=== Simplified RSA Demo ===\n");

        // Step 1: Choose two primes
        int p = 61, q = 53;
        int n = p * q;                // n = 3233 (public modulus)
        int phi = (p - 1) * (q - 1); // φ(n) = 3120

        System.out.println("p = " + p + ", q = " + q);
        System.out.println("n = p*q = " + n);
        System.out.println("φ(n) = (p-1)(q-1) = " + phi);

        // Step 2: Choose public exponent e with gcd(e, φ(n)) = 1
        int e = 17;
        assert gcd(e, phi) == 1 : "e must be coprime to φ(n)";
        System.out.println("Public exponent e = " + e);

        // Step 3: Compute private exponent d = e^(-1) mod φ(n)
        int[] bezout = extendedGcd(e, phi);
        int d = Math.floorMod(bezout[1], phi);
        System.out.println("Private exponent d = " + d);
        System.out.println("Check: e*d mod φ(n) = " + ((long) e * d % phi));

        // Step 4: Encrypt and decrypt
        int message = 42;
        long encrypted = modPow(message, e, n);
        long decrypted = modPow(encrypted, d, n);

        System.out.println("\nMessage: " + message);
        System.out.println("Encrypted: " + encrypted);
        System.out.println("Decrypted: " + decrypted);
        assert decrypted == message;
        System.out.println("Decryption successful!");
    }

    // --- Main ---

    public static void main(String[] args) {
        System.out.println("=== Prime Factorization ===\n");
        for (int n : new int[]{84, 360, 2520, 97, 1000}) {
            var f = factorize(n);
            System.out.printf("  %d = %s  (reconstructed: %d)%n", n,
                factorString(f), fromFactors(f));
        }

        System.out.println("\n=== LCM via Factorization ===\n");
        int[][] lcmTests = {{12, 18}, {35, 15}, {100, 75}};
        for (int[] pair : lcmTests) {
            System.out.printf("  lcm(%d, %d) = %d%n", pair[0], pair[1],
                lcmFromFactors(pair[0], pair[1]));
        }

        System.out.println("\n=== Chinese Remainder Theorem ===\n");
        // x ≡ 2 (mod 3) and x ≡ 3 (mod 5)
        int x1 = crt(2, 3, 3, 5);
        System.out.printf("  x ≡ 2 (mod 3), x ≡ 3 (mod 5) → x = %d (mod 15)%n", x1);
        assert x1 % 3 == 2 && x1 % 5 == 3;

        // Sunzi's original problem: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
        int x2 = crtMultiple(new int[]{2, 3, 2}, new int[]{3, 5, 7});
        System.out.printf("  x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7) → x = %d (mod 105)%n", x2);
        assert x2 % 3 == 2 && x2 % 5 == 3 && x2 % 7 == 2;

        System.out.println();
        rsaDemo();
    }

    static String factorString(Map<Integer, Integer> factors) {
        StringBuilder sb = new StringBuilder();
        for (var entry : factors.entrySet()) {
            if (sb.length() > 0) sb.append(" × ");
            sb.append(entry.getKey());
            if (entry.getValue() > 1) sb.append("^").append(entry.getValue());
        }
        return sb.toString();
    }
}

Historical Context

Euclid (~300 BC) proved that there are infinitely many primes but did not state the Fundamental Theorem of Arithmetic explicitly. The formal proof of unique factorization was first given by Carl Friedrich Gauss in Disquisitiones Arithmeticae (1801).

The Chinese Remainder Theorem originates from Sunzi's Sunzi Suanjing (3rd century CE). The classic problem: "Find a number that leaves remainder 2 when divided by 3, remainder 3 when divided by 5, and remainder 2 when divided by 7." The answer is 23 (modulo 105).

RSA (Rivest, Shamir, Adleman, 1977) is the most famous public-key cryptosystem. Its security relies on the difficulty of factoring large numbers: given $n = pq$ (product of two large primes), finding $p$ and $q$ is computationally hard. The encryption uses modular exponentiation: $c = m^e \bmod n$, and decryption inverts using the private key: $m = c^d \bmod n$, where $ed \equiv 1 \pmod{\phi(n)}$.

Slide-Ready Problem Sets

Slide Set A: Conceptual Questions

A1. Factor $360$ into primes.

A2. True or false: If $p$ is prime and $p \mid 6n$, then $p \mid n$ or $p \leq 3$.

A3. The CRT says the system $x \equiv 1 \pmod{4}$, $x \equiv 2 \pmod{6}$ has a unique solution modulo 24. What's wrong with this claim?

A4. In RSA, why is it important that factoring $n = pq$ is hard?

Slide Set B: Proof Problems

B1. Prove by strong induction: every integer $n > 1$ has a prime factor.

B2. Prove: $\text{lcm}(a, b) = ab / \gcd(a, b)$ using prime factorization.

B3. Prove the CRT for the case $m = 3, n = 5$: the system $x \equiv a \pmod{3}$, $x \equiv b \pmod{5}$ has a unique solution modulo 15.

Slide Set C: Java Coding Problems

C1. Write a method Map<Integer, Integer> factorize(int n) returning a prime-to-exponent map. Verify that fromFactors(factorize(n)) == n for $n = 2, \ldots, 10000$.

C2. Implement a CRT solver for two congruences. Test with Sunzi's original problem.

C3. Write a simplified RSA demo that encrypts and decrypts a single integer message.

Full Problem Set

Discrete Math Problems

DM1. Factor $n = 13860$ into primes. Verify by reconstructing the product.

DM2. Prove: If $p$ is prime and $p \mid a^2$, then $p \mid a$.

DM3. Use the CRT to solve: $x \equiv 3 \pmod{7}$ and $x \equiv 5 \pmod{11}$.

DM4. Prove that $\text{lcm}(a, b) \cdot \gcd(a, b) = ab$ for all positive integers $a, b$.

DM5. Prove: If $n$ has $k$ distinct prime factors, then $n \geq 2^k$.

DM6. Prove that $\sqrt{2}$ is irrational using unique prime factorization. (If $\sqrt{2} = p/q$, then $2q^2 = p^2$; compare the number of 2s in each factorization.)

DM7. Solve the system $x \equiv 1 \pmod{2}$, $x \equiv 2 \pmod{3}$, $x \equiv 3 \pmod{5}$, $x \equiv 4 \pmod{7}$.

Java Programming Problems

JP1. Write Map<Integer, Integer> factorize(int n) and verify FTA for $n = 2, \ldots, 100000$: check that all factors are prime and the product equals $n$.

JP2. Implement int lcm(int a, int b) using the formula $\text{lcm}(a,b) = ab / \gcd(a,b)$. Handle overflow by dividing first: a / gcd(a,b) * b.

JP3. Implement the generalized CRT for an array of congruences (pairwise coprime moduli). Verify that the solution satisfies all congruences.

JP4. Write a simplified RSA key-generation, encryption, and decryption program. Use primes $p$ and $q$ with $pq < 10^6$. Encrypt each letter of a short message individually.

JP5. Given two factorizations (as maps), write methods to compute the GCD and LCM by taking min/max exponents of each prime. Verify against the direct GCD/LCM methods.

JP6. Write a method that determines whether an integer $n$ is a perfect power (i.e., $n = a^k$ for some $a, k \geq 2$) using its prime factorization.

Bridge Problems

BR1. Prove that the trial division algorithm for prime factorization is correct and terminates. Then implement it and verify correctness for $n = 2, \ldots, 50000$.

BR2. Implement a CRT-based method for computing large factorials modulo a product of small primes. For example, compute $100! \bmod 105$ where $105 = 3 \times 5 \times 7$, by computing $100! \bmod 3$, $100! \bmod 5$, and $100! \bmod 7$ separately and combining with CRT.

BR3. Write a program that empirically measures the distribution of prime factorization lengths (number of prime factors with multiplicity) for all integers from 2 to $10^6$, and print a histogram. What's the average number of prime factors?

Solutions

Discrete Math Solutions

DM1. $13860 = 2^2 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11$. Check: $4 \cdot 9 \cdot 5 \cdot 7 \cdot 11 = 4 \cdot 9 \cdot 385 = 36 \cdot 385 = 13860$. ✓

DM2. Write $a = p_1^{e_1} \cdots p_k^{e_k}$. Then $a^2 = p_1^{2e_1} \cdots p_k^{2e_k}$. If $p \mid a^2$, then $p$ appears in the factorization of $a^2$, so $p = p_i$ for some $i$. Then $p \mid a$ (since $e_i \geq 1$). $\blacksquare$

DM3. $\gcd(7, 11) = 1$. Extended GCD: $7(-3) + 11(2) = -21 + 22 = 1$, so $s = -3, t = 2$.

$x = 3 \cdot 11 \cdot 2 + 5 \cdot 7 \cdot (-3) = 66 - 105 = -39 \equiv 38 \pmod{77}$.

Check: $38 \bmod 7 = 3$ ✓, $38 \bmod 11 = 5$ ✓.

DM4. Write $a = \prod p_i^{a_i}$ and $b = \prod p_i^{b_i}$. Then $\gcd(a,b) = \prod p_i^{\min(a_i, b_i)}$ and $\text{lcm}(a,b) = \prod p_i^{\max(a_i, b_i)}$. So $\gcd(a,b) \cdot \text{lcm}(a,b) = \prod p_i^{\min(a_i,b_i) + \max(a_i,b_i)} = \prod p_i^{a_i + b_i} = ab$. $\blacksquare$

DM5. By induction on $k$. Base: $k = 1$, $n \geq 2 = 2^1$. Inductive step: If $n$ has $k + 1$ distinct primes, then $n = p \cdot m$ where $m$ has at least $k$ distinct primes. By hypothesis, $m \geq 2^k$. Since $p \geq 2$, $n = pm \geq 2 \cdot 2^k = 2^{k+1}$. $\blacksquare$

DM6. Suppose $\sqrt{2} = p/q$ with $\gcd(p, q) = 1$. Then $p^2 = 2q^2$. The prime 2 appears an even number of times in $p^2$, but an odd number of times in $2q^2$ (one extra 2). This contradicts unique factorization. $\blacksquare$

DM7. Solve pairwise:

• $x \equiv 1 \pmod{2}$, $x \equiv 2 \pmod{3}$: $x \equiv 5 \pmod{6}$.
• $x \equiv 5 \pmod{6}$, $x \equiv 3 \pmod{5}$: $x \equiv 23 \pmod{30}$.
• $x \equiv 23 \pmod{30}$, $x \equiv 4 \pmod{7}$: $x \equiv 53 \pmod{210}$.

Check: $53 \bmod 2 = 1$ ✓, $53 \bmod 3 = 2$ ✓, $53 \bmod 5 = 3$ ✓, $53 \bmod 7 = 4$ ✓.

Java Solutions

JP1.

public static void verifyFTA(int limit) {
    for (int n = 2; n <= limit; n++) {
        var factors = factorize(n);
        int product = 1;
        for (var entry : factors.entrySet()) {
            assert isPrime(entry.getKey()) : entry.getKey() + " not prime";
            for (int i = 0; i < entry.getValue(); i++) product *= entry.getKey();
        }
        assert product == n : "Product mismatch for " + n;
    }
}

JP2.

public static int lcm(int a, int b) {
    return a / gcd(a, b) * b;  // divide first to reduce overflow risk
}

JP3.

public static int crtMultiple(int[] remainders, int[] moduli) {
    int x = remainders[0], mod = moduli[0];
    for (int i = 1; i < remainders.length; i++) {
        x = crt(x, mod, remainders[i], moduli[i]);
        mod *= moduli[i];
    }
    return Math.floorMod(x, mod);
}

JP4.

public static void rsaEncryptMessage(String msg, int p, int q) {
    int n = p * q;
    int phi = (p - 1) * (q - 1);
    int e = 17;
    while (gcd(e, phi) != 1) e += 2;
    int d = Math.floorMod(extendedGcd(e, phi)[1], phi);

    System.out.println("Public key: (n=" + n + ", e=" + e + ")");
    System.out.println("Private key: d=" + d);

    StringBuilder encrypted = new StringBuilder();
    StringBuilder decrypted = new StringBuilder();
    for (char c : msg.toCharArray()) {
        long enc = modPow(c, e, n);
        long dec = modPow(enc, d, n);
        encrypted.append(enc).append(" ");
        decrypted.append((char) dec);
    }
    System.out.println("Encrypted: " + encrypted);
    System.out.println("Decrypted: " + decrypted);
}

JP5.

public static Map<Integer, Integer> gcdFromFactors(
        Map<Integer, Integer> fa, Map<Integer, Integer> fb) {
    Map<Integer, Integer> result = new TreeMap<>();
    for (int p : fa.keySet()) {
        if (fb.containsKey(p)) {
            result.put(p, Math.min(fa.get(p), fb.get(p)));
        }
    }
    return result;
}

public static Map<Integer, Integer> lcmFromFactors(
        Map<Integer, Integer> fa, Map<Integer, Integer> fb) {
    Map<Integer, Integer> result = new TreeMap<>(fa);
    for (var entry : fb.entrySet()) {
        result.merge(entry.getKey(), entry.getValue(), Math::max);
    }
    return result;
}

JP6.

public static boolean isPerfectPower(int n) {
    var factors = factorize(n);
    if (factors.isEmpty()) return false;
    int g = 0;
    for (int exp : factors.values()) g = gcd(g, exp);
    return g >= 2;
}
// Examples: 8 = 2^3 → gcd(3) = 3 ≥ 2 → true
//           12 = 2^2 × 3 → gcd(2,1) = 1 < 2 → false
//           64 = 2^6 → gcd(6) = 6 ≥ 2 → true

Bridge Solutions

BR1. Correctness: The loop extracts factor $d$ as many times as it divides $n$. After the inner while, $d \nmid n$, so $d$ is fully extracted. After the outer for loop, all factors $\leq \sqrt{n_{\text{current}}}$ are extracted. If $n > 1$ remains, it must be prime (if it were composite, it would have a factor $\leq$ its own square root, contradicting the loop's completion).

Termination: Each inner while iteration strictly reduces $n$. The outer loop's bound $d^2 \leq n$ shrinks each iteration. $\blacksquare$

BR2.

public static int factorialModCRT(int n, int[] primes) {
    int[] remainders = new int[primes.length];
    for (int i = 0; i < primes.length; i++) {
        long factMod = 1;
        for (int j = 1; j <= n; j++) {
            factMod = (factMod * j) % primes[i];
        }
        remainders[i] = (int) factMod;
    }
    return crtMultiple(remainders, primes);
}
// For 100! mod 105: 100! mod 3 = 0, 100! mod 5 = 0, 100! mod 7 = 0
// So 100! mod 105 = 0 (since 3, 5, 7 all divide 100!)

BR3.

public static void primeFactorHistogram(int limit) {
    int[] counts = new int[30]; // counts[k] = how many n have k prime factors
    long totalFactors = 0;
    for (int n = 2; n <= limit; n++) {
        int numFactors = 0;
        int temp = n;
        for (int d = 2; (long) d * d <= temp; d++) {
            while (temp % d == 0) { numFactors++; temp /= d; }
        }
        if (temp > 1) numFactors++;
        counts[numFactors]++;
        totalFactors += numFactors;
    }
    System.out.printf("Average # prime factors (2..%d): %.2f%n",
        limit, (double) totalFactors / (limit - 1));
    for (int k = 1; k < counts.length && counts[k] > 0; k++) {
        System.out.printf("  %2d factors: %d numbers%n", k, counts[k]);
    }
}