Number Theory, Modular Arithmetic and Algebraic Structures

Number theory, once the purest branch of mathematics, now protects every online payment.

This unit covers divisibility, the Euclidean algorithm, modular arithmetic and RSA, then introduces algebraic structures (groups) and the lattice and Boolean algebra viewpoint that unifies sets, logic and circuits.

6.1 Divisibility, primes and gcd

a divides b ( a | b) if b = a k for an integer k. Division algorithm: for integers a and d > 0 there are unique q and r with a = d q + r ,\ 0 \leq r < d.

A prime has exactly two positive divisors (2 ,\ 3 ,\ 5 ,\ 7 ,\ 11 ,\ \ldots). Fundamental theorem of arithmetic: every integer ≥ 2 factors uniquely into primes (up to order); 360 = 2^{3} \cdot 3^{2} \cdot 5.

There are infinitely many primes (Euclid, proved in Unit 1). To test whether n is prime, trial-divide by primes up to \sqrt{n}.

gcd and lcm. \gcd (a ,\ b) is the largest common divisor; \gcd (a ,\ b) · lcm(a, b ) = a b. Using factorisations: gcd takes the minimum powers, lcm the maximum. a and b are coprime if \gcd = 1.

Euclidean algorithm: \gcd (a ,\ b) = \gcd ( b, a mod b), stopping when the remainder is 0. It takes at most about 5 × (digits of the smaller number) steps, which is fast even for 300-digit numbers.

A linear Diophantine equation a x + by = c has integer solutions iff \gcd (a ,\ b) | c.

Example 6 x + 9 y = 8 has none (\gcd 3 does not divide 8 ) ;\ 6 x + 9 y = 12 does (x = - 2 ,\ y = 2).

The sieve of Eratosthenes

Eratosthenes, who also measured the size of the Earth, gave the first method for listing primes: write the numbers, cross out the multiples of 2, then of 3, then of 5 and so on up to the square root of the limit. What is left is prime.

Plate 6.1 runs the sieve on 1 to 100: crossing out multiples of 2, 3, 5 and 7 is enough because the next prime, 11, has 121 above 100. It leaves 25 primes and 8 pairs of twin primes.

(a) Eratosthenes (engraved portrait)

(b) Primes up to 100

6.2 Modular arithmetic

a \equiv b (mod m) means m | (a - b), i.e. a and b leave the same remainder. Congruence is an equivalence relation with m classes (\mathbb{Z}_{m} = \{0 ,\ 1 ,\ \ldots ,\ m - 1\}). It respects addition, subtraction and multiplication:

(a + b) mod m = ( ( a mod m ) + ( b mod m)) mod m; likewise for ×, so we can reduce at every step.

Modular inverse. a has an inverse mod m iff \gcd (a ,\ m) = 1; it is found with extended Euclid. Then a x \equiv b (mod m) has the solution x \equiv a^{-1} b.

Fermat's little theorem: if p is prime and p ∤ a, then a^{p-1} \equiv 1 (mod p).

Euler's theorem: if \gcd (a ,\ n) = 1 then a^{\varphi (n)} \equiv 1 (mod n), where \varphi (n) counts integers up to n coprime to n ;\ \varphi (p) = p - 1 ,\ \varphi (p q) = (p - 1) (q - 1).

Chinese remainder theorem (CRT): if the moduli are pairwise coprime, the system x \equiv a_{i} (mod m_{i}) has a unique solution modulo M = \prod m_{i}.

Arithmetic on a clock face

A clock does arithmetic modulo 12: after 12 it starts again at 0. Ten o'clock plus seven hours is five o'clock because 17 = 12 + 5, which we write 17 mod 12 = 5.

Powers also cycle: successive powers of 3 modulo 7 are 3, 2, 6, 4, 5, 1 and then repeat, a pattern that cryptography relies on. Plate 6.2 shows the clock sums and the six-step cycle computed with Python's pow.

(a) Clock face: hours are numbers modulo 12

(b) Clock sums and the cycle of powers of 3 mod 7

6.3 Applications

• Hashing: h (k) = k mod m with m prime spreads keys well. Keys 123, 456, 789 with m = 11 give 2, 5, 8 (789 = 71·11 + 8).
• Check digits: ISBN-10 requires \sum (i \times d_{i}) \equiv 0 (mod 11); a single wrong digit is always detected, since 11 is prime.
• Pseudo-random numbers: linear congruential generator X_{n+1} = (a X_{n} + c) mod m.
• Caesar cipher: E (x) = (x + 3) mod 26 ,\ D (y) = (y - 3) mod 26; "NEPAL" becomes "QHSDO". It is weak (26 keys); an affine cipher E (x) = (a x + b) mod 26 needs \gcd (a ,\ 26) = 1.
• Fast modular exponentiation (square and multiply) computes a^{k} mod m in O (\log k) multiplications: 3^{13} mod 7: 3^{2} = 2 ,\ 3^{4} = 4 ,\ 3^{8} = 16 \equiv 2 ;\ 13 = 8 + 4 + 1 \Rightarrow 2 \cdot 4 \cdot 3 = 24 ≡ 3.

RSA public-key cryptography.

1. Choose primes p ,\ q ;\ n = p q ;\ \varphi = (p - 1) (q - 1).
2. Choose e coprime to φ (public key (e ,\ n)); compute d = e^{-1} mod φ (private key).
3. Encrypt: c = m^{e} mod n. Decrypt: m = c^{d} mod n (correct by Euler's theorem since ed ≡ 1 mod φ).

Enigma: a lot of modular arithmetic

The German Enigma machine was a chain of rotors, each a permutation of the 26 letters, advancing like an odometer, so every key press was enciphered with a different permutation.

The number of possible settings is a counting problem from Chapter 3.

Choosing and ordering three rotors from five gives 60 ways; each rotor starts at one of 26 positions (17,576 combinations); and the plugboard joined ten pairs of letters. Plate 6.3 multiplies the three factors.

(a) Enigma M4: keyboard, rotors and lamps

(b) Counting the settings of an Enigma

6.4 Algebraic structures

A binary operation on a set S takes two elements and returns an element of S (closure).

Structure	Axioms
Semigroup	closed, associative
Monoid	semigroup with an identity
Group	monoid where every element has an inverse
Abelian group	commutative group
Ring	abelian group under +, monoid (or semigroup) under ×, × distributes over +
Field	commutative ring where every non-zero element has a multiplicative inverse

Examples: (\mathbb{Z}, +) is an abelian group; (\mathbb{N}, +) is a monoid; (\mathbb{Z} ,\ \times) is a monoid; (\mathbb{Q} − {0}, ×) is a group; \mathbb{Z}_{p} with + and × is a field when p is prime (that is why inverses mod a prime always exist); strings under concatenation form a monoid (identity: empty string); invertible n \times n matrices under multiplication form a (non-abelian) group; the permutations of n objects form the symmetric group S_{n} of order n !.

A homomorphism preserves the operation: f ( a ∗ b ) = f ( a) ⋆ f (b).

Example x ↦ x mod 3 from (\mathbb{Z}, +) to (\mathbb{Z}_{3}, +), and x ↦ e^{x} from (\mathbb{R}, +) to (\mathbb{R}^{+} ,\ \times).

Applications: error-correcting codes are built on finite fields (Reed–Solomon in QR codes, CDs); AES uses arithmetic in G F (2^{8}); elliptic-curve cryptography uses a group of curve points.

6.5 Lattices and Boolean algebra

A lattice is a poset in which every two elements have a least upper bound (join, ∨) and a greatest lower bound (meet, ∧). Examples: (subsets of S ,\ \subseteq) with ∪ and ∩; (divisors of n, |) with lcm and \gcd ;\ (\mathbb{N} ,\ \leq) with max and min.

A Boolean algebra is a complemented distributive lattice with 0 and 1.

The two-element algebra {0, 1} is the algebra of switching circuits and of propositional logic; the power set of a set is another; every finite Boolean algebra has 2^{n} elements and looks like subsets of an n-set.

This is why the same laws (De Morgan, distributivity, absorption) hold in logic (Unit 1), sets (Unit 2) and digital circuits (the Digital Logic book): they are three views of one structure.

Divisor lattice of 12: elements {1, 2, 3, 4, 6, 12}; join of 4 and 6 = lcm = 12; meet = \gcd = 2. It is not complemented (4 has no complement), so it is a lattice but not a Boolean algebra; the divisors of 30 (= 2·3·5) form one, with 8 = 2^{3} elements.

The divisors of 12 form a lattice

Under divisibility, the divisors of 12 form a partial order in which every pair of elements has a greatest common divisor (the meet) and a least common multiple (the join).

A Hasse diagram draws only the covering relations: a line from a to b if a divides b and nothing lies strictly between. Plate 6.4 finds those lines by program and confirms that \gcd (4 ,\ 6) = 2 and lcm(4, 6 ) = 12.

(a) Hasse diagram of the subgroups of D4

(b) Divisibility lattice of 12

6.6 Clock arithmetic and the RSA message path

Modular arithmetic is clock arithmetic. On a 12-hour clock, 9 + 7 = 16, which the clock shows as 4, because 16 = 12 + 4, written 16 \equiv 4 (mod 12).

The left half of Figure 6.1 shows this "wrap-around": adding 7 hours to 9 o'clock walks 7 steps round the dial and lands on 4.

The same picture explains why 7 has an inverse mod 12 but 4 does not: stepping 7 at a time visits all 12 positions (\gcd (7 ,\ 12) = 1), whereas stepping 4 at a time only ever visits 0, 4 and 8 (\gcd (4 ,\ 12) = 4).

The right half traces the toy RSA of Section 6.3 from the sender to the receiver: only the receiver's private number d = 2753 can undo the public encryption.

Caesar and Alberti: encryption as modular addition

Shifting every letter three places, as Julius Caesar did, is addition modulo 26: encrypt with c = (p + 3) mod 26 and decrypt with p = (c - 3) mod 26.

Leon Battista Alberti built a disc with two alphabets that can be turned, so the shift changes during the message. There are only 25 useful Caesar keys, so an attacker simply tries all of them.

Plate 6.5 encrypts NEPAL and shows the shifted alphabet.

(a) Cipher disc after Alberti: turn the inner ring to change the key

(b) Caesar shift of 3

6.7 Eight uses of number theory and algebraic structures

1. Online banking and payments. RSA and elliptic-curve keys protect the HTTPS link between your phone and an a p p such as ConnectIPS or Fonepay. The modular exponentiation of Section 6.3 runs every time a secure session starts.
2. Hash tables. The function h (k) = k mod m spreads student roll numbers or customer IDs over m slots. Choosing a prime m reduces collisions, so lookups stay fast even for a large university database.
3. Check digits. ISBN, bank-card and barcode numbers end with a digit computed with modular arithmetic. A single mistyped digit is caught immediately because the modulus is prime or coprime to the weights.
4. Error-correcting codes. QR codes and CDs use Reed–Solomon codes built on finite fields. A damaged label on a parcel can still be scanned because the missing data is rebuilt from the extra field-based symbols.
5. Calendars and schedules. Day-of-week calculations use mod 7, clock times use mod 12 or mod 24, and rotating duty rosters use mod n. Converting a Bikram Sambat date to a weekday is a modular exercise.
6. Random numbers. A linear congruential generator X (n + 1) = (aXn + c) mod m produces the pseudo-random numbers behind simulations and games. Choosing a ,\ c and m with the right gcd conditions gives a long, non-repeating cycle.
7. Symmetric encryption. AES works on bytes as elements of the field G F (2^{8}), so every substitution step is invertible. This is what protects stored passwords and Wi-Fi traffic in homes and offices.
8. Circuit design and logic. A Boolean algebra is the common law-book of logic, sets and switching circuits. Simplifying an expression with these laws gives a cheaper chip with fewer gates.

Formula and fact sheet

• a = d q + r ;\ \gcd (a ,\ b) = \gcd ( b, a mod b ) ;\ \gcd · lcm = a b; Bézout: \gcd = a x + by.
• a \equiv b (mod m ) \Leftrightarrow m | a - b; inverse exists iff \gcd (a ,\ m) = 1.
• Fermat: a^{p-1} \equiv 1 (mod p). Euler: a^{\varphi} (n) \equiv 1 ;\ \varphi (p q) = (p - 1) (q - 1).
• CRT: coprime moduli give a unique solution mod the product.
• RSA: n = p q, ed ≡ 1 (mod \varphi ) ,\ c = m^{e} mod n ,\ m = c^{d} mod n.
• Group: closure, associativity, identity, inverse. \mathbb{Z}_{p} is a field for prime p. Lagrange: subgroup order divides group order.
• Finite Boolean algebra has 2^{n} elements.

Chapter summary

• The Euclidean algorithm computes gcds quickly and the extended version yields inverses.
• Modular arithmetic lets us compute with remainders; Fermat, Euler and the CRT are its workhorses.
• RSA turns the difficulty of factoring into public-key encryption.
• Groups, rings and fields classify structures by their axioms; Boolean algebras unify logic, sets and circuits.

Practice

1. Find \gcd ( 1071, 462) and express it as 1071 x + 462 y.
2. Find 5^{-1} mod 17 and solve 5 x \equiv 3 (mod 17).
3. Find the last two digits of 3^{100} (hint: 3^{20} mod 100).
4. Solve x \equiv 1 (mod 4 ) ,\ x \equiv 2 (mod 9) (use CRT).
5. Compute 7^{100} mod 13 using Fermat's theorem.
6. In RSA with p = 5 ,\ q = 11 ,\ e = 7, find n ,\ \varphi ,\ d, the ciphertext of m = 8 and verify decryption.
7. Is (\mathbb{Z}_{8} − {0}, × mod 8) a group? Justify.
8. List all subgroups of (\mathbb{Z}_{12}, +).
9. Show that the ISBN-10 check digit detects any single wrong digit.
10. Is the divisor lattice of 18 a Boolean algebra?

Answers and worked solutions

1. 1071 = 2·462 + 147; 462 = 3·147 + 21; 147 = 7·21. \gcd = 21. 21 = 462 − 3·147 = 462 - 3 ( 1071 − 2·462) = 7·462 − 3·1071. So x = - 3 ,\ y = 7.

2. 5 \cdot 7 = 35 = 2·17 + 1, so 5^{-1} = 7. 5 x \equiv 3 \Rightarrow x ≡ 7·3 = 21 ≡ 4 (check 20 mod 17 = 3 ✓).

3. 3^{4} = 81 ;\ 3^{20} = 81^{5}: 81^{2} = 6561 \equiv 61 ;\ 81^{4} \equiv 61^{2} = 3721 \equiv 21 ;\ 81^{5} ≡ 21·81 = 1701 \equiv 1. So 3^{20} \equiv 1 (mod 100) and 3^{100} ≡ 01.

4. x = 1 + 4 t \equiv 2 (mod 9 ) \Rightarrow 4 t \equiv 1 \Rightarrow t \equiv 7 (4·7 = 28 \equiv 1 ) \Rightarrow x = 29. Solutions x \equiv 29 (mod 36) (29 mod 4 = 1, 29 mod 9 = 2 ✓).

5. 7^{12} \equiv 1 (mod 13); 100 = 8·12 + 4 ;\ 7^{4} = 2401 = 184·13 + 9. So 7^{100} ≡ 9.

6. n = 55 ,\ \varphi = 40 ;\ d = 7^{-1} mod 40 = 23 (7·23 = 161 = 4·40 + 1). c = 8^{7} mod 55: 8^{2} = 64 \equiv 9 ;\ 8^{4} \equiv 81 \equiv 26 ;\ 8^{6} ≡ 26·9 = 234 \equiv 14 ;\ 8^{7} \equiv 112 ≡ 2.

Decrypt 2^{23} mod 55: 2^{10} = 1024 \equiv 34 ;\ 2^{20} \equiv 34^{2} = 1156 \equiv 1 ;\ 2^{23} \equiv 8 ✓.

7. No: 2, 4, 6 have no inverse (gcd with 8 is not 1) and 2·4 = 8 \equiv 0 is not in the set.

8. Subgroups of \mathbb{Z}_{12} correspond to divisors of 12: ⟨1⟩ (order 12), ⟨2⟩ = {0,2,4,6,8,10} (6), ⟨3⟩ = {0,3,6,9} (4), ⟨4⟩ = {0,4,8} (3), ⟨6⟩ = {0,6} (2), ⟨0⟩ = {0} (1): six subgroups.

9. If digit i (weight i) changes by \delta \neq 0 (|\delta| \leq 10), the weighted sum changes by i \delta, which is not ≡ 0 (mod 11) because 11 is prime and divides neither i (1 to 10) nor δ.

10. 18 = 2 \cdot 3^{2} is not square-free (it has a repeated prime factor), so the divisor lattice (1, 2, 3, 6, 9, 18) is not a Boolean algebra (6 elements is not 2^{n}).

Model answers: medium (5 marks) and long (10 marks) questions

Q1 (5 marks). Find \gcd ( 252, 105) with the Euclidean algorithm, express it as 105 x + 252 y, and state when 105 has an inverse modulo 252.

Introduction. The Euclidean algorithm uses the identity \gcd (a ,\ b) = \gcd ( b, a mod b). It stops when a remainder is 0, and the last non-zero remainder is the gcd.

Division steps.

1. 252 = 2 \times 105 + 42
2. 105 = 2 \times 42 + 21
3. 42 = 2 \times 21 + 0

The last non-zero remainder is 21, so \gcd (252 ,\ 105) = 21, and lcm = 252 \times 105 \div 21 = 1,260.

Extended Euclid (Bézout). Work backwards: 21 = 105 - 2 \times 42, and 42 = 252 - 2 \times 105, so 21 = 105 - 2 (252 - 2 \times 105) = 5 \times 105 - 2 \times 252. Hence x = 5 and y = - 2.

Check 525 - 504 = 21.

Inverse. An inverse of a modulo m exists if and only if \gcd (a ,\ m) = 1. Here \gcd (105 ,\ 252) = 21, not 1, so 105 has no inverse modulo 252. By contrast, 7 has the inverse 15 modulo 26 because 7 \times 15 = 105 = 4 \times 26 + 1.

Conclusion. The extended Euclidean algorithm gives the gcd and the coefficients together; the coefficients are what produce modular inverses in RSA.

Q2 (10 marks). Explain the RSA algorithm with a numerical example, and state the group, ring and field axioms with one example each.

Introduction. RSA is a public-key system: anyone can encrypt with the public key, but only the owner of the private key can decrypt. Its security rests on the difficulty of factoring a large number n = p q.

Algorithm.

1. Choose primes. p = 61 ,\ q = 53.
2. Compute n and φ. n = p q = 3,233; \varphi = (p - 1) (q - 1) = 60 \times 52 = 3,120.
3. Public exponent. Choose e = 17, coprime to 3,120. The public key is (17, 3233).
4. Private exponent. d = e^{-1} mod φ = 2,753, since 17 × 2,753 = 46,801 = 15 × 3,120 + 1.
5. Encrypt. For m = 65 ,\ c = 65^{17} mod 3233 = 2,790.
6. Decrypt. m = 2790^{2753} mod 3233 = 65. This works because ed ≡ 1 (mod φ) and Euler's theorem.

Figure 6.1 shows this path. Real keys use n of 2,048 bits or more, with padding such as OAEP.

Algebraic structures.

7. Group. A set with one operation that is closed, associative, has an identity and has inverses. Example: \mathbb{Z}_{6} under addition mod 6 (identity 0, inverse of 2 is 4); it is cyclic, generated by 1.
8. Ring and field. A ring has two operations (addition forms an abelian group, multiplication is associative and distributes over addition); \mathbb{Z} is a ring. A field also gives every non-zero element a multiplicative inverse; \mathbb{Z}_{p} is a field when p is prime.

Structure	Axioms	Example
Semigroup	closed, associative	(\mathbb{N}, +)
Monoid	+ identity	(\mathbb{Z} ,\ \times)
Group	+ inverses	(\mathbb{Z}, +)
Ring	two operations, distributive	\mathbb{Z}
Field	non-zero elements invertible	\mathbb{Z}_{7}

Conclusion. RSA uses arithmetic in the ring \mathbb{Z}_{n} and the group of units mod φ, so its correctness is an application of group theory. The same structures also underlie AES and elliptic-curve cryptography.