Divisibility: Deep Dive
Formal Definition
Let a, b ∈ ℤ with a ≠ 0. We say a divides b (written a | b) if there exists an integer c such that b = ac.
Alternative names:
- a is a divisor of b
- a is a factor of b
- b is a multiple of a
- b is divisible by a
Important Examples
Example 1: 7 | 21
- Because 21 = 7 × 3
- 7 is a divisor of 21 ✓
Example 2: 5 ∤ 23
- Because 23 = 5 × 4 + 3 (has remainder)
- 5 does not divide 23 ✗
Example 3: -6 | 18
- Because 18 = -6 × (-3)
- Negative numbers can be divisors too ✓
Example 4: Special cases
- Every integer divides 0: n | 0 for all n ≠ 0 (because 0 = n × 0)
- 1 divides everything: 1 | n for all n
- Every non-zero integer divides itself: n | n
Divisibility Properties (Theorems)
Property 1: Transitivity
Theorem: If a | b and b | c, then a | c.
Proof:
- Since a | b, we have b = ak for some integer k
- Since b | c, we have c = bm for some integer m
- Substituting: c = (ak)m = a(km)
- Since km is an integer, a | c ✓
Example: 2 | 6 and 6 | 18, therefore 2 | 18
Property 2: Linear Combination
Theorem: If a | b and a | c, then a | (mb + nc) for any integers m, n.
Proof:
- Since a | b, we have b = ak₁
- Since a | c, we have c = ak₂
- Then mb + nc = m(ak₁) + n(ak₂) = a(mk₁ + nk₂)
- Since mk₁ + nk₂ is an integer, a | (mb + nc) ✓
Example:
- 5 | 10 and 5 | 15
- Therefore 5 | (3×10 + 2×15) = 5 | 60 ✓
Property 3: Product Property
Theorem: If a | b, then a | bc for any integer c.
Proof:
- Since a | b, we have b = ak
- Then bc = (ak)c = a(kc)
- Since kc is an integer, a | bc ✓
Example: 4 | 12, therefore 4 | (12 × 7) = 4 | 84 ✓
Property 4: Divisors of Sum/Difference
Theorem: If a | b and a | c, then:
- a | (b + c)
- a | (b - c)
Example:
- 7 | 14 and 7 | 21
- Therefore 7 | (14 + 21) = 7 | 35 ✓
- And 7 | (21 - 14) = 7 | 7 ✓
Finding All Divisors
Example: Find all positive divisors of 24.
Method: Check each number from 1 to 24:
- 1 | 24 (24 = 1 × 24) ✓
- 2 | 24 (24 = 2 × 12) ✓
- 3 | 24 (24 = 3 × 8) ✓
- 4 | 24 (24 = 4 × 6) ✓
- 5 ∤ 24 ✗
- 6 | 24 (24 = 6 × 4) ✓
- 8 | 24 (24 = 8 × 3) ✓
- 12 | 24 (24 = 12 × 2) ✓
- 24 | 24 (24 = 24 × 1) ✓
Answer: Divisors of 24 = {1, 2, 3, 4, 6, 8, 12, 24}
Tip: Only check up to √24 ≈ 4.9, then include pairs!
Modular Arithmetic
Introduction
Modular arithmetic is sometimes called “clock arithmetic” because it’s like how hours wrap around on a clock. After 12 comes 1, not 13.
Definition of Congruence
Definition: Let a, b, m ∈ ℤ with m > 0. We say a is congruent to b modulo m, written:
a ≡ b (mod m)
if m | (a - b), that is, if m divides (a - b).
Alternative definition: a ≡ b (mod m) if a and b have the same remainder when divided by m.
Understanding Modular Arithmetic
Example 1: Is 17 ≡ 5 (mod 6)?
Method 1 (Division):
- 17 - 5 = 12
- Does 6 | 12? Yes, 12 = 6 × 2
- Therefore, 17 ≡ 5 (mod 6) ✓
Method 2 (Remainders):
- 17 = 6 × 2 + 5 (remainder 5)
- 5 = 6 × 0 + 5 (remainder 5)
- Same remainder, so 17 ≡ 5 (mod 6) ✓
Example 2: Is 23 ≡ 8 (mod 5)?
- 23 - 8 = 15
- 5 | 15 ✓
- Therefore, 23 ≡ 8 (mod 5) ✓
Example 3: Is 14 ≡ 5 (mod 4)?
- 14 - 5 = 9
- 4 ∤ 9 (9 = 4 × 2 + 1) ✗
- Therefore, 14 ≢ 5 (mod 4) ✗
The Modulo Operation
The expression a mod m gives the remainder when a is divided by m.
Examples:
- 17 mod 5 = 2 (because 17 = 5 × 3 + 2)
- 23 mod 7 = 2 (because 23 = 7 × 3 + 2)
- 100 mod 13 = 9 (because 100 = 13 × 7 + 9)
- 24 mod 6 = 0 (because 24 = 6 × 4 + 0)
- -7 mod 3 = 2 (because -7 = 3 × (-3) + 2)
Note: The result of a mod m is always in the range [0, m-1].
Clock Analogy
12-Hour Clock:
- 15:00 (3 PM) ≡ 3 (mod 12)
- 25 hours after midnight ≡ 1 (mod 12) = 1 AM
- 14 ≡ 2 (mod 12)
Days of the Week (mod 7):
- If today is Monday (day 0), what day is it in 10 days?
- 10 mod 7 = 3
- 3 days after Monday = Thursday
Properties of Modular Arithmetic
Property 1: Reflexive
a ≡ a (mod m) for all a
Proof: m | (a - a) = m | 0, which is always true.
Property 2: Symmetric
If a ≡ b (mod m), then b ≡ a (mod m)
Proof: If m | (a - b), then m | -(a - b) = m | (b - a)
Property 3: Transitive
If a ≡ b (mod m) and b ≡ c (mod m), then a ≡ c (mod m)
Proof:
- m | (a - b) means a - b = mk₁
- m | (b - c) means b - c = mk₂
- Adding: (a - b) + (b - c) = mk₁ + mk₂
- a - c = m(k₁ + k₂)
- Therefore m | (a - c) ✓
Arithmetic Operations in Modular Arithmetic
Addition
If a ≡ b (mod m) and c ≡ d (mod m), then: a + c ≡ b + d (mod m)
Example:
- 17 ≡ 2 (mod 5) and 23 ≡ 3 (mod 5)
- Therefore, 17 + 23 ≡ 2 + 3 (mod 5)
- 40 ≡ 5 (mod 5) ✓
Subtraction
If a ≡ b (mod m) and c ≡ d (mod m), then: a - c ≡ b - d (mod m)
Example:
- 22 ≡ 1 (mod 7) and 15 ≡ 1 (mod 7)
- Therefore, 22 - 15 ≡ 1 - 1 (mod 7)
- 7 ≡ 0 (mod 7) ✓
Multiplication
If a ≡ b (mod m) and c ≡ d (mod m), then: ac ≡ bd (mod m)
Example:
- 11 ≡ 3 (mod 4) and 9 ≡ 1 (mod 4)
- Therefore, 11 × 9 ≡ 3 × 1 (mod 4)
- 99 ≡ 3 (mod 4) ✓
Exponentiation
If a ≡ b (mod m), then: aⁿ ≡ bⁿ (mod m) for any positive integer n
Example:
- 7 ≡ 2 (mod 5)
- Therefore, 7³ ≡ 2³ (mod 5)
- 343 ≡ 8 (mod 5)
- 343 mod 5 = 3, and 8 mod 5 = 3 ✓
Solving Congruence Equations
Example 1: Solve 3x ≡ 7 (mod 5)
Try values:
- x = 0: 3(0) = 0 ≡ 0 (mod 5) ✗
- x = 1: 3(1) = 3 ≡ 3 (mod 5) ✗
- x = 2: 3(2) = 6 ≡ 1 (mod 5) ✗
- x = 3: 3(3) = 9 ≡ 4 (mod 5) ✗
- x = 4: 3(4) = 12 ≡ 2 (mod 5) ✗
Wait, 7 ≡ 2 (mod 5), so we need 3x ≡ 2 (mod 5)
- x = 4: 3(4) = 12 ≡ 2 (mod 5) ✓
Answer: x ≡ 4 (mod 5), meaning x = 4, 9, 14, 19, …
Example 2: Solve 5x ≡ 1 (mod 6)
Try values:
- x = 0: 5(0) = 0 ≢ 1 (mod 6)
- x = 1: 5(1) = 5 ≢ 1 (mod 6)
- x = 2: 5(2) = 10 ≢ 1 (mod 6)
- x = 3: 5(3) = 15 ≢ 1 (mod 6)
- x = 4: 5(4) = 20 ≢ 1 (mod 6)
- x = 5: 5(5) = 25 ≡ 1 (mod 6) ✓
Answer: x ≡ 5 (mod 6)
Applications of Modular Arithmetic
Application 1: Check Digits
ISBN-10 uses modular arithmetic to detect errors.
ISBN: 0-306-40615-2
- Check: (0×10 + 3×9 + 0×8 + 6×7 + 4×6 + 0×5 + 6×4 + 1×3 + 5×2 + 2×1) ≡ 0 (mod 11)
Application 2: Days of the Week
Given today is Wednesday, what day is it in 100 days?
- 100 mod 7 = 2
- 2 days after Wednesday = Friday
Application 3: Cryptography
RSA encryption uses modular exponentiation.
Application 4: Hash Tables
Hash functions often use: hash(key) = key mod table_size
Computing Large Powers
Example: Find 2¹⁰⁰ mod 7
Method (using properties):
- 2³ = 8 ≡ 1 (mod 7)
- 2¹⁰⁰ = (2³)³³ × 2¹
- (2³)³³ ≡ 1³³ ≡ 1 (mod 7)
- 2¹⁰⁰ ≡ 1 × 2 ≡ 2 (mod 7)
Answer: 2¹⁰⁰ mod 7 = 2
Modular Inverse
Definition: The modular inverse of a modulo m is an integer b such that:
ab ≡ 1 (mod m)
Example: Find the inverse of 3 modulo 7.
Try values:
- 3 × 1 = 3 ≢ 1 (mod 7)
- 3 × 2 = 6 ≢ 1 (mod 7)
- 3 × 3 = 9 ≡ 2 (mod 7)
- 3 × 4 = 12 ≡ 5 (mod 7)
- 3 × 5 = 15 ≡ 1 (mod 7) ✓
Answer: The inverse of 3 modulo 7 is 5.
Note: Not every number has an inverse. a has an inverse mod m if and only if gcd(a, m) = 1.
Divisibility Rules Using Modular Arithmetic
Divisibility by 3
A number is divisible by 3 if and only if the sum of its digits is divisible by 3.
Example: Is 5421 divisible by 3?
- Sum of digits: 5 + 4 + 2 + 1 = 12
- 12 is divisible by 3
- Therefore, 5421 is divisible by 3 ✓
Why? Because 10 ≡ 1 (mod 3), so 10ⁿ ≡ 1 (mod 3)
Divisibility by 9
A number is divisible by 9 if and only if the sum of its digits is divisible by 9.
Divisibility by 11
A number is divisible by 11 if the alternating sum of its digits is divisible by 11.
Example: Is 1234 divisible by 11?
- Alternating sum: 1 - 2 + 3 - 4 = -2
- -2 is not divisible by 11
- Therefore, 1234 is not divisible by 11 ✗
Key Points for Exams
- a | b means b = ac for some integer c
- a ≡ b (mod m) means m | (a - b)
- Modular arithmetic preserves addition, subtraction, multiplication
- a mod m gives the remainder (always between 0 and m-1)
- Transitivity applies to both divisibility and congruence
- Check work by computing both sides
- Use properties to simplify complex calculations
- Modular inverse exists only if gcd(a, m) = 1
- Clock arithmetic is a good mental model
- Practice divisibility rules - very useful
Practice Problems
-
Find 7⁵⁰ mod 6
-
Solve: 4x ≡ 3 (mod 7)
-
Is 1234567 divisible by 3?
-
Prove: If a ≡ b (mod m), then aⁿ ≡ bⁿ (mod m)
-
Find the inverse of 5 modulo 11
-
What day of the week is it 365 days from Tuesday?
-
Compute: (23 × 47) mod 10
-
Show that 10ⁿ ≡ 1 (mod 9) for all n ≥ 0
-
Find all solutions to 3x ≡ 6 (mod 9)
-
Prove: If a | b and b | a, then a = ±b