STEP-BY-STEP LESSON · §8.4
Modular Arithmetic with Applications to Cryptography
Read congruence and compute remainders while respecting operation conditions.
Before you begin
Direct Proof and Counterexample IV: Divisibility
For integers d,n with d≠0, d|n means n=dk for some integer k. The vertical bar is not a fraction.
d|n ↔ ∃k∈ℤ: n=dk
Direct Proof and Counterexample V: Division into Cases and the Quotient-Remainder Theorem
For integer n and positive integer d there are unique integers q,r with n=dq+r and 0≤r<d.
n=dq+r; 0≤r<d
Equivalence Relations
An equivalence relation must be reflexive, symmetric, and transitive. The idea “treated as equivalent” must satisfy all three.
a∼b
The class [a] contains all x related to a. Reflexivity ensures that a belongs to its own class.
[a]={x∈A : x∼a}Symbols
- a≡b (mod n)
- a and b are congruent modulo n
- a mod n
- nonnegative remainder upon division by n
- gcd(a,n)
- greatest positive common divisor of integers a and n
Definitions and notation for this topic
Does not divide
a∤b
For integers a≠0 and b, a∤b means there is no integer k with b=ak.
The operands are integers. This negates divisibility under the stated nonzero-divisor convention; it is not a fraction or an inequality.
Separate glossary example
3∤10, since 10=3·3+1.
Congruence modulo m
a ≡ b (mod m)
For integers a, b and positive integer m, a−b is divisible by m.
The difference 17−2=15 is divisible by 5.
Here a,b are integers and m is a positive integer. Congruence is a relation: it says m divides a−b. In contrast, a mod m is the single remainder value.
Separate glossary example
17 ≡ 2 (mod 5)
Modulo: remainder value
a mod m
For integer a and positive integer m, a mod m is the unique integer r with a=mq+r and 0≤r<m for some integer q.
This produces one number. The statement a≡b (mod m) instead says their remainders agree. Some programming languages use a different convention for a negative dividend.
Separate glossary example
−17 mod 5=3 because −17=5(−4)+3.
Equivalence class
[a]={x∈A:x∼a}For an equivalence relation ∼ on A, [a] is the set of all elements of A equivalent to a. The relation must be stated.
Any two classes are equal or disjoint; the union of all equivalence classes is A. The brackets here do not mean a real interval or rounding down.
Separate glossary example
On ℤ modulo 3, [1]={…,−5,−2,1,4,7,…} and [1]=[4].
Step by step
Step 1 / 6
Check the difference
For integer n>1, a and b are congruent modulo n when their difference is divisible by n.
a≡b (mod n) ⇔ n | (a−b)
This means they have the same nonnegative remainder.
Worked example
Find (17+(−3)) mod 5 in two ways.
- Directly: 17−3=14=2·5+4, so the remainder is 4.
- Separately: 17=3·5+2 and −3=(−1)·5+2, so both remainders are 2.
- Add the remainders: 2+2=4. In both methods the remainder lies between 0 and 4.
Optional self-check
Which number in {0,1,2,3,4} is the inverse of 3 modulo 5?
Show answer
2, because 3·2=6≡1 (mod 5).