Module 1 – Class 1: Parity and Variables
Learning Objectives
By the end of this class, students will be able to:
- State the formal definitions of even and odd integers using existential quantifiers.
- Write direct proofs about parity (even/odd) properties of sums and products.
- Disprove false claims by constructing counterexamples.
- Implement Java methods that test parity and connect each line of code to its mathematical definition.
- Explain how parity relates to computational concepts such as checksums and hash functions.
Concept Overview
What Are Integers?
The integers are the set $\mathbb{Z} = \{\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots\}$. They include all positive whole numbers, all negative whole numbers, and zero. In computer science, integers are the most fundamental data type — every program manipulates them.
Even and Odd: The First Definitions
Mathematics is built on definitions. Before we can prove anything about numbers, we must agree on exactly what our words mean.
Definition (Even). An integer $n$ is even if there exists an integer $k$ such that $n = 2k$.
Definition (Odd). An integer $n$ is odd if there exists an integer $k$ such that $n = 2k + 1$.
These definitions are exhaustive: every integer is either even or odd, never both. This is because dividing any integer by 2 leaves remainder 0 (even) or 1 (odd) — there are no other possibilities.
Plain Language
- Even means "divisible by 2 with no remainder." Examples: $-4, 0, 2, 14, 100$.
- Odd means "leaves remainder 1 when divided by 2." Examples: $-3, 1, 7, 15, 99$.
The key insight is that these English descriptions are informal. The mathematical definitions above are formal — they give us something precise to work with in proofs.
Why Definitions Matter
In programming, a bug often comes from a vague specification. In mathematics, a wrong proof often comes from a vague definition. The habit of starting with precise definitions transfers directly to writing clear code specifications.
Formal Notation
Set Membership
We write $a \in \mathbb{Z}$ to mean "$a$ is an integer." The symbol $\in$ means "is an element of."
Existential Quantifier
The statement "$n$ is even" is formally written:
Read this as: "There exists an integer $k$ such that $n$ equals $2k$."
Similarly, "$n$ is odd" is:
Common Pitfalls
| Pitfall | Why It's Wrong |
|---|---|
| Writing $n = 2k$ without specifying $k \in \mathbb{Z}$ | The $k$ must be an integer — if $k = 1.5$, then $2(1.5) = 3$ but $k$ is not an integer witness |
| Assuming $k$ is positive | Negative numbers can be even too: $-6 = 2(-3)$, so $k = -3$ |
| Confusing "even" with "positive even" | Zero is even: $0 = 2(0)$ |
| Using the same variable $k$ for two different unknowns in one proof | Each unknown needs its own name |
Worked Examples
Example 1: Prove That the Sum of Two Even Numbers Is Even (Discrete Math)
Claim. If $a$ and $b$ are even integers, then $a + b$ is even.
Proof.
Step 1 — Unpack the definitions. Since $a$ is even, there exists an integer $m$ such that $a = 2m$. Since $b$ is even, there exists an integer $n$ such that $b = 2n$.
Step 2 — Compute the sum.
Step 3 — Apply the definition. Let $k = m + n$. Since $m$ and $n$ are integers, $k$ is an integer (integers are closed under addition). Therefore $a + b = 2k$, which means $a + b$ is even by definition. $\blacksquare$
Structure of a Direct Proof:
- State what you are given (hypotheses).
- Unpack the definitions to get equations.
- Do algebra to reach the form required by the conclusion's definition.
- Identify the witness integer and confirm it is an integer.
- State the conclusion.
Example 2: The Sum of Two Even Numbers in Java (Java Translation)
Here is a complete, runnable Java program that tests the claim from Example 1:
/**
* ParityDemo.java
* Demonstrates the connection between the mathematical definition
* of even/odd and Java's modulo operator.
*/
public class ParityDemo {
/**
* Returns true if x is even.
* Mathematical basis: x is even iff there exists k in Z such that x = 2k.
* Java implementation: x % 2 == 0 checks whether the remainder upon
* division by 2 is zero, which is equivalent to the definition.
*/
public static boolean isEven(int x) {
return x % 2 == 0;
}
/**
* Returns true if x is odd.
* Mathematical basis: x is odd iff there exists k in Z such that x = 2k+1.
* Java note: we check x % 2 != 0 rather than x % 2 == 1 because
* Java's % operator can return -1 for negative odd numbers.
* For example, (-3) % 2 == -1 in Java, not 1.
*/
public static boolean isOdd(int x) {
return x % 2 != 0;
}
/**
* Tests the theorem: the sum of two even integers is even.
* Tries many pairs and reports any counterexample found.
*/
public static void testSumOfEvens() {
System.out.println("Testing: sum of two even numbers is even");
for (int a = -100; a <= 100; a += 2) { // a is even
for (int b = -100; b <= 100; b += 2) { // b is even
if (!isEven(a + b)) {
System.out.println(" COUNTEREXAMPLE: a=" + a + ", b=" + b);
return;
}
}
}
System.out.println(" Passed for all tested pairs.");
}
public static void main(String[] args) {
// Basic demonstrations
System.out.println("isEven(4) = " + isEven(4)); // true
System.out.println("isEven(7) = " + isEven(7)); // false
System.out.println("isOdd(7) = " + isOdd(7)); // true
System.out.println("isOdd(-3) = " + isOdd(-3)); // true
System.out.println("isEven(0) = " + isEven(0)); // true
System.out.println();
testSumOfEvens();
}
}Sample Output:
isEven(4) = true
isEven(7) = false
isOdd(7) = true
isOdd(-3) = true
isEven(0) = true
Testing: sum of two even numbers is even
Passed for all tested pairs.Line-by-line connection to math:
| Java Code | Mathematical Concept |
|---|---|
x % 2 == 0 |
Checking $\exists k: x = 2k$, i.e., the remainder is 0 |
x % 2 != 0 |
Checking $\exists k: x = 2k+1$ (remainder is not 0) |
a += 2 in loop |
Generating only even numbers (multiples of 2) |
!isEven(a + b) |
Searching for a counterexample to the theorem |
| The loop finding none | Empirical evidence (but not a proof!) that the theorem holds |
Important distinction: The Java test is not a proof. It only checks finitely many cases. The mathematical proof covers all integers — infinitely many. This is why we need both: proofs give certainty, code gives intuition and verification for specific cases.
Example 3: Prove That the Product of Two Odd Numbers Is Odd (Combined DM + Java)
Claim. If $a$ and $b$ are odd integers, then $a \cdot b$ is odd.
Proof.
Since $a$ is odd, $a = 2m + 1$ for some integer $m$.
Since $b$ is odd, $b = 2n + 1$ for some integer $n$.
Compute the product:
Let $k = 2mn + m + n$. Since $m, n \in \mathbb{Z}$, we have $k \in \mathbb{Z}$ (integers are closed under multiplication and addition). Therefore $a \cdot b = 2k + 1$, which is odd by definition. $\blacksquare$
Java Verification:
/**
* Verifies: the product of two odd integers is odd.
*/
public static void testProductOfOdds() {
System.out.println("Testing: product of two odd numbers is odd");
for (int a = -99; a <= 99; a += 2) { // odd values
for (int b = -99; b <= 99; b += 2) { // odd values
if (!isOdd(a * b)) {
System.out.println(" COUNTEREXAMPLE: a=" + a + ", b=" + b);
return;
}
}
}
System.out.println(" Passed for all tested pairs.");
}What makes this a "bridge" example: The proof establishes the result for all integers. The Java code then provides a concrete computational check. Students see that the algebraic manipulation $4mn + 2m + 2n + 1 = 2(2mn+m+n)+1$ is mirrored by the code testing isOdd(a * b) — both rely on the same underlying definition of oddness.
Example 4: Disprove a False Claim Using a Counterexample
False Claim. "The sum of two odd numbers is odd."
Disproof. We need only one counterexample. Let $a = 3$ and $b = 5$. Then $a + b = 8 = 2(4)$, which is even, not odd. Therefore the claim is false. $\blacksquare$
What is actually true? The sum of two odd integers is always even. Let's prove it:
$a = 2m+1$, $b = 2n+1$, so $a + b = 2m + 1 + 2n + 1 = 2(m+n+1)$, which is even.
Java Counterexample Finder:
/**
* Attempts to find a counterexample to: "sum of two odds is odd."
* Finds one immediately because the claim is false.
*/
public static void findCounterexample() {
System.out.println("Searching for counterexample to: sum of two odds is odd");
for (int a = 1; a <= 20; a += 2) {
for (int b = 1; b <= 20; b += 2) {
if (!isOdd(a + b)) {
System.out.println(" Found: " + a + " + " + b + " = " + (a + b)
+ " which is EVEN. Claim disproved!");
return;
}
}
}
System.out.println(" No counterexample found (claim may be true).");
}Output:
Searching for counterexample to: sum of two odds is odd
Found: 1 + 1 = 2 which is EVEN. Claim disproved!Example 5: Parity of Squares
Claim. If $n$ is even, then $n^2$ is even. If $n$ is odd, then $n^2$ is odd.
Proof (even case). Let $n = 2k$. Then $n^2 = (2k)^2 = 4k^2 = 2(2k^2)$. Since $2k^2$ is an integer, $n^2$ is even.
Proof (odd case). Let $n = 2k+1$. Then $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2+2k) + 1$. Since $2k^2+2k$ is an integer, $n^2$ is odd.
Combined result: $n^2$ has the same parity as $n$.
/**
* Demonstrates: n^2 has the same parity as n.
*/
public static void testSquareParity() {
System.out.println("Testing: n^2 has the same parity as n");
for (int n = -50; n <= 50; n++) {
boolean sameParityEven = isEven(n) && isEven(n * n);
boolean sameParityOdd = isOdd(n) && isOdd(n * n);
if (!(sameParityEven || sameParityOdd)) {
System.out.println(" COUNTEREXAMPLE: n=" + n);
return;
}
}
System.out.println(" Passed for all tested values.");
}Proof Techniques Spotlight
Direct Proof from Definitions
This class introduces the most fundamental proof technique: direct proof.
Template:
Claim: If [hypothesis], then [conclusion].
>
Proof.
Assume [hypothesis].
By definition, [unpack hypothesis into equations].
[Algebraic manipulation].
Therefore [conclusion is satisfied by definition]. $\blacksquare$
Step-by-step recipe:
- Write down what you know. List the hypotheses. Use the definition to translate each hypothesis into an equation (e.g., "$a$ is even" becomes "$a = 2m$ for some $m \in \mathbb{Z}$").
- Write down what you want to show. State the conclusion and identify what form you need (e.g., "we need to show $a + b = 2k$ for some integer $k$").
- Do algebra. Substitute, expand, factor — whatever leads from the known equations to the desired form.
- Identify the witness. Name the integer that makes the conclusion's definition work (e.g., "$k = m + n$") and confirm it is the right type ($k \in \mathbb{Z}$).
- State the conclusion explicitly.
Counterexample
To disprove a universal claim "for all $x$, $P(x)$," you need only find one $x$ where $P(x)$ is false.
Template:
Claim (false): For all integers $n$, [property].
>
Disproof. Let $n = $ [specific value]. Then [show property fails]. Therefore the claim is false. $\blacksquare$
Common Mistakes
| Mistake | Correction |
|---|---|
| Proving by example: "4 + 6 = 10, which is even, so the sum of two evens is even" | One example does not prove a universal claim — you must prove it for all even numbers |
| Using the same variable for two different unknowns: "$a = 2k$ and $b = 2k$" | This forces $a = b$. Use different variables: "$a = 2m$ and $b = 2n$" |
| Forgetting to say why the witness is an integer | Always state "since $m, n \in \mathbb{Z}$, we have $m+n \in \mathbb{Z}$" |
| Proving the converse instead of the original statement | "If $a+b$ is even then $a$ and $b$ are even" is different from "if $a, b$ are even then $a+b$ is even" (and actually false!) |
Java Deep Dive
Complete Runnable Program: Parity Library
This program implements all the parity concepts from this class as a self-contained Java file.
/**
* ParityLibrary.java
* A complete library of parity-related methods with mathematical documentation.
*
* MATHEMATICAL FOUNDATION:
* - Even: n is even iff ∃k∈Z such that n = 2k
* - Odd: n is odd iff ∃k∈Z such that n = 2k + 1
* - Every integer is exactly one of even or odd (never both, never neither)
*/
public class ParityLibrary {
// =========================================================
// CORE PARITY TESTS
// =========================================================
/**
* Tests whether n is even.
*
* Math: n is even ↔ n = 2k for some k ∈ Z
* Code: n % 2 == 0 tests whether 2 divides n with remainder 0
*
* Why this works: By the quotient-remainder theorem, n = 2q + r
* where r ∈ {0, 1}. If r == 0, then n = 2q, so n is even.
*
* Edge cases:
* isEven(0) → true (0 = 2·0)
* isEven(-4) → true (-4 = 2·(-2))
*/
public static boolean isEven(int n) {
return n % 2 == 0;
}
/**
* Tests whether n is odd.
*
* Math: n is odd ↔ n = 2k + 1 for some k ∈ Z
* Code: n % 2 != 0 (NOT n % 2 == 1, because Java's % can return -1)
*
* Why n % 2 != 0 instead of n % 2 == 1:
* In Java, (-3) % 2 == -1, not 1.
* But (-3) is odd because -3 = 2(-2) + 1.
* So we use != 0 to handle negative numbers correctly.
*/
public static boolean isOdd(int n) {
return n % 2 != 0;
}
// =========================================================
// FINDING THE WITNESS
// =========================================================
/**
* If n is even, returns the integer k such that n = 2k.
* This is the "witness" in the existential definition.
*
* Precondition: n must be even.
*/
public static int evenWitness(int n) {
assert isEven(n) : "Precondition violated: " + n + " is not even";
return n / 2; // n = 2k → k = n/2
}
/**
* If n is odd, returns the integer k such that n = 2k + 1.
*
* Precondition: n must be odd.
*/
public static int oddWitness(int n) {
assert isOdd(n) : "Precondition violated: " + n + " is not odd";
return (n - 1) / 2; // n = 2k+1 → k = (n-1)/2
}
// =========================================================
// THEOREM VERIFIERS
// =========================================================
/**
* Verifies: even + even = even
* Math: if a = 2m and b = 2n, then a+b = 2(m+n) which is even.
*/
public static boolean verifyEvenPlusEven(int a, int b) {
if (!isEven(a) || !isEven(b)) return true; // hypothesis not met
return isEven(a + b);
}
/**
* Verifies: odd + odd = even
* Math: if a = 2m+1 and b = 2n+1, then a+b = 2(m+n+1) which is even.
*/
public static boolean verifyOddPlusOdd(int a, int b) {
if (!isOdd(a) || !isOdd(b)) return true; // hypothesis not met
return isEven(a + b);
}
/**
* Verifies: even + odd = odd
* Math: if a = 2m and b = 2n+1, then a+b = 2(m+n)+1 which is odd.
*/
public static boolean verifyEvenPlusOdd(int a, int b) {
if (!isEven(a) || !isOdd(b)) return true;
return isOdd(a + b);
}
/**
* Verifies: odd * odd = odd
* Math: if a = 2m+1 and b = 2n+1, then ab = 2(2mn+m+n)+1 which is odd.
*/
public static boolean verifyOddTimesOdd(int a, int b) {
if (!isOdd(a) || !isOdd(b)) return true;
return isOdd(a * b);
}
/**
* Verifies: even * anything = even
* Math: if a = 2m, then ab = 2(mb), which is even.
*/
public static boolean verifyEvenTimesAnything(int a, int b) {
if (!isEven(a)) return true;
return isEven(a * b);
}
// =========================================================
// COMPLETE PARITY TABLE
// =========================================================
/**
* Prints a summary table of parity rules verified by exhaustive testing.
*/
public static void printParityTable() {
System.out.println("=== PARITY RULES (verified for n in [-1000, 1000]) ===");
System.out.println();
String[] rules = {
"even + even = even",
"odd + odd = even",
"even + odd = odd",
"odd * odd = odd",
"even * any = even"
};
boolean allPassed = true;
int range = 100;
// Test each rule
for (int a = -range; a <= range; a++) {
for (int b = -range; b <= range; b++) {
if (!verifyEvenPlusEven(a, b)) { allPassed = false; System.out.println("FAIL: even+even at " + a + "," + b); }
if (!verifyOddPlusOdd(a, b)) { allPassed = false; System.out.println("FAIL: odd+odd at " + a + "," + b); }
if (!verifyEvenPlusOdd(a, b)) { allPassed = false; System.out.println("FAIL: even+odd at " + a + "," + b); }
if (!verifyOddTimesOdd(a, b)) { allPassed = false; System.out.println("FAIL: odd*odd at " + a + "," + b); }
if (!verifyEvenTimesAnything(a, b)) { allPassed = false; System.out.println("FAIL: even*any at " + a + "," + b); }
}
}
if (allPassed) {
System.out.println("All rules passed for integers in [-" + range + ", " + range + "].");
}
System.out.println();
System.out.println("Summary of Parity Arithmetic:");
System.out.println("+--------+-------+--------+");
System.out.println("| + | even | odd |");
System.out.println("+--------+-------+--------+");
System.out.println("| even | even | odd |");
System.out.println("| odd | odd | even |");
System.out.println("+--------+-------+--------+");
System.out.println();
System.out.println("+--------+-------+--------+");
System.out.println("| * | even | odd |");
System.out.println("+--------+-------+--------+");
System.out.println("| even | even | even |");
System.out.println("| odd | even | odd |");
System.out.println("+--------+-------+--------+");
}
// =========================================================
// MAIN — RUN ALL DEMONSTRATIONS
// =========================================================
public static void main(String[] args) {
System.out.println("==================================");
System.out.println(" PARITY AND VARIABLES — CLASS 1 ");
System.out.println("==================================");
System.out.println();
// Demo 1: Basic parity checks
System.out.println("--- Basic Parity Checks ---");
int[] samples = {-6, -3, 0, 1, 4, 7, 12, 15};
for (int n : samples) {
String parity = isEven(n) ? "even" : "odd";
System.out.printf(" %4d is %s%n", n, parity);
}
System.out.println();
// Demo 2: Finding witnesses
System.out.println("--- Witnesses (the k in n = 2k or n = 2k+1) ---");
for (int n : samples) {
if (isEven(n)) {
int k = evenWitness(n);
System.out.printf(" %4d = 2 * %d (k = %d)%n", n, k, k);
} else {
int k = oddWitness(n);
System.out.printf(" %4d = 2 * %d + 1 (k = %d)%n", n, k, k);
}
}
System.out.println();
// Demo 3: Parity table
printParityTable();
}
}Sample Output:
==================================
PARITY AND VARIABLES — CLASS 1
==================================
--- Basic Parity Checks ---
-6 is even
-3 is odd
0 is even
1 is odd
4 is even
7 is odd
12 is even
15 is odd
--- Witnesses (the k in n = 2k or n = 2k+1) ---
-6 = 2 * -3 (k = -3)
-3 = 2 * -2 + 1 (k = -2)
0 = 2 * 0 (k = 0)
1 = 2 * 0 + 1 (k = 0)
4 = 2 * 2 (k = 2)
7 = 2 * 3 + 1 (k = 3)
12 = 2 * 6 (k = 6)
15 = 2 * 7 + 1 (k = 7)
All rules passed for integers in [-100, 100].
Summary of Parity Arithmetic:
+--------+-------+--------+
| + | even | odd |
+--------+-------+--------+
| even | even | odd |
| odd | odd | even |
+--------+-------+--------+
+--------+-------+--------+
| * | even | odd |
+--------+-------+--------+
| even | even | even |
| odd | even | odd |
+--------+-------+--------+Computational Use: Parity in Computer Science
Checksums
A checksum is a simple error-detection scheme. The simplest version adds up bytes of data and checks whether the sum is even or odd. If a single bit flips during transmission, the parity of the sum changes, and the error is detected. This is called a parity bit.
Hash Tables and Indexing
Hash functions often use % m to map keys to buckets. When $m = 2$, this is simply a parity check — the key goes into bucket 0 (even) or bucket 1 (odd). More generally, key % tableSize generalizes the idea of parity to arbitrary moduli.
Alternating Behavior
Many algorithms alternate behavior based on parity: even-indexed elements vs. odd-indexed elements, alternating turns in game trees, alternating directions in bidirectional search.
Historical Context
Euclid (c. 300 BC) devoted Books VII–IX of the Elements to number theory. He defined even and odd numbers and proved basic properties of parity and divisibility using geometric arguments. His proofs, while geometric rather than algebraic, follow the same logical structure we use today — start from definitions, chain deductions.
The Greeks classified numbers into even and odd, perfect and abundant, prime and composite. Parity was the first classification: the simplest way to partition infinitely many objects into two classes.
Why this matters for CS: Computer science inherited this axiomatic style. When we write program specifications or define data structures, we are doing exactly what Euclid did — starting from definitions and deducing properties.
Slide-Ready Problem Sets
Slide Set A: Conceptual Questions (Warm-Up / Quick Check)
A1. True or false: Zero is an even number. Justify using the definition.
A2. True or false: The number $-7$ is odd. Find the integer $k$ such that $-7 = 2k + 1$.
A3. Is $1$ even or odd? What about $1^{100}$? What about $(-1)^{100}$? Explain.
A4. A student says: "I checked $2 + 4 = 6$, $6 + 8 = 14$, and $10 + 12 = 22$, so the sum of two evens is always even." What is wrong with this reasoning?
Slide Set B: Proof Problems (Class Discussion)
B1. Prove: If $n$ is an odd integer, then $n + 1$ is even.
B2. Prove: If $a$ is even and $b$ is odd, then $a + b$ is odd.
B3. Disprove: "If $n^2$ is even, then $n$ is even and $n > 0$." (Find a counterexample.)
B4. Prove or disprove: The sum of three consecutive integers is always divisible by 3.
Slide Set C: Java Coding Problems (Code Along)
C1. Write a method public static String parityLabel(int n) that returns "even" or "odd". Test it with $n = -10, -3, 0, 1, 42$.
C2. Write a method public static int countEvens(int[] arr) that returns the number of even elements in the array. What mathematical concept does the loop implement? (Answer: it computes $|\{i : \text{arr}[i] \text{ is even}\}|$.)
C3. Write a method public static boolean sumParityCheck(int a, int b) that returns true if a + b has the expected parity based on the parity of a and b (using the parity addition table). Test with 10 random pairs.
C4. Java's % operator behaves differently for negative numbers. What does (-7) % 2 return in Java? How does this affect isOdd?
Full Problem Set
Discrete Math Problems
DM1. Prove: If $a$ is an even integer and $b$ is an even integer, then $a - b$ is even.
DM2. Prove: If $n$ is odd, then $n^2 - 1$ is divisible by 8. (Hint: write $n = 2k+1$ and factor $n^2 - 1 = (n-1)(n+1)$.)
DM3. Prove: The product of any integer with an even integer is even.
DM4. Disprove: "For all integers $n$, if $n^2$ is odd, then $n > 0$."
DM5. Prove: For any integer $n$, the expression $n^2 + n$ is always even. (Hint: consider two cases — $n$ even and $n$ odd.)
DM6. Prove: If $a$ and $b$ are both odd, then $a^2 + b^2$ is even but not divisible by 4.
DM7. Prove or disprove: "The sum of four consecutive integers is always even."
Java Programming Problems
JP1. Write a method public static boolean allEven(int[] arr) that returns true if every element in the array is even. Connect this to the mathematical statement $\forall i \in \{0, \ldots, n-1\},\; \text{arr}[i] \text{ is even}$.
JP2. Write a method public static int[] separateByParity(int[] arr) that returns a new array with all even elements first, then all odd elements. Verify that evens and odds are in the correct positions.
JP3. Write a method public static boolean parityPreservedBySquare(int n) that checks whether $n$ and $n^2$ have the same parity. Test it for $n = -100$ to $100$.
JP4. Implement public static void printParityTable(int from, int to) that prints each integer in the range and its parity. Format the output in two columns.
JP5. Write a method public static int findFirstOdd(int[] arr) that returns the first odd element, or throws NoSuchElementException if there is none. What mathematical concept does "returns first odd" correspond to? (Answer: existential witness.)
JP6. The Collatz conjecture says: start with any positive integer $n$. If $n$ is even, divide by 2; if $n$ is odd, compute $3n + 1$. Repeat. The conjecture says you always reach 1. Write a method public static int collatzSteps(int n) that returns the number of steps to reach 1. Test for $n = 1$ to $100$. (This uses parity as a branching condition.)
Bridge Problems (Discrete Math + Java)
BR1. Prove and Verify. Prove that $n(n+1)$ is even for all integers $n$ (use cases: $n$ even and $n$ odd). Then write a Java method that checks this for $n = -1000$ to $1000$.
BR2. Proof to Code. The proof that "odd + odd = even" uses the witness $k = m + n + 1$ where $a = 2m+1$ and $b = 2n+1$. Write a method public static int sumWitness(int a, int b) that, given two odd integers, computes and returns this witness $k$ and verifies that $a + b = 2k$.
BR3. Code to Proof. A student wrote this Java method:
public static boolean mysteryCheck(int n) {
return (n * n) % 4 == 0 || (n * n) % 4 == 1;
}What does this method check? State and prove the mathematical theorem that guarantees mysteryCheck always returns true.
(Answer: For any integer $n$, $n^2 \mod 4$ is either 0 or 1. Proof: if $n$ is even, $n = 2k$, so $n^2 = 4k^2 \equiv 0 \pmod{4}$. If $n$ is odd, $n = 2k+1$, so $n^2 = 4k^2 + 4k + 1 \equiv 1 \pmod{4}$.)
Solutions
Discrete Math Solutions
DM1 Solution. Let $a = 2m$ and $b = 2n$ for $m, n \in \mathbb{Z}$. Then $a - b = 2m - 2n = 2(m-n)$. Since $m - n \in \mathbb{Z}$, $a - b$ is even. $\blacksquare$
DM2 Solution. Let $n = 2k + 1$ for some $k \in \mathbb{Z}$. Then:
Since $k$ and $k+1$ are consecutive integers, one of them is even, so $k(k+1)$ is even. Write $k(k+1) = 2j$ for some $j \in \mathbb{Z}$. Then $n^2 - 1 = 4(2j) = 8j$. Therefore $8 \mid (n^2 - 1)$. $\blacksquare$
DM3 Solution. Let $a$ be any integer and $b = 2k$ for some $k \in \mathbb{Z}$. Then $a \cdot b = a \cdot 2k = 2(ak)$. Since $ak \in \mathbb{Z}$, the product is even. $\blacksquare$
DM4 Solution. Counterexample: $n = -3$. Then $n^2 = 9$, which is odd, but $n = -3 < 0$. $\blacksquare$
DM5 Solution. Case 1: $n$ is even, $n = 2k$. Then $n^2 + n = 4k^2 + 2k = 2(2k^2 + k)$, which is even.
Case 2: $n$ is odd, $n = 2k+1$. Then $n^2 + n = (2k+1)^2 + (2k+1) = 4k^2 + 4k + 1 + 2k + 1 = 4k^2 + 6k + 2 = 2(2k^2 + 3k + 1)$, which is even.
Alternatively: $n^2 + n = n(n+1)$, and consecutive integers always include one even number. $\blacksquare$
DM6 Solution. Let $a = 2m+1$ and $b = 2n+1$. Then:
This equals $2(2m^2 + 2m + 2n^2 + 2n + 1)$, which is even. But $2m^2 + 2m + 2n^2 + 2n + 1$ is odd (it is $2(m^2+m+n^2+n) + 1$). So $a^2 + b^2 = 2 \times \text{odd}$, which means $a^2 + b^2$ is divisible by 2 but not by 4. $\blacksquare$
DM7 Solution. Let the four consecutive integers be $n, n+1, n+2, n+3$. Their sum is $4n + 6 = 2(2n+3)$, which is even. The claim is true. $\blacksquare$
Java Solutions
JP1 Solution.
public static boolean allEven(int[] arr) {
for (int x : arr) { // ∀ element x in arr
if (x % 2 != 0) { // if x is not even
return false; // the universal claim fails
}
}
return true; // all elements passed the test
}
// Mathematically: returns ∀i ∈ {0,...,arr.length-1}: arr[i] mod 2 = 0JP2 Solution.
public static int[] separateByParity(int[] arr) {
int[] result = new int[arr.length];
int left = 0; // index for evens
int right = arr.length - 1; // index for odds
for (int x : arr) {
if (x % 2 == 0) {
result[left++] = x; // place even elements at front
} else {
result[right--] = x; // place odd elements at back
}
}
return result;
}JP3 Solution.
public static boolean parityPreservedBySquare(int n) {
// Theorem: n and n^2 have the same parity.
boolean nEven = (n % 2 == 0);
boolean sqEven = ((n * n) % 2 == 0);
return nEven == sqEven;
}
// Test:
public static void testParityPreserved() {
for (int n = -100; n <= 100; n++) {
assert parityPreservedBySquare(n) : "Failed for n=" + n;
}
System.out.println("Parity preserved by squaring: all tests passed.");
}JP4 Solution.
public static void printParityTable(int from, int to) {
System.out.printf("%-10s %-10s%n", "Number", "Parity");
System.out.println("--------------------");
for (int n = from; n <= to; n++) {
System.out.printf("%-10d %-10s%n", n, (n % 2 == 0) ? "even" : "odd");
}
}JP5 Solution.
import java.util.NoSuchElementException;
public static int findFirstOdd(int[] arr) {
for (int x : arr) { // existential search: ∃x ∈ arr such that x is odd
if (x % 2 != 0) {
return x; // found the witness
}
}
throw new NoSuchElementException("No odd element found");
}JP6 Solution.
public static int collatzSteps(int n) {
if (n <= 0) throw new IllegalArgumentException("n must be positive");
int steps = 0;
while (n != 1) {
if (n % 2 == 0) { // n is even: divide by 2
n = n / 2;
} else { // n is odd: compute 3n + 1
n = 3 * n + 1;
}
steps++;
}
return steps;
}
// Test:
public static void testCollatz() {
System.out.printf("%-5s %-10s%n", "n", "Steps");
for (int n = 1; n <= 20; n++) {
System.out.printf("%-5d %-10d%n", n, collatzSteps(n));
}
}Bridge Problem Solutions
BR1 Solution.
Proof: Case 1: $n$ is even, $n = 2k$. Then $n(n+1) = 2k(2k+1) = 2[k(2k+1)]$, which is even.
Case 2: $n$ is odd, $n = 2k+1$. Then $n+1 = 2k+2 = 2(k+1)$, so $n(n+1) = (2k+1) \cdot 2(k+1) = 2[(2k+1)(k+1)]$, which is even. $\blacksquare$
Java:
public static void verifyConsecutiveProduct() {
for (int n = -1000; n <= 1000; n++) {
long product = (long) n * (n + 1); // use long to avoid overflow
assert product % 2 == 0 : "Failed for n=" + n;
}
System.out.println("n(n+1) is always even: verified for n in [-1000, 1000].");
}BR2 Solution.
/**
* Given two odd integers a, b, computes the witness k
* such that a + b = 2k.
*
* Math: a = 2m+1, b = 2n+1, so a+b = 2(m+n+1).
* The witness is k = m + n + 1 = (a-1)/2 + (b-1)/2 + 1 = (a+b)/2.
*/
public static int sumWitness(int a, int b) {
assert a % 2 != 0 : a + " is not odd";
assert b % 2 != 0 : b + " is not odd";
int sum = a + b;
int k = sum / 2; // k = m + n + 1
assert sum == 2 * k : "Witness verification failed";
return k;
}BR3 Solution.
The method checks whether $n^2 \mod 4 \in \{0, 1\}$.
Theorem: For any integer $n$, $n^2 \equiv 0 \pmod{4}$ or $n^2 \equiv 1 \pmod{4}$.
Proof:
- If $n$ is even, write $n = 2k$. Then $n^2 = 4k^2$, so $n^2 \equiv 0 \pmod{4}$.
- If $n$ is odd, write $n = 2k+1$. Then $n^2 = 4k^2 + 4k + 1$, so $n^2 \equiv 1 \pmod{4}$.
In either case, $n^2 \mod 4$ is 0 or 1. Therefore mysteryCheck always returns true. $\blacksquare$
Module 1 – Class 2: Divisibility Relations
Learning Objectives
By the end of this class, students will be able to:
- State the formal definition of divisibility and use the notation $a \mid b$.
- Prove that the divisibility relation is transitive using a direct proof.
- Prove that if $a$ divides two numbers, then $a$ divides any linear combination of those numbers.
- Implement a
dividesmethod in Java and connect it to the mathematical definition. - Compose divisibility tests to verify transitivity computationally.
Concept Overview
What Is Divisibility?
Divisibility is a relationship between two integers that generalizes the idea of "goes into evenly."
Definition (Divisibility). Let $a, b \in \mathbb{Z}$ with $a \neq 0$. We say $a$ divides $b$, written $a \mid b$, if there exists an integer $k$ such that $b = a \cdot k$.
When $a \mid b$, we also say:
- "$a$ is a divisor of $b$"
- "$a$ is a factor of $b$"
- "$b$ is a multiple of $a$"
- "$b$ is divisible by $a$"
Plain Language
$a \mid b$ means: when you divide $b$ by $a$, there is no remainder. Equivalently, $b$ is some number of "$a$s."
Examples:
- $3 \mid 12$ because $12 = 3 \times 4$ (the witness is $k = 4$)
- $5 \mid 0$ because $0 = 5 \times 0$ (the witness is $k = 0$; zero is divisible by everything)
- $7 \nmid 15$ because there is no integer $k$ with $15 = 7k$ (we get $k = 15/7 \approx 2.14$, not an integer)
- $1 \mid n$ for every integer $n$ because $n = 1 \times n$
Key Properties of Divisibility
| Property | Statement | Meaning |
|---|---|---|
| Reflexive | $a \mid a$ (for $a \neq 0$) | Every nonzero integer divides itself |
| Transitive | If $a \mid b$ and $b \mid c$, then $a \mid c$ | Divisibility "chains" |
| Antisymmetric | If $a \mid b$ and $b \mid a$, then $a = \pm b$ | Mutual divisibility forces equality (up to sign) |
| Linear combination | If $a \mid b$ and $a \mid c$, then $a \mid (bx + cy)$ for all $x, y \in \mathbb{Z}$ | Divisibility is preserved by linear combinations |
Why This Matters in CS
Divisibility is the foundation for:
- Modular arithmetic (Module 2): checking $a \mid b$ is equivalent to checking $b \mod a = 0$
- Hashing: hash functions use modular reduction, which relies on divisibility
- Cryptography: RSA encryption depends on the difficulty of finding divisors of large numbers
- Loop bounds: if a loop runs $n$ times and processes items in groups of $k$, divisibility determines whether all items are processed evenly
Formal Notation
The Divisibility Symbol
$a \mid b$ (read "a divides b") means $\exists k \in \mathbb{Z}$ such that $b = ak$.
Careful! The vertical bar in $a \mid b$ is a relation symbol — it is either true or false. Do not confuse it with:
- $a / b$ (division, which returns a fraction or quotient)
- $a \mid b$ in set-builder notation $\{x \mid P(x)\}$ (which means "such that")
Writing Divisibility Proofs
To prove $a \mid b$: find an explicit integer $k$ such that $b = ak$ and verify that $k \in \mathbb{Z}$.
To prove $a \nmid b$: show that $b/a$ is not an integer (often by the quotient-remainder theorem: $b = aq + r$ with $0 < r < a$).
Common Pitfalls
| Pitfall | Why It's Wrong |
|---|---|
| Writing $a \mid b$ as "$a$ is divisible by $b$" | It's the other way around: $b$ is divisible by $a$ |
| Forgetting that $a \neq 0$ | Division by zero is undefined |
| Assuming $a \mid b$ means $a \leq b$ | False: $3 \mid (-6)$ even though $3 > -6$ |
| Confusing $a \mid b$ with $a / b$ | $a \mid b$ is a true/false relationship; $a/b$ is an arithmetic operation |
Worked Examples
Example 1: Prove Transitivity of Divisibility (Discrete Math)
Claim. If $a \mid b$ and $b \mid c$, then $a \mid c$.
Proof.
Step 1 — Hypotheses. We are given $a \mid b$ and $b \mid c$.
Step 2 — Unpack definitions.
- Since $a \mid b$, there exists an integer $m$ such that $b = am$.
- Since $b \mid c$, there exists an integer $n$ such that $c = bn$.
Step 3 — Algebra. Substitute the first equation into the second:
Step 4 — Identify the witness. Let $k = mn$. Since $m, n \in \mathbb{Z}$, we have $k = mn \in \mathbb{Z}$ (integers are closed under multiplication).
Step 5 — Conclusion. Since $c = ak$ with $k \in \mathbb{Z}$, we have $a \mid c$ by definition. $\blacksquare$
Concrete illustration: $4 \mid 12$ (because $12 = 4 \times 3$) and $12 \mid 60$ (because $60 = 12 \times 5$). By transitivity, $4 \mid 60$ (because $60 = 4 \times 15$, and indeed $15 = 3 \times 5 = mn$).
Example 2: Divisibility in Java (Java Translation)
/**
* DivisibilityDemo.java
* Implements and tests divisibility relations.
*/
public class DivisibilityDemo {
/**
* Returns true if a divides b.
*
* Math: a | b ↔ ∃k ∈ Z such that b = a·k
* Code: b % a == 0 checks whether the remainder is zero.
*
* Precondition: a != 0 (division by zero is undefined)
*
* Connection: b % a computes the remainder r where b = a·q + r.
* If r == 0, then b = a·q, so the witness is k = q = b/a.
*/
public static boolean divides(int a, int b) {
if (a == 0) throw new ArithmeticException("a cannot be zero in a|b");
return b % a == 0;
}
/**
* If a | b, returns the witness k such that b = a * k.
*/
public static int witness(int a, int b) {
assert divides(a, b) : a + " does not divide " + b;
return b / a;
}
/**
* Tests transitivity: if a|b and b|c, then a|c.
* Also displays the chain of witnesses.
*/
public static void demonstrateTransitivity(int a, int b, int c) {
System.out.printf("Testing transitivity: %d | %d and %d | %d ?%n", a, b, b, c);
if (divides(a, b) && divides(b, c)) {
int m = witness(a, b); // b = a * m
int n = witness(b, c); // c = b * n
int k = m * n; // c = a * (m * n)
System.out.printf(" b = %d * %d = %d (m = %d)%n", a, m, b, m);
System.out.printf(" c = %d * %d = %d (n = %d)%n", b, n, c, n);
System.out.printf(" c = %d * %d = %d (k = m*n = %d)%n", a, k, a * k, k);
System.out.printf(" Therefore %d | %d ✓%n", a, c);
} else {
System.out.println(" Hypotheses not satisfied.");
}
System.out.println();
}
public static void main(String[] args) {
System.out.println("=== DIVISIBILITY RELATIONS ===\n");
// Basic examples
System.out.println("--- Basic Divisibility Tests ---");
int[][] tests = {{3, 12}, {5, 0}, {7, 15}, {1, 42}, {-3, 9}, {4, -8}};
for (int[] t : tests) {
int a = t[0], b = t[1];
System.out.printf(" %d | %d ? %s%n", a, b, divides(a, b));
}
System.out.println();
// Transitivity demonstrations
System.out.println("--- Transitivity Demonstrations ---");
demonstrateTransitivity(4, 12, 60);
demonstrateTransitivity(3, 6, 18);
demonstrateTransitivity(2, 10, 50);
}
}Sample Output:
=== DIVISIBILITY RELATIONS ===
--- Basic Divisibility Tests ---
3 | 12 ? true
5 | 0 ? true
7 | 15 ? false
1 | 42 ? true
-3 | 9 ? true
4 | -8 ? true
--- Transitivity Demonstrations ---
Testing transitivity: 4 | 12 and 12 | 60 ?
b = 4 * 3 = 12 (m = 3)
c = 12 * 5 = 60 (n = 5)
c = 4 * 15 = 60 (k = m*n = 15)
Therefore 4 | 60 ✓
Testing transitivity: 3 | 6 and 6 | 18 ?
b = 3 * 2 = 6 (m = 2)
c = 6 * 3 = 18 (n = 3)
c = 3 * 6 = 18 (k = m*n = 6)
Therefore 3 | 18 ✓
Testing transitivity: 2 | 10 and 10 | 50 ?
b = 2 * 5 = 10 (m = 5)
c = 10 * 5 = 50 (n = 5)
c = 2 * 25 = 50 (k = m*n = 25)
Therefore 2 | 50 ✓Example 3: Linear Combinations Theorem (Combined DM + Java)
Claim. If $a \mid b$ and $a \mid c$, then for any integers $x$ and $y$, $a \mid (bx + cy)$.
Proof.
Since $a \mid b$, we have $b = am$ for some $m \in \mathbb{Z}$.
Since $a \mid c$, we have $c = an$ for some $n \in \mathbb{Z}$.
Then:
Let $k = mx + ny$. Since $m, x, n, y \in \mathbb{Z}$, we have $k \in \mathbb{Z}$. Therefore $a \mid (bx + cy)$. $\blacksquare$
Why this is powerful: This theorem says that if $a$ divides two numbers, then $a$ divides any combination of those numbers. For example, since $5 \mid 15$ and $5 \mid 20$, we know $5 \mid (15 \cdot 7 + 20 \cdot (-3)) = 105 - 60 = 45$.
Java Implementation:
/**
* Verifies the linear combination theorem:
* if a | b and a | c, then a | (bx + cy) for all x, y.
*/
public static void verifyLinearCombination(int a, int b, int c) {
if (!divides(a, b) || !divides(a, c)) {
System.out.printf(" Skipping: %d does not divide both %d and %d%n", a, b, c);
return;
}
System.out.printf("Since %d | %d and %d | %d, testing linear combinations:%n", a, b, a, c);
boolean allPass = true;
for (int x = -10; x <= 10; x++) {
for (int y = -10; y <= 10; y++) {
int lc = b * x + c * y;
if (!divides(a, lc)) {
System.out.printf(" FAIL: %d*%d + %d*%d = %d not divisible by %d%n",
b, x, c, y, lc, a);
allPass = false;
}
}
}
if (allPass) {
System.out.printf(" All linear combinations %d*x + %d*y divisible by %d (x,y in [-10,10])%n",
b, c, a);
}
}Example 4: Non-Divisibility Proof
Claim. $3 \nmid 20$.
Proof. By the quotient-remainder theorem, $20 = 3 \times 6 + 2$, so the remainder when dividing 20 by 3 is $r = 2 \neq 0$. Since no integer $k$ satisfies $20 = 3k$ (we would need $k = 20/3 \approx 6.67$), we have $3 \nmid 20$. $\blacksquare$
In Java: 20 % 3 == 2, which is nonzero, so divides(3, 20) returns false.
Example 5: Divisibility and Absolute Value
Claim. If $a \mid b$, then $|a| \mid |b|$.
Proof. Since $a \mid b$, we have $b = ak$ for some $k \in \mathbb{Z}$. Taking absolute values:
Since $|k| \in \mathbb{Z}$ (absolute value of an integer is a non-negative integer), we have $|a| \mid |b|$. $\blacksquare$
Proof Techniques Spotlight
Direct Proof with Divisibility
Divisibility proofs follow the same "direct proof from definitions" pattern as parity proofs from Class 1:
Template for Proving $a \mid (\text{expression})$:
Claim: If [hypotheses involving divisibility], then $a \mid [\text{some expression}]$.
>
Proof.
1. From each hypothesis "$d \mid x$," write $x = dk$ for a fresh variable $k \in \mathbb{Z}$.
2. Substitute these equations into the target expression.
3. Factor out $a$.
4. Identify the integer witness.
5. Conclude $a$ divides the expression. $\blacksquare$
Chaining Divisibility
Many divisibility proofs involve chains of substitutions. The key algebraic moves are:
- Substitution: Replace $b$ with $am$ (from $a \mid b$)
- Factoring: Rewrite $am \cdot n$ as $a(mn)$
- Closure: Note that products and sums of integers are integers
Common Mistakes
| Mistake | Correction |
|---|---|
| "Since $a \mid b$, we have $a = bk$" | Wrong direction! It should be $b = ak$ |
| Forgetting to introduce different variables for different hypotheses | If $a \mid b$ and $a \mid c$, write $b = am$ and $c = an$ with different $m, n$ |
| Not verifying the witness is an integer | Always confirm "$k \in \mathbb{Z}$ because integers are closed under [operation]" |
Java Deep Dive
Complete Divisibility Library
/**
* DivisibilityLibrary.java
* Complete library for divisibility operations and verification.
*/
public class DivisibilityLibrary {
/**
* Tests a | b.
* Math: a | b ↔ ∃k∈Z: b = ak ↔ b mod a = 0
*/
public static boolean divides(int a, int b) {
if (a == 0) throw new ArithmeticException("Cannot test divisibility by 0");
return b % a == 0;
}
/**
* Returns all positive divisors of n.
* A divisor d of n satisfies d | n and 1 ≤ d ≤ |n|.
*/
public static java.util.List<Integer> getDivisors(int n) {
java.util.List<Integer> divisors = new java.util.ArrayList<>();
if (n == 0) return divisors; // 0 has infinitely many divisors
int absN = Math.abs(n);
for (int d = 1; d <= absN; d++) {
if (absN % d == 0) {
divisors.add(d);
}
}
return divisors;
}
/**
* Counts the number of positive divisors of n.
* Notation: τ(n) or d(n) in number theory.
*/
public static int countDivisors(int n) {
return getDivisors(n).size();
}
/**
* Tests whether the divisibility relation is transitive
* for three specific values.
*/
public static boolean testTransitivity(int a, int b, int c) {
// If a|b and b|c, then a|c must hold
if (divides(a, b) && divides(b, c)) {
return divides(a, c);
}
return true; // vacuously true if hypothesis not met
}
/**
* Tests the linear combination property:
* if a|b and a|c, then a|(bx+cy) for given x, y.
*/
public static boolean testLinearCombination(int a, int b, int c, int x, int y) {
if (!divides(a, b) || !divides(a, c)) return true;
return divides(a, b * x + c * y);
}
/**
* Finds the common divisors of two integers.
* Common divisors of a and b are all d > 0 such that d|a and d|b.
*/
public static java.util.List<Integer> commonDivisors(int a, int b) {
java.util.List<Integer> result = new java.util.ArrayList<>();
java.util.List<Integer> divA = getDivisors(a);
for (int d : divA) {
if (divides(d, b)) {
result.add(d);
}
}
return result;
}
// =========================================================
// DEMONSTRATIONS
// =========================================================
public static void main(String[] args) {
System.out.println("===================================");
System.out.println(" DIVISIBILITY RELATIONS — CLASS 2 ");
System.out.println("===================================\n");
// Demo 1: Basic divisibility
System.out.println("--- Divisibility Tests ---");
int[][] pairs = {{3, 12}, {4, 18}, {5, 0}, {7, 49}, {6, 15}, {1, 100}};
for (int[] p : pairs) {
System.out.printf(" %d | %d ? %s", p[0], p[1], divides(p[0], p[1]));
if (divides(p[0], p[1])) {
System.out.printf(" (witness k = %d)", p[1] / p[0]);
}
System.out.println();
}
System.out.println();
// Demo 2: Listing divisors
System.out.println("--- Divisors ---");
for (int n : new int[]{1, 12, 28, 30, 100}) {
System.out.printf(" Divisors of %d: %s (count = %d)%n",
n, getDivisors(n), countDivisors(n));
}
System.out.println();
// Demo 3: Common divisors
System.out.println("--- Common Divisors ---");
System.out.println(" Common divisors of 12 and 18: " + commonDivisors(12, 18));
System.out.println(" Common divisors of 24 and 36: " + commonDivisors(24, 36));
System.out.println();
// Demo 4: Transitivity verification
System.out.println("--- Transitivity Verification ---");
boolean allTransitive = true;
for (int a = 1; a <= 10; a++) {
for (int b = 1; b <= 50; b++) {
for (int c = 1; c <= 50; c++) {
if (!testTransitivity(a, b, c)) {
System.out.printf(" FAIL: %d, %d, %d%n", a, b, c);
allTransitive = false;
}
}
}
}
if (allTransitive) {
System.out.println(" Transitivity holds for all tested triples.");
}
System.out.println();
// Demo 5: Linear combination verification
System.out.println("--- Linear Combination Verification ---");
boolean allLC = true;
int a = 6, b = 18, c = 24;
for (int x = -20; x <= 20; x++) {
for (int y = -20; y <= 20; y++) {
if (!testLinearCombination(a, b, c, x, y)) {
System.out.printf(" FAIL: %d | (%d*%d + %d*%d)%n", a, b, x, c, y);
allLC = false;
}
}
}
if (allLC) {
System.out.printf(" %d divides all %d*x + %d*y (x,y in [-20,20]) ✓%n", a, b, c);
}
}
}Sample Output:
===================================
DIVISIBILITY RELATIONS — CLASS 2
===================================
--- Divisibility Tests ---
3 | 12 ? true (witness k = 4)
4 | 18 ? false
5 | 0 ? true (witness k = 0)
7 | 49 ? true (witness k = 7)
6 | 15 ? false
1 | 100 ? true (witness k = 100)
--- Divisors ---
Divisors of 1: [1] (count = 1)
Divisors of 12: [1, 2, 3, 4, 6, 12] (count = 6)
Divisors of 28: [1, 2, 4, 7, 14, 28] (count = 6)
Divisors of 30: [1, 2, 3, 5, 6, 10, 15, 30] (count = 8)
Divisors of 100: [1, 2, 4, 5, 10, 20, 25, 50, 100] (count = 9)
--- Common Divisors ---
Common divisors of 12 and 18: [1, 2, 3, 6]
Common divisors of 24 and 36: [1, 2, 3, 4, 6, 12]
--- Transitivity Verification ---
Transitivity holds for all tested triples.
--- Linear Combination Verification ---
6 divides all 18*x + 24*y (x,y in [-20,20]) ✓Computational Use: Divisibility in Computer Science
Modular Arithmetic
Checking b % a == 0 is the computational core of divisibility. This operation underlies nearly every area of CS that deals with number properties.
Cryptography
RSA encryption relies on the fact that given a large number $n = pq$ (product of two primes), it is computationally hard to find $p$ and $q$. The security of RSA is fundamentally about the difficulty of the divisibility problem for large numbers.
Data Alignment
Computer memory is organized in words (4 bytes, 8 bytes). For efficiency, data structures must be aligned — their starting address must be divisible by their alignment requirement. Checking alignment is a divisibility test.
Cyclic Structures
Circular buffers, round-robin scheduling, and cyclic linked lists all use the pattern index = (index + 1) % size. Understanding divisibility helps reason about when indices wrap around and whether every position is visited.
Historical Context
Euclid (c. 300 BC) in Book VII of the Elements defined divisibility and proved the transitivity of the "measures" relation (his term for divisibility). His proofs were geometric — he represented numbers as line segments and "measuring" meant fitting one segment into another.
The notation $a \mid b$ was introduced much later, in the 19th century. Before that, mathematicians wrote "a measures b" or "a is contained in b." The compact symbol emerged as algebra became more formal.
Gauss (1801) in Disquisitiones Arithmeticae elevated divisibility to a central role in number theory, introducing congruence notation $a \equiv b \pmod{m}$ as a shorthand for $m \mid (a - b)$.
Slide-Ready Problem Sets
Slide Set A: Conceptual Questions
A1. True or false: $5 \mid 0$. Justify using the definition.
A2. True or false: $0 \mid 5$. Explain why.
A3. If $a \mid b$, does this imply $a \leq b$? Give an example or counterexample.
A4. List all positive integers that divide 24.
Slide Set B: Proof Problems
B1. Prove: If $6 \mid n$, then $2 \mid n$ and $3 \mid n$.
B2. Prove: If $a \mid b$, then $a \mid (-b)$.
B3. Prove: If $a \mid b$ and $a \mid c$, then $a \mid (b + c)$.
B4. Prove or disprove: If $a \mid (b + c)$, then $a \mid b$ or $a \mid c$.
Slide Set C: Java Coding Problems
C1. Write a method boolean divides(int a, int b) that returns true when $a \mid b$. Handle the edge case $a = 0$.
C2. Write a method List<Integer> getDivisors(int n) that returns all positive divisors of $n$. What is the relationship between the number of divisors and whether $n$ is prime?
C3. Write a method that takes three integers $a, b, c$ and checks whether $a \mid b$ and $b \mid c$ implies $a \mid c$ for those values.
C4. Write a method boolean isPerfect(int n) that returns true if $n$ is a perfect number (equal to the sum of its proper divisors). Test: is 28 perfect?
Full Problem Set
Discrete Math Problems
DM1. Prove: If $a \mid b$ and $b \mid c$, then $a \mid c$. (Transitivity — prove from scratch if this is your first time.)
DM2. Prove: If $a \mid b$ and $a \mid c$, then $a \mid (b - c)$.
DM3. Prove: If $a \mid b$, then $a \mid (b \cdot n)$ for any integer $n$.
DM4. Prove: If $a \mid b$ and $c \mid d$, then $ac \mid bd$.
DM5. Prove or disprove: If $6 \mid ab$, then $6 \mid a$ or $6 \mid b$.
DM6. Prove: If $a \mid b$ and $b \neq 0$, then $|a| \leq |b|$.
DM7. Prove: For any integer $n$, the product $n(n+1)(n+2)$ is divisible by 6. (Hint: among any three consecutive integers, one is divisible by 2 and one by 3.)
Java Programming Problems
JP1. Implement a method boolean relativelyPrime(int a, int b) that returns true if $a$ and $b$ share no common positive divisor other than 1. Test with pairs like $(8, 15)$, $(12, 18)$, $(7, 11)$.
JP2. Write a method int sumOfDivisors(int n) that returns the sum of all positive divisors of $n$. Test with $n = 28$ (answer: 56) and $n = 12$ (answer: 28).
JP3. Write a method that finds all "abundant" numbers up to 100. (A number $n$ is abundant if the sum of its proper divisors exceeds $n$.) Example: 12 is abundant because $1+2+3+4+6 = 16 > 12$.
JP4. Write a method void printDivisibilityChain(int a, int b, int c) that, when $a \mid b$ and $b \mid c$, prints the witnesses $m, n, k$ showing $b = am$, $c = bn$, $c = ak$ with $k = mn$.
JP5. Write a method that, given an array of integers and a divisor $d$, returns a new array containing only the elements divisible by $d$. Mathematically, this computes $\{x \in \text{arr} : d \mid x\}$.
JP6. Implement a method int gcd_naive(int a, int b) that finds the greatest common divisor by checking all common divisors. (This is a brute-force approach; the Euclidean algorithm in Class 3 is much faster.)
Bridge Problems (Discrete Math + Java)
BR1. Prove and Verify. Prove that for any integer $n$, $n(n+1)(n+2)$ is divisible by 6. Then write a Java method that tests this for $n = -100$ to $100$.
BR2. Proof to Code. The proof of transitivity uses substitution: $c = bn = (am)n = a(mn)$. Write a method int transitivityWitness(int a, int b, int c) that computes and returns the combined witness $k = mn$, and asserts that $c == a * k$.
BR3. Code to Proof. Consider:
public static boolean mysteryDivCheck(int n) {
return (n * n * n - n) % 6 == 0;
}State the mathematical theorem this checks and prove it. (Hint: $n^3 - n = n(n-1)(n+1)$, which is a product of three consecutive integers.)
Solutions
Discrete Math Solutions
DM1 Solution. Let $a \mid b$ and $b \mid c$. Then $b = am$ and $c = bn$ for some $m, n \in \mathbb{Z}$. Substituting: $c = (am)n = a(mn)$. Since $mn \in \mathbb{Z}$, $a \mid c$. $\blacksquare$
DM2 Solution. Since $a \mid b$, we have $b = am$. Since $a \mid c$, we have $c = an$. Then $b - c = am - an = a(m - n)$. Since $m - n \in \mathbb{Z}$, $a \mid (b - c)$. $\blacksquare$
DM3 Solution. Since $a \mid b$, we have $b = ak$ for some $k \in \mathbb{Z}$. Then $bn = (ak)n = a(kn)$. Since $kn \in \mathbb{Z}$, $a \mid bn$. $\blacksquare$
DM4 Solution. Since $a \mid b$, we have $b = am$ for some $m \in \mathbb{Z}$. Since $c \mid d$, we have $d = cn$ for some $n \in \mathbb{Z}$. Then $bd = (am)(cn) = (ac)(mn)$. Since $mn \in \mathbb{Z}$, $ac \mid bd$. $\blacksquare$
DM5 Solution. Disproof. Let $a = 2$ and $b = 3$. Then $ab = 6$ and $6 \mid 6$, but $6 \nmid 2$ and $6 \nmid 3$. The claim is false. $\blacksquare$
Note: This would be true if 6 were prime (Euclid's lemma), but 6 is composite. The correct statement is: if $p$ is prime and $p \mid ab$, then $p \mid a$ or $p \mid b$.
DM6 Solution. Since $a \mid b$ and $b \neq 0$, we have $b = ak$ for some $k \in \mathbb{Z}$, $k \neq 0$ (since $b \neq 0$). Taking absolute values: $|b| = |a| \cdot |k|$. Since $|k| \geq 1$, we get $|b| \geq |a|$. $\blacksquare$
DM7 Solution. Among three consecutive integers $n, n+1, n+2$:
- At least one is even (divisible by 2).
- At least one is divisible by 3 (since the remainders mod 3 cycle through 0, 1, 2).
So $2 \mid n(n+1)(n+2)$ and $3 \mid n(n+1)(n+2)$. Since $\gcd(2, 3) = 1$, we get $6 \mid n(n+1)(n+2)$. $\blacksquare$
Java Solutions
JP1 Solution.
public static boolean relativelyPrime(int a, int b) {
// Two numbers are relatively prime if their only common positive divisor is 1
a = Math.abs(a); b = Math.abs(b);
for (int d = 2; d <= Math.min(a, b); d++) {
if (a % d == 0 && b % d == 0) {
return false; // found a common divisor > 1
}
}
return true;
}JP2 Solution.
public static int sumOfDivisors(int n) {
// σ(n) = sum of all positive divisors of n
int sum = 0;
for (int d = 1; d <= Math.abs(n); d++) {
if (n % d == 0) {
sum += d;
}
}
return sum;
}JP3 Solution.
public static void findAbundant(int limit) {
System.out.println("Abundant numbers up to " + limit + ":");
for (int n = 2; n <= limit; n++) {
int properSum = sumOfDivisors(n) - n; // subtract n itself
if (properSum > n) {
System.out.printf(" %d (proper divisor sum = %d)%n", n, properSum);
}
}
}
// Output includes: 12, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56, 60, ...JP4 Solution.
public static void printDivisibilityChain(int a, int b, int c) {
if (b % a != 0 || c % b != 0) {
System.out.println("Hypotheses not met: a|b and b|c required.");
return;
}
int m = b / a;
int n = c / b;
int k = m * n;
System.out.printf("%d = %d * %d (m = %d)%n", b, a, m, m);
System.out.printf("%d = %d * %d (n = %d)%n", c, b, n, n);
System.out.printf("%d = %d * %d (k = m*n = %d*%d = %d)%n", c, a, k, m, n, k);
}JP5 Solution.
public static int[] filterDivisible(int[] arr, int d) {
// Returns {x ∈ arr : d | x}
return java.util.Arrays.stream(arr)
.filter(x -> x % d == 0)
.toArray();
}
// Or without streams:
public static int[] filterDivisibleLoop(int[] arr, int d) {
int count = 0;
for (int x : arr) if (x % d == 0) count++;
int[] result = new int[count];
int idx = 0;
for (int x : arr) {
if (x % d == 0) result[idx++] = x;
}
return result;
}JP6 Solution.
public static int gcd_naive(int a, int b) {
a = Math.abs(a); b = Math.abs(b);
if (a == 0) return b;
if (b == 0) return a;
int gcd = 1;
for (int d = 1; d <= Math.min(a, b); d++) {
if (a % d == 0 && b % d == 0) {
gcd = d;
}
}
return gcd;
}
// This is O(min(a, b)) — the Euclidean algorithm in Class 3 is O(log(min(a,b)))Bridge Problem Solutions
BR1 Solution.
Proof: Among $n, n+1, n+2$, one is divisible by 2 and one by 3 (since they are consecutive, their remainders mod 2 cycle through 0-1, and mod 3 through 0-1-2). So the product is divisible by both 2 and 3, hence by 6. $\blacksquare$
public static void verifyConsecutiveTriple() {
for (int n = -100; n <= 100; n++) {
long product = (long) n * (n + 1) * (n + 2);
assert product % 6 == 0 : "Failed for n=" + n;
}
System.out.println("n(n+1)(n+2) is always divisible by 6: verified.");
}BR2 Solution.
public static int transitivityWitness(int a, int b, int c) {
assert b % a == 0 : a + " does not divide " + b;
assert c % b == 0 : b + " does not divide " + c;
int m = b / a; // b = a * m
int n = c / b; // c = b * n
int k = m * n; // c = a * k
assert c == a * k : "Witness verification failed";
return k;
}BR3 Solution.
The method checks: $6 \mid (n^3 - n)$ for all $n$.
Theorem: For any integer $n$, $n^3 - n$ is divisible by 6.
Proof: Factor: $n^3 - n = n(n^2 - 1) = n(n-1)(n+1) = (n-1) \cdot n \cdot (n+1)$. This is the product of three consecutive integers. Among any three consecutive integers, one is divisible by 2 and one by 3. Since $\gcd(2,3) = 1$, the product is divisible by $2 \times 3 = 6$. $\blacksquare$
Module 1 – Class 3: Primes and the Euclidean Algorithm
Learning Objectives
By the end of this class, students will be able to:
- Define prime and composite numbers formally and identify them.
- State and explain the Euclidean algorithm for computing the greatest common divisor (gcd).
- Prove the correctness of the Euclidean algorithm using a loop invariant.
- Argue that the algorithm terminates using a variant function (decreasing remainders).
- Implement
gcd,isPrime, and a prime sieve in Java, connecting each to the mathematical definitions.
Concept Overview
Prime Numbers
Definition (Prime). An integer $p > 1$ is prime if its only positive divisors are 1 and $p$ itself.
Definition (Composite). An integer $n > 1$ is composite if it is not prime — that is, there exist integers $a, b$ with $1 < a, b < n$ such that $n = ab$.
Special cases:
- 1 is neither prime nor composite (by convention).
- 2 is the only even prime.
- 0 and negative integers are neither prime nor composite.
Plain Language
A prime number cannot be broken into smaller factors (other than 1 and itself). A composite number can be factored. Primes are the "atoms" of arithmetic — every integer greater than 1 is either prime or can be built by multiplying primes together.
The First Few Primes
Greatest Common Divisor
Definition (GCD). The greatest common divisor of integers $a$ and $b$ (not both zero), written $\gcd(a, b)$, is the largest positive integer that divides both $a$ and $b$.
Examples:
- $\gcd(12, 18) = 6$ because the common divisors of 12 and 18 are $\{1, 2, 3, 6\}$
- $\gcd(7, 11) = 1$ (they share no common factor except 1 — they are "coprime")
- $\gcd(0, n) = |n|$ for any nonzero $n$
The Euclidean Algorithm
The Euclidean algorithm computes $\gcd(a, b)$ efficiently using the key identity:
The algorithm repeatedly applies this identity until the remainder is 0. At that point, the other value is the gcd.
Why does this work? If $a = bq + r$, then any common divisor of $a$ and $b$ also divides $r$ (since $r = a - bq$), and any common divisor of $b$ and $r$ also divides $a$ (since $a = bq + r$). So $a$ and $b$ have exactly the same set of common divisors as $b$ and $r$.
Formal Notation
The Division Algorithm Identity
For any integers $a$ and $b$ with $b > 0$:
GCD Properties
| Property | Statement |
|---|---|
| Commutativity | $\gcd(a, b) = \gcd(b, a)$ |
| GCD with 0 | $\gcd(a, 0) = \|a\|$ |
| Key identity | $\gcd(a, b) = \gcd(b, a \bmod b)$ |
| Coprime | $\gcd(a, b) = 1$ means $a$ and $b$ share no factor $> 1$ |
Algorithm in Pseudocode
GCD(a, b):
while b ≠ 0:
r ← a mod b
a ← b
b ← r
return aCommon Pitfalls
| Pitfall | Correction |
|---|---|
| Forgetting that $\gcd(a, 0) = a$, not 0 | Zero is divisible by everything, so the gcd is the other number |
| Testing primality by checking only a few small primes | You must check all potential factors up to $\sqrt{n}$ |
| Confusing gcd with lcm | $\gcd$ is the greatest common divisor; $\text{lcm}$ is the least common multiple |
Worked Examples
Example 1: Computing gcd(1071, 462) by Hand (Discrete Math)
Apply the Euclidean algorithm step by step:
| Step | Division | Quotient $q$ | Remainder $r$ |
|---|---|---|---|
| 1 | $1071 = 462 \cdot 2 + 147$ | 2 | 147 |
| 2 | $462 = 147 \cdot 3 + 21$ | 3 | 21 |
| 3 | $147 = 21 \cdot 7 + 0$ | 7 | 0 |
When the remainder reaches 0, the other value (21) is the gcd.
Verification: $1071 = 21 \times 51$ and $462 = 21 \times 22$. Both are divisible by 21, and 51 and 22 share no common factor ($\gcd(51, 22) = 1$), confirming 21 is the greatest common divisor.
Example 2: The Euclidean Algorithm in Java (Java Translation)
/**
* EuclideanGCD.java
* Implements the Euclidean algorithm with detailed tracing.
*/
public class EuclideanGCD {
/**
* Computes gcd(a, b) using the Euclidean algorithm.
*
* LOOP INVARIANT: gcd(a, b) = gcd(original_a, original_b)
* at the start of each iteration.
*
* VARIANT FUNCTION: b decreases each iteration (b > 0 before, and
* the new b = old_a % old_b which is in [0, old_b - 1]).
*
* TERMINATION: b is a non-negative integer that strictly decreases
* each iteration, so the loop must terminate when b == 0.
*
* POSTCONDITION: when b == 0, gcd(a, 0) = a.
*
* Math: gcd(a, b) = gcd(b, a mod b)
* Code: each iteration replaces (a, b) with (b, a % b)
*/
public static int gcd(int a, int b) {
a = Math.abs(a);
b = Math.abs(b);
while (b != 0) {
int r = a % b; // r = a mod b; the key step
a = b; // replace a with b
b = r; // replace b with r
}
return a; // when b == 0, a is the gcd
}
// try this
public static int gcd(int a, int b) {
a = Math.abs(a);
b = Math.abs(b);
// Base Case: "If b is zero, return the other one"
if (b == 0) {
return a;
}
// Recursive Step: Explicitly sending the output to the next 'a' and 'b'
return gcd(b, a % b);
}
/**
* Same algorithm with step-by-step tracing for teaching.
*/
public static int gcdWithTrace(int a, int b) {
a = Math.abs(a);
b = Math.abs(b);
System.out.printf("Computing gcd(%d, %d):%n", a, b);
int step = 1;
while (b != 0) {
int q = a / b;
int r = a % b;
System.out.printf(" Step %d: %d = %d × %d + %d%n", step, a, b, q, r);
a = b;
b = r;
step++;
}
System.out.printf(" Result: gcd = %d%n%n", a);
return a;
}
public static void main(String[] args) {
System.out.println("===========================================");
System.out.println(" PRIMES AND THE EUCLIDEAN ALGORITHM — CLASS 3");
System.out.println("===========================================\n");
// Traced examples
gcdWithTrace(1071, 462);
gcdWithTrace(48, 18);
gcdWithTrace(100, 35);
gcdWithTrace(17, 13); // coprime
gcdWithTrace(0, 15);
// Verify commutativity
System.out.println("--- Commutativity Check ---");
for (int a = 0; a <= 50; a++) {
for (int b = 0; b <= 50; b++) {
if (a == 0 && b == 0) continue;
assert gcd(a, b) == gcd(b, a) : "Commutativity failed!";
}
}
System.out.println(" gcd(a,b) = gcd(b,a) verified for a,b in [0,50]\n");
// Verify: gcd(a,b) divides both a and b
System.out.println("--- GCD Divides Both ---");
boolean allPass = true;
for (int a = 1; a <= 100; a++) {
for (int b = 1; b <= 100; b++) {
int g = gcd(a, b);
if (a % g != 0 || b % g != 0) {
System.out.printf(" FAIL: gcd(%d,%d)=%d%n", a, b, g);
allPass = false;
}
}
}
if (allPass) {
System.out.println(" gcd(a,b) divides both a and b: verified.\n");
}
}
}Sample Output:
===========================================
PRIMES AND THE EUCLIDEAN ALGORITHM — CLASS 3
===========================================
Computing gcd(1071, 462):
Step 1: 1071 = 462 × 2 + 147
Step 2: 462 = 147 × 3 + 21
Step 3: 147 = 21 × 7 + 0
Result: gcd = 21
Computing gcd(48, 18):
Step 1: 48 = 18 × 2 + 12
Step 2: 18 = 12 × 1 + 6
Step 3: 12 = 6 × 2 + 0
Result: gcd = 6
Computing gcd(100, 35):
Step 1: 100 = 35 × 2 + 30
Step 2: 35 = 30 × 1 + 5
Step 3: 30 = 5 × 6 + 0
Result: gcd = 5
Computing gcd(17, 13):
Step 1: 17 = 13 × 1 + 4
Step 2: 13 = 4 × 3 + 1
Step 3: 4 = 1 × 4 + 0
Result: gcd = 1
Computing gcd(15, 0):
Result: gcd = 15Example 3: Proving the Euclidean Algorithm Is Correct (Combined DM + Java)
We prove three things: (1) the loop invariant holds, (2) the algorithm terminates, and (3) the postcondition gives the right answer.
Loop Invariant: At the start of each iteration, $\gcd(a, b) = \gcd(a_0, b_0)$ where $a_0, b_0$ are the original inputs.
Proof of the invariant:
Initialization: Before the first iteration, $a = a_0$ and $b = b_0$, so $\gcd(a, b) = \gcd(a_0, b_0)$. ✓
Maintenance: Suppose $\gcd(a, b) = \gcd(a_0, b_0)$ at the start of an iteration. The algorithm computes $r = a \bmod b$ and replaces $(a, b)$ with $(b, r)$.
We must show $\gcd(b, r) = \gcd(a, b)$. Since $a = bq + r$ for some integer $q$:
- Any common divisor of $a$ and $b$ also divides $r = a - bq$ (by the linear combination theorem from Class 2).
- Any common divisor of $b$ and $r$ also divides $a = bq + r$.
So the set of common divisors is the same, and hence the greatest common divisor is the same. ✓
Termination: The loop ends when $b = 0$. At that point, $\gcd(a, 0) = a$. By the invariant, $a = \gcd(a_0, b_0)$. ✓
Termination Proof via Variant Function:
Define the variant $V = b$. At each step:
- $b_{\text{new}} = a \bmod b$, and $0 \leq a \bmod b < b$ by the quotient-remainder theorem.
- So $b_{\text{new}} < b_{\text{old}}$ (strictly decreasing).
- Since $b \geq 0$ always, and a non-negative integer cannot decrease forever, the loop terminates. $\blacksquare$
Java annotation showing invariant and variant:
public static int gcdAnnotated(int a, int b) {
a = Math.abs(a);
b = Math.abs(b);
// INVARIANT: gcd(a, b) = gcd(original a, original b)
// VARIANT: b ≥ 0 and strictly decreases each iteration
while (b != 0) {
assert b > 0; // variant is positive
int oldB = b;
int r = a % b;
a = b;
b = r;
assert b < oldB; // variant strictly decreases
// gcd(a, b) = gcd(old a, old b) by the key identity
}
// b == 0, so gcd(a, 0) = a
return a;
}Example 4: Primality Testing (Discrete Math)
Claim. To test whether $n > 1$ is prime, it suffices to check for divisors up to $\sqrt{n}$.
Proof. Suppose $n$ is composite, so $n = ab$ with $1 < a, b < n$. We cannot have both $a > \sqrt{n}$ and $b > \sqrt{n}$, because then $ab > n$, contradicting $ab = n$. So at least one factor satisfies $a \leq \sqrt{n}$. Therefore, if no integer from 2 to $\lfloor\sqrt{n}\rfloor$ divides $n$, then $n$ is prime. $\blacksquare$
Example: To test if 97 is prime, check divisors up to $\lfloor\sqrt{97}\rfloor = 9$. Check: $97/2, 97/3, 97/5, 97/7$ — none divide evenly. So 97 is prime.
Example 5: Sieve of Eratosthenes
The Sieve of Eratosthenes finds all primes up to $N$:
- List all integers from 2 to $N$.
- The first uncrossed number is prime. Cross out all its multiples.
- Repeat until you've processed numbers up to $\sqrt{N}$.
For $N = 30$:
Start: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Cross out multiples of 2: ~~4~~ ~~6~~ ~~8~~ ~~10~~ ~~12~~ ~~14~~ ~~16~~ ~~18~~ ~~20~~ ~~22~~ ~~24~~ ~~26~~ ~~28~~ ~~30~~
Cross out multiples of 3: ~~9~~ ~~15~~ ~~21~~ ~~27~~
Cross out multiples of 5: ~~25~~
Done ($5 < \sqrt{30} < 6$). Primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
Proof Techniques Spotlight
Loop Invariants
A loop invariant is a condition that is:
- True before the loop starts (initialization).
- Preserved by each iteration (maintenance).
- Useful when the loop ends (postcondition).
This is the proof technique that most directly connects mathematics to programming. It mirrors mathematical induction:
| Induction | Loop Invariant |
|---|---|
| Base case $P(1)$ | Initialization: invariant holds before first iteration |
| Inductive step: $P(k) \Rightarrow P(k+1)$ | Maintenance: if invariant holds before iteration, it holds after |
| Conclusion for all $n$ | Postcondition: when loop exits, invariant + exit condition gives result |
Variant Functions (Termination)
A variant function (or decrementing function) is a function $V$ of the loop variables that:
- Is always $\geq 0$.
- Strictly decreases each iteration.
Since a non-negative integer cannot decrease forever, the loop must terminate.
Common Mistakes
| Mistake | Correction |
|---|---|
| Claiming the invariant is the entire postcondition | The invariant is something that holds during the loop; the postcondition combines the invariant with the loop exit condition |
| Forgetting to prove initialization | The invariant must hold before the first iteration |
| Not identifying the variant function | Without a variant, you haven't proved termination |
Java Deep Dive
Complete Primes and GCD Library
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* PrimesAndGCD.java
* Complete library for primality testing, the Euclidean algorithm,
* and related computations.
*/
public class PrimesAndGCD {
// =========================================================
// GCD
// =========================================================
/**
* Euclidean algorithm: computes gcd(a, b).
* Invariant: gcd(a,b) is preserved each iteration.
* Variant: b strictly decreases toward 0.
*/
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;
}
/**
* Recursive version of the Euclidean algorithm.
* Mirrors the mathematical identity: gcd(a, b) = gcd(b, a mod b).
* Base case: gcd(a, 0) = a.
*/
public static int gcdRecursive(int a, int b) {
a = Math.abs(a);
b = Math.abs(b);
if (b == 0) return a;
return gcdRecursive(b, a % b);
}
/**
* Least common multiple using the identity: lcm(a,b) = |a*b| / gcd(a,b).
*/
public static int lcm(int a, int b) {
if (a == 0 || b == 0) return 0;
return Math.abs(a / gcd(a, b) * b); // divide first to avoid overflow
}
/**
* Extended Euclidean algorithm: returns {g, x, y} where
* g = gcd(a, b) and a*x + b*y = g (Bézout's identity).
*/
public static int[] extendedGcd(int a, int b) {
if (b == 0) return new int[]{a, 1, 0};
int[] result = extendedGcd(b, a % b);
int g = result[0];
int x = result[2];
int y = result[1] - (a / b) * result[2];
return new int[]{g, x, y};
}
// =========================================================
// PRIMALITY
// =========================================================
/**
* Tests whether n is prime.
*
* Math: n is prime iff n > 1 and the only positive divisors of n
* are 1 and n.
* Optimization: only check divisors up to sqrt(n), because if
* n = a*b with a <= b, then a <= sqrt(n).
*
* Time: O(sqrt(n))
*/
public static boolean isPrime(int n) {
if (n < 2) return false;
if (n < 4) return true; // 2, 3 are prime
if (n % 2 == 0 || n % 3 == 0) return false;
// Only need to check divisors of the form 6k ± 1
for (int i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
return true;
}
/**
* Simple primality test (for clarity, not efficiency).
* Checks all potential divisors from 2 to sqrt(n).
*/
public static boolean isPrimeSimple(int n) {
if (n < 2) return false;
for (int d = 2; d * d <= n; d++) {
if (n % d == 0) return false; // found a divisor: not prime
}
return true; // no divisors found: prime
}
/**
* Sieve of Eratosthenes: returns all primes up to limit.
*
* Math: cross out multiples of each prime starting from 2.
* After processing primes up to sqrt(limit), all remaining
* uncrossed numbers are prime.
*
* Time: O(n log log n)
*/
public static List<Integer> sieve(int limit) {
boolean[] isComposite = new boolean[limit + 1];
List<Integer> primes = new ArrayList<>();
for (int p = 2; p <= limit; p++) {
if (!isComposite[p]) {
primes.add(p);
// Cross out multiples of p starting from p*p
// (smaller multiples already crossed out)
for (long multiple = (long) p * p; multiple <= limit; multiple += p) {
isComposite[(int) multiple] = true;
}
}
}
return primes;
}
/**
* Returns the prime factorization of n as a list of factors.
* E.g., primeFactors(84) returns [2, 2, 3, 7] since 84 = 2² × 3 × 7.
*/
public static List<Integer> primeFactors(int n) {
List<Integer> factors = new ArrayList<>();
if (n < 2) return factors;
// Divide out 2s
while (n % 2 == 0) {
factors.add(2);
n /= 2;
}
// Check odd factors from 3 to sqrt(n)
for (int d = 3; d * d <= n; d += 2) {
while (n % d == 0) {
factors.add(d);
n /= d;
}
}
// If n > 1, then n is a prime factor
if (n > 1) {
factors.add(n);
}
return factors;
}
// =========================================================
// DEMONSTRATIONS
// =========================================================
public static void main(String[] args) {
System.out.println("================================================");
System.out.println(" PRIMES AND THE EUCLIDEAN ALGORITHM — CLASS 3 ");
System.out.println("================================================\n");
// Demo 1: Prime checking
System.out.println("--- Primality Tests ---");
int[] testNums = {1, 2, 3, 4, 11, 15, 17, 25, 29, 97, 100};
for (int n : testNums) {
System.out.printf(" isPrime(%d) = %s%n", n, isPrime(n));
}
System.out.println();
// Demo 2: Sieve of Eratosthenes
System.out.println("--- Primes up to 100 (Sieve) ---");
List<Integer> primes = sieve(100);
System.out.println(" " + primes);
System.out.println(" Count: " + primes.size());
System.out.println();
// Demo 3: Prime factorization
System.out.println("--- Prime Factorization ---");
int[] toFactor = {12, 28, 84, 100, 97, 360};
for (int n : toFactor) {
System.out.printf(" %d = %s%n", n, primeFactors(n));
}
System.out.println();
// Demo 4: GCD examples
System.out.println("--- GCD Computations ---");
int[][] gcdTests = {{1071, 462}, {48, 18}, {100, 35}, {17, 13}, {0, 15}};
for (int[] pair : gcdTests) {
System.out.printf(" gcd(%d, %d) = %d%n", pair[0], pair[1], gcd(pair[0], pair[1]));
}
System.out.println();
// Demo 5: Extended Euclidean algorithm (Bézout's identity)
System.out.println("--- Extended GCD (Bézout's Identity) ---");
for (int[] pair : gcdTests) {
if (pair[0] == 0 || pair[1] == 0) continue;
int[] result = extendedGcd(pair[0], pair[1]);
System.out.printf(" gcd(%d, %d) = %d = %d×(%d) + %d×(%d)%n",
pair[0], pair[1], result[0], pair[0], result[1], pair[1], result[2]);
// Verify
assert pair[0] * result[1] + pair[1] * result[2] == result[0];
}
System.out.println();
// Demo 6: Verify iterative = recursive
System.out.println("--- Iterative vs Recursive GCD ---");
boolean match = true;
for (int a = 0; a <= 100; a++) {
for (int b = 0; b <= 100; b++) {
if (a == 0 && b == 0) continue;
if (gcd(a, b) != gcdRecursive(a, b)) {
match = false;
System.out.printf(" MISMATCH: gcd(%d,%d)%n", a, b);
}
}
}
if (match) {
System.out.println(" Iterative and recursive agree for a,b in [0,100].");
}
System.out.println();
// Demo 7: LCM
System.out.println("--- LCM Computations ---");
int[][] lcmTests = {{12, 18}, {4, 6}, {7, 13}, {100, 35}};
for (int[] pair : lcmTests) {
System.out.printf(" lcm(%d, %d) = %d%n", pair[0], pair[1], lcm(pair[0], pair[1]));
}
}
}Sample Output:
--- Primality Tests ---
isPrime(1) = false
isPrime(2) = true
isPrime(3) = true
isPrime(4) = false
isPrime(11) = true
isPrime(15) = false
isPrime(17) = true
isPrime(25) = false
isPrime(29) = true
isPrime(97) = true
isPrime(100) = false
--- Primes up to 100 (Sieve) ---
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
Count: 25
--- Prime Factorization ---
12 = [2, 2, 3]
28 = [2, 2, 7]
84 = [2, 2, 3, 7]
100 = [2, 2, 5, 5]
97 = [97]
360 = [2, 2, 2, 3, 3, 5]
--- GCD Computations ---
gcd(1071, 462) = 21
gcd(48, 18) = 6
gcd(100, 35) = 5
gcd(17, 13) = 1
gcd(0, 15) = 15
--- Extended GCD (Bézout's Identity) ---
gcd(1071, 462) = 21 = 1071×(-9) + 462×(21)
gcd(48, 18) = 6 = 48×(-1) + 18×(3)
gcd(100, 35) = 5 = 100×(-1) + 35×(3)
gcd(17, 13) = 1 = 17×(-3) + 13×(4)Computational Use: Primes and GCD in Computer Science
Cryptography (RSA)
RSA encryption relies on:
- Generating two large primes $p$ and $q$.
- Computing $n = pq$ (easy).
- The security assumption: factoring $n$ back into $p$ and $q$ is computationally hard.
The gcd and extended Euclidean algorithm are used to compute modular inverses needed for the keys.
Hash Functions
Many hash functions use modular arithmetic with a prime table size. Using a prime $m$ distributes keys more uniformly because primes have no common factors with typical data patterns.
Rational Arithmetic
To reduce a fraction $a/b$ to lowest terms, divide both by $\gcd(a, b)$.
Performance Analysis
The Euclidean algorithm runs in $O(\log(\min(a, b)))$ time — remarkably efficient. The number of steps is at most about $5 \times (\text{number of digits of } \min(a, b))$.
Historical Context
Euclid (c. 300 BC) described the algorithm in Propositions 1 and 2 of Book VII of the Elements. It is one of the oldest algorithms still in widespread use — over 2300 years old. Euclid described it geometrically: given two line segments, repeatedly subtract the shorter from the longer until the segments are equal.
Fibonacci (1202) popularized the algorithm in Europe through his Liber Abaci. The worst case of the Euclidean algorithm occurs for consecutive Fibonacci numbers — this is because Fibonacci numbers grow as slowly as possible relative to their gcd.
Lamé (1844) proved that the number of steps in the Euclidean algorithm for $\gcd(a, b)$ with $a > b$ is at most $5 \times (\text{number of digits of } b)$.
Slide-Ready Problem Sets
Slide Set A: Conceptual Questions
A1. Is 1 a prime number? Why or why not?
A2. Why is 2 the only even prime?
A3. What is $\gcd(15, 0)$? What is $\gcd(0, 0)$? (Trick question — $\gcd(0,0)$ is conventionally undefined or taken as 0.)
A4. If $\gcd(a, b) = 1$, what does that tell you about $a$ and $b$?
Slide Set B: Proof Problems
B1. Prove: There are infinitely many prime numbers. (Hint: Euclid's proof. Assume finitely many primes $p_1, \ldots, p_n$. Consider $N = p_1 p_2 \cdots p_n + 1$.)
B2. Prove that $\gcd(a, b) = \gcd(b, a \bmod b)$ by showing the two pairs have the same set of common divisors.
B3. Prove that the Euclidean algorithm terminates by identifying a variant function.
B4. If $\gcd(a, b) = d$, prove that $\gcd(a/d, b/d) = 1$.
Slide Set C: Java Coding Problems
C1. Implement int gcd(int a, int b) both iteratively and recursively. Verify they give the same answer for $a, b \in [0, 100]$.
C2. Implement boolean isPrime(int n) using the $\sqrt{n}$ optimization. Test it for $n = 1$ to $100$.
C3. Implement the Sieve of Eratosthenes to find all primes up to 1000. How many are there?
C4. Write a method that computes the prime factorization of any integer and returns it as a List<Integer>.
Full Problem Set
Discrete Math Problems
DM1. Compute $\gcd(252, 198)$ by hand using the Euclidean algorithm. Show each step.
DM2. Prove: If $p$ is prime and $p \mid ab$, then $p \mid a$ or $p \mid b$. (This is Euclid's Lemma. Hint: if $p \nmid a$, then $\gcd(p, a) = 1$, so by Bézout's identity, $1 = px + ay$. Multiply both sides by $b$.)
DM3. Prove: $\gcd(n, n+1) = 1$ for any positive integer $n$. (Hint: if $d \mid n$ and $d \mid (n+1)$, then $d \mid ((n+1) - n) = 1$.)
DM4. Prove: $\gcd(a, b) \cdot \text{lcm}(a, b) = |ab|$.
DM5. Find integers $x$ and $y$ such that $\gcd(1071, 462) = 1071x + 462y$. (Use the extended Euclidean algorithm by back-substituting.)
DM6. Prove: If $\gcd(a, b) = 1$ and $a \mid c$ and $b \mid c$, then $ab \mid c$.
DM7. Prove that every composite number $n$ has a prime factor $\leq \sqrt{n}$.
Java Programming Problems
JP1. Write int gcd(int a, int b) iteratively and int gcdRec(int a, int b) recursively. Assert they match for 10,000 random pairs.
JP2. Implement the Sieve of Eratosthenes for $N = 10{,}000$. Count the primes (should be 1229). Compute the ratio $\pi(N) / (N / \ln N)$ and compare to 1 (the prime number theorem).
JP3. Write a method int[] extendedGcd(int a, int b) that returns $\{g, x, y\}$ where $g = \gcd(a,b)$ and $ax + by = g$. Verify for 100 pairs.
JP4. Write List<Integer> primeFactorization(int n) using trial division. Verify that multiplying the factors recovers $n$ for all $n$ from 2 to 1000.
JP5. Write a method that determines whether two numbers are coprime (gcd = 1). Use it to count the number of integers from 1 to 100 that are coprime to 100. (This is Euler's totient function $\phi(100)$.)
JP6. Implement a method that finds all prime pairs $(p, p+2)$ ("twin primes") up to 1000. How many are there?
Bridge Problems (Discrete Math + Java)
BR1. Prove and Verify. Prove that $\gcd(n, n+1) = 1$ for all $n \geq 1$. Then write a Java method that verifies this for $n = 1$ to $10{,}000$.
BR2. Loop Invariant in Code. Annotate your iterative gcd method with assert statements that check:
- The loop invariant (gcd of current $a, b$ equals gcd of original inputs).
- The variant function (b decreases each iteration).
Run with assertions enabled (java -ea) and verify no assertions fail.
BR3. Back-Substitution. The Euclidean algorithm for $\gcd(48, 18)$ gives:
48 = 18 × 2 + 12
18 = 12 × 1 + 6
12 = 6 × 2 + 0Back-substitute to find $x, y$ such that $6 = 48x + 18y$. Then write Java code that performs this back-substitution automatically (i.e., implement the extended Euclidean algorithm).
Solutions
Discrete Math Solutions
DM1 Solution.
Therefore $\gcd(252, 198) = 18$.
DM2 Solution (Euclid's Lemma).
Suppose $p$ is prime, $p \mid ab$, and $p \nmid a$. Since $p$ is prime, its only divisors are 1 and $p$. Since $p \nmid a$, $\gcd(p, a) = 1$. By Bézout's identity, there exist $x, y$ such that $px + ay = 1$. Multiply by $b$: $pxb + aby = b$. Now $p \mid (pxb)$ (trivially) and $p \mid (aby)$ (since $p \mid ab$). So $p \mid (pxb + aby) = b$. $\blacksquare$
DM3 Solution.
Suppose $d \mid n$ and $d \mid (n+1)$. Then $d \mid ((n+1) - n) = 1$, so $d = \pm 1$. The largest positive common divisor is 1. $\blacksquare$
DM4 Solution.
Write $a = d \alpha$ and $b = d \beta$ where $d = \gcd(a, b)$ and $\gcd(\alpha, \beta) = 1$.
Then $\text{lcm}(a, b) = d \alpha \beta$ (one can verify this is the smallest common multiple).
So $\gcd(a,b) \cdot \text{lcm}(a,b) = d \cdot d\alpha\beta = d^2 \alpha \beta = (d\alpha)(d\beta) = ab = |ab|$ (for positive $a, b$; take absolute values in general). $\blacksquare$
DM5 Solution.
From $\gcd(1071, 462) = 21$, back-substitute:
$21 = 462 - 147 \times 3$
$147 = 1071 - 462 \times 2$
Substitute: $21 = 462 - (1071 - 462 \times 2) \times 3 = 462 - 1071 \times 3 + 462 \times 6 = 462 \times 7 + 1071 \times (-3)$
So $21 = 1071 \times (-3) + 462 \times 7$. Check: $-3213 + 3234 = 21$. ✓
DM6 Solution.
Since $a \mid c$, $c = am$. Since $b \mid c$, $c = bn$. Since $\gcd(a,b) = 1$, by Bézout there exist $x, y$ with $ax + by = 1$. Multiply by $c$: $acx + bcy = c$. Now $ab \mid (acx)$ (since $b \mid c$, $acx = a \cdot bn \cdot x = ab \cdot nx$) and $ab \mid (bcy)$ (since $a \mid c$, $bcy = b \cdot am \cdot y = ab \cdot my$). So $ab \mid c$. $\blacksquare$
DM7 Solution.
If $n$ is composite, then $n = ab$ with $1 < a \leq b < n$. Since $a \leq b$, we have $a^2 \leq ab = n$, so $a \leq \sqrt{n}$. Now $a > 1$ and $a \mid n$, so $a$ has a prime factor $p \leq a \leq \sqrt{n}$, and $p \mid n$. $\blacksquare$
Java Solutions
JP1 Solution.
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 gcdRec(int a, int b) {
a = Math.abs(a); b = Math.abs(b);
return b == 0 ? a : gcdRec(b, a % b);
}
// Verification:
public static void verifyGcdVersions() {
java.util.Random rng = new java.util.Random(42);
for (int i = 0; i < 10000; i++) {
int a = rng.nextInt(10000);
int b = rng.nextInt(10000);
if (a == 0 && b == 0) continue;
assert gcd(a, b) == gcdRec(a, b);
}
System.out.println("Both GCD versions agree for 10,000 random pairs.");
}JP2 Solution.
public static void sieveStatistics(int N) {
List<Integer> primes = sieve(N);
int count = primes.size();
double estimate = N / Math.log(N);
System.out.printf("Primes up to %d: %d%n", N, count);
System.out.printf("N / ln(N) ≈ %.1f%n", estimate);
System.out.printf("π(N) / (N/ln(N)) ≈ %.4f (approaches 1 as N→∞)%n",
count / estimate);
}
// For N=10000: count=1229, N/ln(N)≈1085.7, ratio≈1.1319JP3 Solution.
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]};
}
// Verify:
for (int a = 1; a <= 100; a++) {
for (int b = 1; b <= 100; b++) {
int[] r = extendedGcd(a, b);
assert a * r[1] + b * r[2] == r[0];
}
}JP4 Solution.
public static List<Integer> primeFactorization(int n) {
List<Integer> factors = new ArrayList<>();
for (int d = 2; d * d <= n; d++) {
while (n % d == 0) { factors.add(d); n /= d; }
}
if (n > 1) factors.add(n);
return factors;
}
// Verify:
for (int n = 2; n <= 1000; n++) {
List<Integer> f = primeFactorization(n);
int product = 1;
for (int p : f) { assert isPrime(p); product *= p; }
assert product == n : "Factorization of " + n + " failed";
}JP5 Solution.
public static int eulerTotient(int n) {
int count = 0;
for (int k = 1; k <= n; k++) {
if (gcd(k, n) == 1) count++;
}
return count;
}
// eulerTotient(100) = 40JP6 Solution.
public static List<int[]> twinPrimes(int limit) {
List<Integer> primes = sieve(limit);
List<int[]> twins = new ArrayList<>();
for (int i = 0; i < primes.size() - 1; i++) {
if (primes.get(i + 1) - primes.get(i) == 2) {
twins.add(new int[]{primes.get(i), primes.get(i + 1)});
}
}
return twins;
}
// Up to 1000: (3,5),(5,7),(11,13),(17,19),(29,31),(41,43),(59,61),
// (71,73),(101,103),(107,109),(137,139),(149,151),
// (179,181),(191,193),(197,199),(227,229),(239,241),
// (269,271),(281,283),(311,313),(347,349),(419,421),
// (431,433),(461,463),(521,523),(569,571),(599,601),
// (617,619),(641,643),(659,661),(809,811),(821,823),
// (827,829),(857,859),(881,883) — 35 twin prime pairsBridge Problem Solutions
BR1 Solution.
Proof: Let $d = \gcd(n, n+1)$. Then $d \mid n$ and $d \mid (n+1)$. So $d \mid (n+1-n) = 1$, giving $d = 1$. $\blacksquare$
for (int n = 1; n <= 10000; n++) {
assert gcd(n, n + 1) == 1 : "Failed for n=" + n;
}
System.out.println("gcd(n, n+1) = 1 verified for n = 1..10000");BR2 Solution.
public static int gcdWithAssertions(int origA, int origB) {
int a = Math.abs(origA), b = Math.abs(origB);
int expectedGcd = gcd(origA, origB); // precompute for checking
while (b != 0) {
assert gcd(a, b) == expectedGcd : "Invariant violated";
int oldB = b;
int r = a % b;
a = b;
b = r;
assert b < oldB : "Variant did not decrease";
}
assert a == expectedGcd : "Postcondition violated";
return a;
}BR3 Solution.
Back-substitution:
$6 = 18 - 12 \times 1$
$12 = 48 - 18 \times 2$
Substitute: $6 = 18 - (48 - 18 \times 2) = 18 \times 3 - 48 = 48 \times (-1) + 18 \times 3$.
Check: $48 \times (-1) + 18 \times 3 = -48 + 54 = 6$. ✓
Java: The extendedGcd method above implements this automatically.