Number Theory and Modular Arithmetic

Introduction and Context

Number theory studies the properties of integers, including divisibility, prime numbers, greatest common divisors, and congruences. Although many results originated in pure mathematics, they are central to modern computing. Hash functions, pseudorandom number generators, public-key cryptography, error detection, scheduling systems, and data structures all use number-theoretic ideas.

For AI and ML students, number theory is especially relevant to secure model deployment, privacy-preserving computation, authenticated data pipelines, randomized algorithms, and the implementation of cryptographic libraries. The central theme of this chapter is that arithmetic over integers can be transformed into arithmetic over finite sets of remainders. This transformation produces modular arithmetic, a foundation of computational security.

Learning Objectives

By the end of this chapter, a student should be able to:

1. Explain divisibility, prime factorization, and the fundamental theorem of arithmetic.

2. Compute greatest common divisors using the Euclidean algorithm.

3. Express a greatest common divisor as a linear combination using the extended Euclidean algorithm.

4. Work with congruences and solve linear congruences when solutions exist.

5. Apply Fermat’s and Euler’s theorems under their required conditions.

6. Compute modular powers efficiently using repeated squaring.

7. Explain how number theory supports hashing, pseudorandomness, and cryptography.

8. Identify practical limitations, security requirements, and governance concerns in digital systems.

1. Divisibility and Integer Structure

For integers a and b, with a not equal to 0, we say that a divides b, written a | b, if there exists an integer k such that b = ak. The integer a is a divisor or factor of b, and b is a multiple of a. For example, 6 | 42 because 42 = 6(7), whereas 6 does not divide 43.

Important properties include:

• If a | b and a | c, then a | (b + c) and a | (b - c).
• If a | b, then a | bc for every integer c.
• If a | b and b | c, then a | c.

The division algorithm states that for any integer a and any positive integer d, there exist unique integers q and r such that

a = dq + r, where 0 <= r < d.

Here q is the quotient and r is the remainder. For example, 47 = 6(7) + 5. The restriction on the remainder makes the representation unique.

Prime Numbers and Factorization

An integer p greater than 1 is prime if its only positive divisors are 1 and p. An integer greater than 1 that is not prime is composite. The first primes are 2, 3, 5, 7, 11, and 13.

The fundamental theorem of arithmetic states that every integer n greater than 1 has a unique factorization into primes, apart from the order of the factors. Thus,

360 = 2^3 × 3^2 × 5.

This theorem supports efficient reasoning about divisors, greatest common divisors, and least common multiples. If

a = p_1^α1 p_2^α2 ... p_k^αk and b = p_1^β1 p_2^β2 ... p_k^βk,

then

gcd(a,b) = product of p_i raised to min(α_i, β_i),

and

lcm(a,b) = product of p_i raised to max(α_i, β_i).

For positive a and b,

gcd(a,b) lcm(a,b) = ab.

Prime factorization is conceptually important but can be computationally expensive for very large integers. Cryptographic systems exploit this asymmetry: multiplying large primes is easy, while reversing the process by factoring their product can be difficult.

2. Greatest Common Divisors and Euclidean Algorithms

The greatest common divisor of integers a and b, not both zero, is the largest positive integer that divides both. It is written gcd(a,b). For example, gcd(84,30) = 6.

The Euclidean Algorithm

The Euclidean algorithm is based on the identity

gcd(a,b) = gcd(b, a mod b),

when b is nonzero. The identity follows because a = bq + r implies that a and b have exactly the same common divisors as b and r.

Worked Example: gcd(252,105)

252 = 105(2) + 42

105 = 42(2) + 21

42 = 21(2) + 0

Therefore, gcd(252,105) = 21.

A basic pseudocode version is:

```

GCD(a, b):

while b ≠ 0:

(a, b) = (b, a mod b)

return |a|

```

The algorithm is efficient. Its number of divisions grows logarithmically with the size of the input values, so it is practical even for very large integers.

Bézout’s Identity and the Extended Algorithm

For integers a and b, not both zero, there exist integers x and y such that

ax + by = gcd(a,b).

This is Bézout’s identity. The extended Euclidean algorithm computes x and y as well as the gcd.

For 252 and 105, back-substitution gives:

21 = 105 - 2(42)

21 = 105 - 2(252 - 2(105))

21 = 5(105) - 2(252).

Thus, x = -2 and y = 5 satisfy 252(-2) + 105(5) = 21.

Bézout coefficients are particularly important for modular inverses. If gcd(a,m) = 1, then there are integers x and y satisfying ax + my = 1. Reducing this equation modulo m gives ax congruent to 1 modulo m. Therefore x is an inverse of a modulo m.

3. Congruences and Modular Arithmetic

For integers a, b, and positive integer m, we say that a is congruent to b modulo m, written

a ≡ b (mod m),

if m divides a - b. Equivalently, a and b have the same remainder after division by m.

For example,

29 ≡ 5 (mod 12)

because 29 - 5 = 24, which is divisible by 12.

Congruence modulo m is an equivalence relation: it is reflexive, symmetric, and transitive. It partitions the integers into residue classes. Modulo 5, the classes can be represented by 0, 1, 2, 3, and 4. Every integer belongs to exactly one of these classes.

Congruences can be added and multiplied:

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

a + c ≡ b + d (mod m)

and

ac ≡ bd (mod m).

Consequently, polynomial expressions can be reduced modulo m at every step. However, division requires care. From ac ≡ bc (mod m), cancellation of c is valid only when gcd(c,m) = 1. For example, 2(1) ≡ 2(4) (mod 6), but 1 is not congruent to 4 modulo 6. Cancellation fails because gcd(2,6) is 2 rather than 1.

Modular Inverses

An integer a has a multiplicative inverse modulo m if there is an integer a^(-1) such that

aa^(-1) ≡ 1 (mod m).

Such an inverse exists exactly when gcd(a,m) = 1.

#### Worked Example: Inverse of 17 Modulo 43

Using the Euclidean algorithm:

43 = 2(17) + 9

17 = 1(9) + 8

9 = 1(8) + 1.

Back-substitution gives:

1 = 9 - 8 = 9 - (17 - 9) = 2(9) - 17 = 2(43 - 2(17)) - 17 = 2(43) - 5(17).

Therefore, -5(17) ≡ 1 (mod 43), so the inverse of 17 modulo 43 is -5 ≡ 38 (mod 43). Indeed, 17(38) = 646 ≡ 1 (mod 43).

Solving Linear Congruences

Consider

ax ≡ b (mod m).

Let d = gcd(a,m). A solution exists if and only if d divides b. If a solution exists, there are d distinct solutions modulo m.

For example, solve 14x ≡ 8 (mod 30). Since gcd(14,30) = 2 and 2 divides 8, solutions exist. Dividing the congruence by 2 gives

7x ≡ 4 (mod 15).

The inverse of 7 modulo 15 is 13 because 7(13) = 91 ≡ 1 (mod 15). Hence

x ≡ 13(4) ≡ 52 ≡ 7 (mod 15).

The solutions modulo 30 are x ≡ 7 and x ≡ 22.

4. Important Theorems

Fermat’s Little Theorem

If p is prime and p does not divide a, then

a^(p-1) ≡ 1 (mod p).

Equivalently, for every integer a,

a^p ≡ a (mod p).

The first form requires that a not be divisible by p. Fermat’s theorem is useful for reducing exponents and constructing examples of modular inverses. If p does not divide a, then

a^(-1) ≡ a^(p-2) (mod p).

This is not generally valid when the modulus is composite.

Euler’s Theorem

Euler’s theorem generalizes Fermat’s result. If gcd(a,n) = 1, then

a^φ(n) ≡ 1 (mod n),

where φ(n), Euler’s totient function, counts the positive integers up to n that are relatively prime to n.

If p is prime, φ(p) = p - 1. If p and q are distinct primes, φ(pq) = (p - 1)(q - 1). More generally, if

n = product of distinct prime powers p_i^α_i,

then

φ(n) = n product over p_i of (1 - 1/p_i).

The coprimality condition is essential. For example, 2^φ(8) = 2^4 = 16 is not congruent to 1 modulo 8.

Chinese Remainder Theorem

If m and n are coprime, then the simultaneous congruences

x ≡ a (mod m), x ≡ b (mod n)

have exactly one solution modulo mn. This is the Chinese remainder theorem (CRT).

CRT is used to combine computations performed modulo smaller numbers. It is important in cryptographic implementations because computations modulo prime factors can be faster than computation modulo their product. Implementations must, however, protect CRT operations against side-channel and fault-injection attacks.

#### Example

Solve x ≡ 2 (mod 3) and x ≡ 3 (mod 5). Values congruent to 2 modulo 3 are 2, 5, 8, 11, and so on. The value 8 is congruent to 3 modulo 5. Therefore x ≡ 8 (mod 15), and all solutions are x = 8 + 15k.

5. Efficient Modular Exponentiation

Directly computing a^e can be impractical because the intermediate number may contain thousands or millions of digits. Modular exponentiation avoids this problem by reducing after every multiplication.

The repeated-squaring method represents the exponent in binary. For example, 13 = 8 + 4 + 1, so

a^13 = a^8 a^4 a.

Worked Example: Compute 7^13 Modulo 20

7^2 ≡ 49 ≡ 9 (mod 20)

7^4 ≡ 9^2 = 81 ≡ 1 (mod 20)

7^8 ≡ 1^2 ≡ 1 (mod 20)

Thus,

7^13 = 7^8 7^4 7 ≡ 1(1)(7) ≡ 7 (mod 20).

A right-to-left binary algorithm is:

```

ModPower(a, e, m):

result = 1

base = a mod m

while e > 0:

if e is odd:

result = (result * base) mod m

base = (base * base) mod m

e = floor(e / 2)

return result

```

The algorithm requires O(log e) modular multiplications. In real cryptographic software, the implementation must also consider timing, memory access, power consumption, and fault leakage. An mathematically correct algorithm can still be insecure if its execution reveals information about a secret exponent.

6. Applications in Computing and AI Systems

Hashing and Data Structures

A hash function maps data from a large domain to a fixed-size range. Modular arithmetic is often used in simple polynomial rolling hashes. For a sequence of symbols with numerical values s_0, ..., s_{k-1}, a typical rolling expression is

H = (s_0 b^(k-1) + s_1 b^(k-2) + ... + s_{k-1}) mod m,

where b is a chosen base and m is the table size or a large modulus. The modulus keeps values bounded and permits efficient updates. Such hashes are useful for string matching and data indexing, but they are not automatically secure cryptographic hashes. Collision resistance, unpredictability, and resistance to deliberate attacks require stronger constructions such as SHA-256 or SHA-3.

In AI pipelines, hashes can support dataset deduplication, cache keys, model-artifact identification, and integrity checks. A cryptographic hash should be used when an adversary may intentionally modify inputs.

Pseudorandomness

Linear congruential generators use a recurrence such as

X_(t+1) = (aX_t + c) mod m.

They are computationally inexpensive but have predictable structure and should not be used for cryptographic secrets. Their period depends on parameters. For a full period of m, standard conditions include gcd(c,m) = 1, every prime factor of m dividing a - 1, and, if m is divisible by 4, 4 dividing a - 1.

Cryptographic pseudorandom number generators use stronger designs and carefully collected entropy. Randomness is essential for cryptographic keys, nonces, salts, and initialization values. Reusing a nonce or generating predictable keys can completely undermine otherwise sound mathematics.

RSA Public-Key Cryptography

RSA illustrates the relationship among primes, gcds, modular inverses, and exponentiation. In simplified key generation:

1. Choose distinct large primes p and q.

2. Set n = pq and φ(n) = (p - 1)(q - 1).

3. Choose e with 1 < e < φ(n) and gcd(e,φ(n)) = 1.

4. Compute d such that ed ≡ 1 (mod φ(n)).

5. The public key is (n,e); the private key contains d and usually p and q.

Encryption of a suitably encoded message M is C ≡ M^e (mod n), and decryption is M ≡ C^d (mod n), under the mathematical assumptions of the scheme. Modern RSA must use secure padding, such as OAEP for encryption or PSS for signatures. Textbook RSA is deterministic and insecure.

RSA security depends on computational assumptions related to factoring and the RSA problem, not merely on the fact that multiplication is easy. Key generation, random-number quality, padding, implementation security, and key management are equally important.

Diffie–Hellman and Discrete Logarithms

In a cyclic group with generator g and large prime modulus p, two parties may choose secret integers a and b. They publish g^a mod p and g^b mod p. Both can compute the shared value

g^(ab) mod p.

An observer would need to solve a discrete logarithm problem to recover a secret under the classical security model. Practical protocols use authenticated versions to prevent man-in-the-middle attacks and select standardized groups or elliptic-curve groups. Future quantum computers motivate migration toward post-quantum cryptography; Shor’s algorithm threatens RSA and classical Diffie–Hellman, while symmetric cryptography is affected differently.

7. Illustrative Case: Integrity of an AI Model Registry

This fictional case illustrates professional application.

Background

A company operates a central registry containing trained machine-learning models. Several deployment servers download models from the registry. An attacker who replaces a model could cause incorrect predictions, privacy violations, or unsafe automated decisions.

Problem

A simple checksum based on a small modulus detects accidental transmission errors but is easy for an attacker to manipulate. The company needs both integrity verification and trustworthy identification of model artifacts.

Analysis

A cryptographic hash of the model file provides a compact digest. However, a digest alone does not prove who produced the file: an attacker who can replace both the model and its digest may remain undetected. The registry therefore needs authenticated metadata, such as a digital signature. Key generation requires a cryptographically secure random source; signature verification uses modular arithmetic or elliptic-curve operations depending on the selected algorithm.

Approach and Solution

The registry stores the model hash, version, training-data identifier, evaluation metrics, and signer identity. The publisher signs the canonical metadata and hash using an approved digital-signature scheme. Deployment servers verify the signature, recompute the hash, enforce an approved key and algorithm policy, and record the verification event. Private signing keys are held in a hardware-backed key-management service. Key rotation and revocation procedures are documented.

Outcome

Accidental corruption is detected by hash comparison, while unauthorized substitution is rejected by signature verification. Audit records support incident investigation and model rollback.

Learning Points

1. A checksum is not necessarily a cryptographic integrity mechanism.

2. Number-theoretic algorithms operate inside a broader security architecture.

3. Secure key storage, identity management, logging, and revocation are essential.

4. Model integrity does not guarantee model fairness, validity, or safety; those require separate evaluation.

8. Challenges, Limitations, and Best Practices

Number-theoretic security relies on assumptions about computational difficulty. These assumptions can change with algorithmic advances, hardware improvements, or quantum computing. Large key sizes improve resistance but increase computation, storage, and communication costs.

Common implementation failures include incorrect modular reduction, insecure random-number generation, reuse of nonces, inadequate primality testing, failure to validate inputs, and timing side channels. Developers should use reviewed cryptographic libraries rather than implementing RSA, elliptic-curve cryptography, or pseudorandom generators from scratch.

Best practices include:

• Use standardized, current cryptographic algorithms and parameter sizes.
• Distinguish ordinary hashes, message authentication codes, and digital signatures.
• Verify gcd and invertibility conditions before modular division.
• Use constant-time or side-channel-resistant implementations where secrets are involved.
• Protect private keys with hardware-backed or access-controlled storage.
• Plan key rotation, revocation, recovery, and destruction.
• Follow applicable standards, privacy obligations, and sector regulations.
• Treat cryptographic protection as one component of a larger risk-management system.

Ethically, secure systems should protect personal data and prevent unauthorized manipulation without enabling unjustified surveillance. AI model signing and audit trails should support accountability while respecting privacy and access controls. Security decisions must consider affected stakeholders, not only technical performance.

Chapter Summary

Number theory provides the mathematical foundation for many secure digital systems. Divisibility and prime factorization describe the structure of integers. The Euclidean algorithm efficiently computes greatest common divisors, while the extended algorithm produces Bézout coefficients and modular inverses. Congruences describe equality of remainders and support arithmetic in finite residue systems. Linear congruences require careful attention to gcd conditions.

Fermat’s little theorem, Euler’s theorem, and the Chinese remainder theorem enable exponent reduction and efficient computation under stated assumptions. Repeated squaring computes modular powers in logarithmic time. These ideas support hashing, pseudorandom generation, RSA, Diffie–Hellman, digital signatures, and integrity controls for AI artifacts. Correct mathematics is necessary but insufficient: secure randomness, robust implementation, key management, side-channel resistance, governance, and post-quantum planning are also required.

Key Terms

Divisibility: The relation a | b meaning b = ak for some integer k.

Prime number: An integer greater than 1 with exactly two positive divisors.

Composite number: An integer greater than 1 that is not prime.

Fundamental theorem of arithmetic: The theorem that every integer greater than 1 has a unique prime factorization.

Greatest common divisor: The largest positive integer dividing two or more integers.

Euclidean algorithm: An efficient algorithm for computing a gcd using repeated remainders.

Bézout’s identity: The statement that ax + by can equal gcd(a,b) for suitable integers x and y.

Congruence: Equality of integers modulo a specified modulus.

Residue class: The set of integers having the same remainder modulo a modulus.

Modular inverse: A number whose product with another number is congruent to 1.

Euler’s totient function: The number of positive integers up to n that are relatively prime to n.

Fermat’s little theorem: A theorem describing powers modulo a prime.

Chinese remainder theorem: A theorem combining compatible congruences with coprime moduli.

Modular exponentiation: Computation of a^e modulo m without forming the full power.

Hash function: A function mapping arbitrary data to a fixed-size digest or value.

Pseudorandom generator: A deterministic process producing sequences intended to resemble random sequences.

Cryptographic key: Secret or public information controlling a cryptographic operation.

Digital signature: An authenticated cryptographic value used to verify origin and integrity.

Side-channel attack: An attack using indirect information such as timing or power consumption.

Post-quantum cryptography: Cryptography designed to resist attacks from quantum computers.

Review Questions

Short Answer Questions

1. Define a | b using an existential equation.

2. State the condition under which a modular inverse of a modulo m exists.

3. What is the main recurrence used by the Euclidean algorithm?

4. State Fermat’s little theorem in its standard form.

5. Why is textbook RSA insecure even though its modular arithmetic is correct?

Long Answer Questions

1. Explain the Euclidean and extended Euclidean algorithms and illustrate both with a numerical example.

2. Explain congruence classes, modular addition and multiplication, and the limitations on cancellation.

3. Compare Fermat’s little theorem, Euler’s theorem, and the Chinese remainder theorem.

4. Describe repeated-squaring modular exponentiation and analyze its computational efficiency.

5. Explain how number theory contributes to RSA, including key generation and the role of modular inverses.

Analytical / Application Questions

1. Solve 18x ≡ 12 (mod 30), determine whether solutions exist, and list all distinct solutions modulo 30.

2. Design a secure integrity workflow for an AI model registry. Explain why a small-modulus checksum alone is insufficient.

3. A system uses a linear congruential generator for security tokens. Analyze the risks and recommend a more suitable approach, including the role of secure randomness and nonce management.

Multiple Choice Questions with Answers

Question 1

Which condition is necessary and sufficient for a to have a multiplicative inverse modulo m?

A. a is greater than m

B. gcd(a,m) = 1

C. a is prime

D. m is even

Correct Answer: B. gcd(a,m) = 1

Question 2

What is gcd(252,105)?

A. 7

B. 14

C. 21

D. 42

Correct Answer: C. 21

Question 3

Which statement correctly expresses Fermat’s little theorem?

A. For every a and prime p, a^(p-1) ≡ 0 mod p

B. If p is prime and p does not divide a, then a^(p-1) ≡ 1 mod p

C. If a is prime, then a^p ≡ 0 mod p

D. For every composite n, a^n ≡ a mod n

Correct Answer: B. If p is prime and p does not divide a, then a^(p-1) ≡ 1 mod p

Question 4

What is 7^13 modulo 20?

A. 1

B. 7

C. 13

D. 19

Correct Answer: B. 7

Question 5

The congruence ax ≡ b (mod m) has a solution exactly when:

A. a divides m

B. m divides a

C. gcd(a,m) divides b

D. b is prime

Correct Answer: C. gcd(a,m) divides b

Question 6

Which algorithm computes modular powers efficiently in O(log e) multiplications?

A. Bubble sort

B. Repeated squaring

C. Linear search

D. Prime enumeration

Correct Answer: B. Repeated squaring

Question 7

What does the Chinese remainder theorem combine when the moduli are coprime?

A. Prime factorizations only

B. Compatible congruences

C. Hash collisions

D. Random seeds

Correct Answer: B. Compatible congruences

Question 8

For a linear congruential generator X_(t+1) = (aX_t+c) mod m, which property is a known requirement for a full period of m?

A. gcd(c,m) = 1

B. c = 0 always

C. a = m

D. m must be prime

Correct Answer: A. gcd(c,m) = 1

Question 9

Why is a cryptographic hash preferable to a small-modulus checksum for adversarial model-integrity protection?

A. It always produces a unique value

B. It provides stronger resistance to deliberate manipulation

C. It requires no computation

D. It encrypts the model contents

Correct Answer: B. It provides stronger resistance to deliberate manipulation

Question 10

In RSA key generation, why must e be relatively prime to φ(n)?

A. To ensure e has a modular inverse modulo φ(n)

B. To make n equal to e

C. To guarantee that e is even

D. To eliminate the need for prime numbers

Correct Answer: A. To ensure e has a modular inverse modulo φ(n)