SEM 6 › Discrete Mathematics › Week 06
Discrete Mathematics · Week 06

Number Theory & Cryptography

Divisibility and its theorem, the division algorithm (div and mod), congruence modulo m, congruence classes, primes and composites, the fundamental theorem of arithmetic, and Caesar's cipher.

ITE38221 video · 33 min📄 Lesson 6 - Number Theory Cryptography.pdf

1Divisibility

Number theory ("higher arithmetic") studies integers and their properties. This lesson covers divisibility, modular arithmetic, primes and a cryptography application.

Definition 1

Let a and b be integers with a ≠ 0. If there is an integer c with b = ac, then a divides b, written a | b.

  • a is a factor of b; b is a multiple of a.
  • If a does not divide b, write a ∤ b.
Example 6.1.1
  • 20/4 = 5 is an integer, so 4 | 20.
  • 17/6 is not an integer, so 6 ∤ 17.
Don't confuse the notations

a | b is a statement (true or false): "a divides b". a / b is a number: a divided by b.

3 | 12 is true; 12/3 = 4.

Theorem 1 — properties of divisibility

For integers a, b, c:

  1. If a | b and a | c, then a | (b + c).
  2. If a | b, then a | bc for every integer c.
  3. If a | b and b | c, then a | c (transitivity).
Proofs (direct, using the definition)

(i) a | b and a | c, so b = as and c = at for integers s and t. Then b + c = as + at = a(s + t), so a | (b + c). ∎

(ii) a | b, so b = as. Then bc = asc = a(sc), so a | bc. ∎

(iii) b = as and c = bt, so c = (as)t = a(st), so a | c. ∎

Corollary

If a | b and a | c, then a | (mb + nc) for any integers m and n.

Proof: by (ii), a | mb and a | nc. Then by (i), a | mb + nc. ∎

2The division algorithm

Theorem 2 (the division algorithm)

Let a be an integer and d a positive integer. Then there are unique integers q and r with 0 ≤ r < d such that

a = dq + r

Name Symbol Notation
Dividend a —
Divisor d —
Quotient q q = a div d
Remainder r r = a mod d
Examples 6.2.1 and 6.2.2
  • 27 ÷ 4: 27 = 4·6 + 3, so 6 = 27 div 4 and 3 = 27 mod 4.
  • −23 ÷ 5: −23 = 5·(−5) + 2, so −5 = −23 div 5 and 2 = −23 mod 5.
The remainder is never negative

For −23 ÷ 5 the answer is not q = −4, r = −3. The remainder must satisfy 0 ≤ r < d. So go one step further down: q = −5, and r = −23 − (−25) = 2.

If the remainder is zero, then x is divisible by y (y | x).

🧪 Try it — Division algorithm & mod calculator

3Modular arithmetic & congruence

Definition 2 — congruence

Let m be a positive integer. a is congruent to b modulo m, written a ≡ b (mod m), if m divides a − b. If not, write a ≢ b (mod m).

Theorem 3

a ≡ b (mod m) if and only if a mod m = b mod m: a and b leave the same remainder.

Example 6.3.1
  • Is 17 ≡ 3 (mod 7)? 17 − 3 = 14, and 7 | 14. Yes, 17 ≡ 3 (mod 7).
  • Is 21 ≡ 6 (mod 8)? 21 − 6 = 15, and 8 ∤ 15. No, 21 ≢ 6 (mod 8).
Theorem 4 — you can add and multiply congruences

If a ≡ b (mod m) and c ≡ d (mod m), then:

  • a + c ≡ b + d (mod m)
  • ac ≡ bd (mod m)
Example 6.3.2

12 ≡ 2 (mod 5) and 16 ≡ 1 (mod 5). So:

  • 28 = 12 + 16 ≡ 2 + 1 = 3 (mod 5)
  • 192 = 12·16 ≡ 2·1 = 2 (mod 5)

Congruence classes (Definition 3)

The congruence class of a modulo n is the set of all integers with the same remainder as a when divided by n.

Example 6.3.3

… ≡ −40 ≡ −33 ≡ −26 ≡ −19 ≡ −12 ≡ −5 ≡ 2 ≡ 9 ≡ 16 ≡ 23 ≡ 30 ≡ 37 ≡ … ≡ 2 (mod 7)

So the congruence class of 2 modulo 7 is {…, −40, −33, −26, −19, −12, −5, 2, 9, 16, 23, 30, 37, …}. Start at 2 and keep adding or subtracting 7.

🧪 Try it — Congruence checker & class lister

4Primes

Every positive integer greater than 1 is divisible by at least 1 and itself.

Definition 4
  • A positive integer p > 1 is prime if its only positive factors are 1 and p.
  • An integer > 1 that is not prime is composite.
  • Equivalently, a prime is a natural number > 1 that can't be written as a product of two smaller natural numbers.
  • Remark: n is composite ⇔ there is an integer a with a | n and 1 < a < n.
Example Reasoning
7 is prime (6.4.1) The only products are 1 × 7 and 7 × 1
6 is composite (6.4.2) 6 = 2 × 3, both smaller than 6
Every even integer > 2 is composite (6.4.3) x = 2 × (x/2), and x/2 is an integer
Theorem 5 (Euclid)

There are infinitely many primes. If p₁, …, pₙ are the n smallest primes, there is always a larger prime not in that list.

Theorem 6 — the fundamental theorem of arithmetic

Every positive integer greater than 1 can be written uniquely as a prime or as a product of two or more primes, with the prime factors in non-decreasing order.

Example 6.4.4 — A = {4, 5, 12, 49, 748}
n Prime or composite Prime factorisation
4 Composite 2²
5 Prime 5
12 Composite 2² × 3
49 Composite 7²
748 Composite 2² × 11 × 17
🧪 Try it — Prime checker & factoriser
Fast primality check

To test n, you only need to try divisors up to √n. If n = ab with both a and b greater than √n, then ab > n, which is impossible.

5Cryptography — Caesar's cipher

Cryptography is the study of secret messages. It has two parts:

  • Encryption: making a message secret.
  • Decryption: recovering the original message.

Caesar's cipher (used by Julius Caesar) shifts each letter three places forward. So C → F and Y → B (it wraps around).

Number the letters A = 0, B = 1, …, Z = 25. Then:

Encrypt: f(p) = (p + 3) mod 26
Decrypt: f⁻¹(p) = (p − 3) mod 26

f is one-to-one (in fact a bijection) on {0, …, 25}, so f⁻¹ exists. Both domain and codomain are {0, 1, …, 25}.

Example 6.5.1 — encrypt YARD
Letter Y A R D
p 24 0 17 3
(p + 3) mod 26 27 ≡ 1 3 20 6
Cipher B D U G

YARD → BDUG

Decrypt CHVW
Letter C H V W
p 2 7 21 22
(p − 3) mod 26 −1 ≡ 25 4 18 19
Plain Z E S T

CHVW → ZEST. (Note −1 = 26 × (−1) + 25, so −1 mod 26 = 25.)

🧪 Try it — Caesar cipher machine
Exam focus

Expect:

  • Deciding a | b
  • Proving divisibility properties (direct proofs using b = as)
  • Quotient and remainder including negatives
  • a mod m
  • Checking congruences
  • Listing congruence classes
  • Prime or composite + prime factorisation
  • Caesar encryption and decryption with a working table

6Quick revision sheet

Concept Remember it as
a | b b = ac for some integer c (a ≠ 0); a ∤ b otherwise
Theorem 1 a|b, a|c ⇒ a|(b+c); a|b ⇒ a|bc; a|b, b|c ⇒ a|c
Corollary a|b, a|c ⇒ a|(mb + nc)
Division algorithm a = dq + r, 0 ≤ r < d; q = a div d, r = a mod d
Negative a −23 = 5(−5) + 2, so r = 2 (never negative)
a ≡ b (mod m) m | (a − b) ⇔ same remainder
Theorem 4 Can add and multiply congruences
Congruence class All integers with the same remainder: r + km
Prime > 1, factors only 1 and itself; composite otherwise
Euclid Infinitely many primes
FTA Unique prime factorisation (748 = 2² × 11 × 17)
Caesar Encrypt (p + 3) mod 26; decrypt (p − 3) mod 26; YARD → BDUG

?Self-check quiz

12 questions on this week. Answer them all, then press Check my answers. Your best and latest scores are saved and shown on the subject page.

← PreviousMatricesNext →Mathematical Induction & Recursion