Number Theory and Modular Arithmetic

Introduction and Context

Number theory studies the properties of integers. Although many results in number theory were developed as pure mathematics, they now support essential information-technology tasks: hash functions, checksums, error-detecting codes, pseudorandom-number generation, digital signatures, encryption, indexing, and distributed systems.

A central idea is that integers can be analyzed through divisibility and remainders. Modular arithmetic treats numbers as equivalent when they leave the same remainder after division by a chosen modulus. This makes it particularly useful for computer systems, where values are commonly stored in fixed-size fields and where wraparound arithmetic is natural.

This chapter develops the concepts needed to apply number theory responsibly in IT. It distinguishes mathematical properties from engineering guarantees: a checksum can detect many accidental errors but is not automatically secure; a prime modulus can support cryptographic operations but does not by itself make an algorithm secure.

Learning Objectives

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

• apply divisibility rules and the division algorithm;
• identify prime and composite numbers and use prime factorization;
• calculate greatest common divisors and least common multiples using the Euclidean algorithm;
• explain Bézout’s identity and determine modular inverses;
• solve and interpret linear congruences;
• perform modular addition, multiplication, exponentiation, and reduction;
• use modular arithmetic in checksums, hashing, coding, and introductory cryptography;
• evaluate the strengths and limitations of number-theoretic techniques in practical systems.

1. Divisibility and the Division Algorithm

For integers a and b, with b ≠ 0, we say that b divides a, written b ∣ a, if there is an integer k such that

Here a is the dividend, b is the divisor, and k is the quotient. For example, 6 ∣ 42 because 42 = 6 × 7. However, 6 does not divide 43 because 43 ÷ 6 is not an integer.

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

The integer q is the quotient and r is the remainder. The condition 0 ≤ r < n is important because it makes the remainder unique. For example, dividing 47 by 9 gives q = 5 and r = 2, since 47 = 9 × 5 + 2.

Divisibility has several useful properties. If d ∣ a and d ∣ b, then d ∣ (a + b) and d ∣ (a − b). If d ∣ a, then d ∣ ca for every integer c. These properties are useful when simplifying expressions and proving algorithms correct.

Common divisibility tests

For decimal integers, a number is divisible by 2 if its final digit is even; by 5 if its final digit is 0 or 5; and by 10 if its final digit is 0. A number is divisible by 3 or 9 when the sum of its decimal digits is divisible by 3 or 9, respectively. These tests arise from the fact that powers of 10 have simple remainders under these moduli.

For example, 7,245 is divisible by 9 because 7 + 2 + 4 + 5 = 18, and 18 is divisible by 9.

2. 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 number 1 is neither prime nor composite.

The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be written uniquely, apart from the order of factors, as a product of primes. For example,

This factorization is useful for calculating greatest common divisors, least common multiples, and the number of possible divisors.

To test whether an integer n is prime by trial division, it is sufficient to test prime divisors no greater than √n. If n had a factor greater than √n, its paired factor would be less than √n. For large numbers, however, trial division is inefficient. Practical systems use faster primality tests, including probabilistic tests such as Miller–Rabin. A probable-prime result is not the same as an elementary proof of primality, although appropriately configured tests are widely used in cryptographic software.

3. Greatest Common Divisors and Least Common Multiples

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,

The least common multiple, lcm(a, b), is the smallest positive integer divisible by both a and b. For positive integers a and b,

Thus lcm(18, 30) = (18 × 30) ÷ 6 = 90. The identity assumes positive values when lcm is interpreted as positive; gcd is conventionally nonnegative.

The Euclidean algorithm

The Euclidean algorithm calculates gcd efficiently by repeatedly replacing a pair with the divisor and the remainder:

This applies for integers a and b with b ≠ 0. The process stops when the remainder is zero; the last nonzero remainder is the gcd.

For gcd(252, 105):

• 252 = 2 × 105 + 42
• 105 = 2 × 42 + 21
• 42 = 2 × 21 + 0

Therefore, gcd(252, 105) = 21. The algorithm is efficient because the remainder decreases at every step. Its running time grows approximately logarithmically with the size of the inputs, making it suitable for very large integers.

Bézout’s identity

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

The extended Euclidean algorithm finds x and y. These coefficients are important because they can produce modular inverses and support cryptographic key generation.

Using the previous calculation:

• 21 = 105 − 2 × 42
• 42 = 252 − 2 × 105

Substitution gives 21 = 5 × 105 − 2 × 252. Thus x = −2 and y = 5 satisfy 252x + 105y = 21.

4. Congruence and Modular Arithmetic

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

if n divides a − b. Equivalently, a and b have the same remainder when divided by n.

For example,

because 29 − 5 = 24, which is divisible by 12. The notation does not mean that 29 and 5 are equal as ordinary integers; it means that they belong to the same equivalence class modulo 12.

The residue classes modulo n are represented by 0, 1, 2, …, n − 1. Every integer has exactly one standard residue in this range. For instance, the standard residue of −4 modulo 7 is 3, because −4 = 7(−1) + 3.

Congruence is compatible with addition, subtraction, and multiplication. If a ≡ b (mod n) and c ≡ d (mod n), then

Consequently, polynomial expressions can be reduced modulo n during calculation. This prevents intermediate values from becoming unnecessarily large.

Modular exponentiation

To compute a^e mod n, one may repeatedly square and reduce. This is called repeated squaring or binary exponentiation. It reduces the number of multiplications from roughly e to roughly log₂e.

Calculate 3^13 mod 7:

• 3² ≡ 2 (mod 7)
• 3⁴ ≡ 2² ≡ 4 (mod 7)
• 3⁸ ≡ 4² ≡ 2 (mod 7)
• 3¹³ = 3⁸ × 3⁴ × 3, so 3¹³ ≡ 2 × 4 × 3 = 24 ≡ 3 (mod 7).

Thus 3¹³ mod 7 = 3. Modular exponentiation is a basic operation in public-key cryptography.

5. Modular Inverses and Linear Congruences

A modular inverse of a modulo n is an integer a⁻¹ satisfying

An inverse exists if and only if gcd(a, n) = 1. This condition is essential: division modulo n is defined as multiplication by an inverse only when the inverse exists.

For example, the inverse of 7 modulo 26 is 15 because 7 × 15 = 105 and 105 ≡ 1 (mod 26). Using Bézout’s identity, 7 × 15 + 26 × (−4) = 1.

A linear congruence has the form

Let d = gcd(a, n). A solution exists if and only if d ∣ b. When solutions exist, there are d distinct solutions modulo n. If d = 1, multiply both sides by a⁻¹ to obtain

Example: solve 7x ≡ 5 (mod 26). Since gcd(7, 26) = 1 and 7⁻¹ ≡ 15 (mod 26),

x ≡ 15 × 5 = 75 ≡ 23 (mod 26).

Therefore, all solutions are x ≡ 23 (mod 26).

As a contrasting example, 6x ≡ 4 (mod 8) has d = gcd(6, 8) = 2, and 2 divides 4, so solutions exist. Dividing the congruence by 2 gives 3x ≡ 2 (mod 4). Since 3⁻¹ ≡ 3 (mod 4), x ≡ 6 ≡ 2 (mod 4). Thus the two solutions modulo 8 are x ≡ 2 and x ≡ 6.

Chinese Remainder Theorem

If moduli n₁ and n₂ are relatively prime, meaning gcd(n₁, n₂) = 1, then the simultaneous congruences

have exactly one solution modulo n₁n₂. More generally, the theorem combines a system of congruences whose moduli are pairwise relatively prime. It is used in scheduling, numerical algorithms, computer arithmetic, and cryptographic implementations.

Example: solve x ≡ 2 (mod 3) and x ≡ 3 (mod 5). Numbers congruent to 2 modulo 3 are 2, 5, 8, 11, …. Among these, 8 is congruent to 3 modulo 5. Hence x ≡ 8 (mod 15).

6. Applications in Information Technology

6.1 Checksums

A checksum maps data to a smaller value used to detect accidental corruption. A simple additive checksum for symbols represented by integers v₁, …, v_k is

where m is the modulus and C is normally stored as a residue from 0 through m − 1. The receiver recomputes C and compares it with the transmitted checksum.

For values 12, 8, 19, and 7 with m = 10, C ≡ 12 + 8 + 19 + 7 = 46 ≡ 6 (mod 10). Such a checksum detects many changes, but not all. For example, exchanging two values leaves their sum unchanged, and different data sets can have the same residue. A checksum is therefore an error-detection mechanism, not a proof of integrity against an intentional attacker.

Weighted checksums improve detection by assigning different weights:

where wᵢ are predetermined weights. The design of weights determines which error patterns are detected.

6.2 Hashing and table indexing

A hash function maps a key to a fixed range of positions. A simple integer hash for a table of size m is

where k is a nonnegative integer key. If m = 13 and k = 428, then h(k) = 428 mod 13 = युद्ध?

Let's calculate correctly: 13 × 32 = 416, so h(k) = 12. In software, negative keys require an explicit policy because some programming languages return a negative remainder. A common normalized form is ((k mod m) + m) mod m.

The choice of table size affects collisions. If keys have patterns, a prime table size can sometimes distribute them better than a highly composite size, but no modulus guarantees uniform distribution. Modern hash tables often use carefully designed hash functions, resizing, and collision-resolution methods such as chaining or open addressing.

Cryptographic hash functions have stronger requirements: one-wayness, resistance to collision finding, and sensitivity to small input changes. A simple remainder function is not a cryptographic hash.

6.3 Error-detecting and error-correcting codes

Modular arithmetic supports parity checks and more advanced codes. In a simple parity scheme, a parity bit is selected so that the total number of 1 bits is even or odd. More sophisticated cyclic redundancy checks treat a bit string as a polynomial over a finite field and perform division using modulo-2 arithmetic, where addition is XOR. The remainder becomes the check value.

Checks and codes must be evaluated against specified error models. A code designed to detect single-bit errors may not detect every burst or multiple-bit error. Engineering documentation should state the guaranteed detection and correction properties rather than claiming general reliability.

6.4 Introductory cryptography

The RSA idea illustrates the role of primes, gcds, modular inverses, and exponentiation. In a simplified key-generation outline:

1. Choose distinct large primes p and q.
2. Compute n = pq.
3. Compute φ(n) = (p − 1)(q − 1), for distinct primes p and q.
4. Choose e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1.
5. Compute d satisfying ed ≡ 1 (mod φ(n)).

The public key is commonly (n, e), and the private exponent is d. A simplified encryption operation is c ≡ m^e (mod n), and decryption is m ≡ c^d (mod n), under appropriate mathematical conditions and with secure padding in a real implementation.

The arithmetic alone is not sufficient for security. Real RSA requires large, randomly generated primes, approved padding schemes, secure random-number generation, side-channel protections, key management, and current standards. Textbook RSA applied directly to structured messages is insecure. Modern systems often use hybrid encryption: public-key cryptography establishes a session key, while a symmetric authenticated cipher protects the data.

7. Detailed Applied Case: File-Transfer Integrity

Background

Consider an illustrative university file-transfer service that sends batches of sensor readings from laboratory computers to a central server. The service initially appends a decimal additive checksum modulo 10 to every batch.

Problem

A batch contains the values 12, 8, 19, and 7. The checksum is 6. During transmission, the values 12 and 22 replace 12 and 2 in another possible batch, while the total remains unchanged. The server accepts the altered batch because the checksum is identical. An intentional attacker could exploit this weakness even more easily.

Analysis

The checksum verifies only the residue of the sum. It does not preserve order, does not identify which value changed, and has only ten possible outputs. Its collision probability for random independent inputs is roughly 1/10, although actual distributions may make collisions more or less likely. It should not be described as authentication.

Approach and solution

The service should use layered controls:

• retain a checksum or error-detecting code for rapid accidental-corruption detection;
• replace the weak checksum for security purposes with a standardized message authentication code, such as HMAC, when a shared secret is available;
• use authenticated encryption when confidentiality and integrity are both required;
• include sequence numbers or nonces to detect replay and reordering;
• validate lengths, ranges, and message structure before processing;
• log failures without exposing secret keys or sensitive readings.

A weighted checksum could improve accidental-error detection, but it would still not resist a knowledgeable attacker who can construct a compensating change. Cryptographic authentication is needed for adversarial integrity.

Outcome

The revised design separates three objectives: checksums provide inexpensive error screening, authenticated cryptography provides origin authentication and tamper detection, and sequence controls provide freshness and ordering. This separation makes the system easier to test and govern.

Learning points

1. A small modular value is not a unique representation of data.
2. Collision resistance and authentication are different requirements.
3. Mathematical correctness must be combined with secure implementation and operational controls.
4. Security claims should be stated against a defined threat model.

8. Implementation Practices and Limitations

When implementing modular arithmetic, use integer types large enough for intermediate products or use a safe modular-multiplication method. In fixed-width arithmetic, overflow can occur before the modulus is applied. Normalize negative residues consistently. Test boundary cases such as zero, one, negative inputs, modulus one, and non-coprime values.

For cryptographic applications, do not design a new cipher, hash function, or random-number generator merely from elementary modular formulas. Use reviewed libraries and current standards. Protect private keys, use constant-time operations where relevant, and obtain independent security review.

Number-theoretic algorithms also have limitations. Factoring large integers may be computationally difficult for classical computers, but security assumptions can change with algorithmic advances and quantum computing. Shor’s algorithm, in principle, threatens RSA and other systems based on factoring or discrete logarithms on a sufficiently capable fault-tolerant quantum computer. This motivates post-quantum cryptography, whose security relies on different mathematical problems. Transition planning is a governance issue as well as a technical issue because encrypted data may need protection for many years.

Chapter Summary

Divisibility describes exact integer factors, while the division algorithm expresses every integer as a quotient and a bounded remainder. Prime factorization provides the basic structure of positive integers. The gcd and lcm summarize common divisors and multiples, and the Euclidean algorithm computes the gcd efficiently. Bézout’s identity connects gcd computation with modular inverses.

Congruence modulo n groups integers according to their remainders. Addition, subtraction, multiplication, and exponentiation can be performed while reducing intermediate results. A modular inverse exists exactly when the relevant number is relatively prime to the modulus. Linear congruences require careful attention to the gcd condition, and the Chinese Remainder Theorem combines compatible congruences with coprime moduli.

In IT, modular arithmetic supports checksums, hash-table indexing, error-detecting codes, and public-key cryptography. Applications must be judged against their objectives: simple checksums detect some accidental errors, whereas cryptographic authentication addresses intentional tampering. Secure systems require sound mathematics, tested algorithms, careful implementation, threat modeling, and responsible governance.

Key Terms

Divisibility: The relation b ∣ a meaning a = bk for some integer k.

Division algorithm: The representation a = nq + r with 0 ≤ r < n.

Remainder: The bounded value left after integer division.

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

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

Prime factorization: Expression of an integer as a product of primes.

Greatest common divisor: The largest positive common divisor of two integers.

Least common multiple: The smallest positive integer divisible by two given positive integers.

Euclidean algorithm: An efficient repeated-remainder method for computing a gcd.

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

Congruence: Equality of remainders modulo a specified positive integer.

Modulus: The positive integer that defines a modular system.

Residue: A representative of a congruence class.

Modular inverse: A value that multiplies a number to give 1 modulo n.

Linear congruence: A congruence of the form ax ≡ b (mod n).

Chinese Remainder Theorem: A theorem combining congruences with pairwise coprime moduli.

Checksum: A compact value used primarily to detect data errors.

Hash function: A function mapping inputs to values in a fixed range.

Collision: Two distinct inputs producing the same output value.

Message authentication code: A keyed construction used to verify message integrity and authenticity.

Review Questions

Short Answer Questions

1. State the division algorithm and explain the restrictions on the remainder.
2. What condition must hold for a modular inverse of a modulo n to exist?
3. Use the Euclidean algorithm to calculate gcd(84, 30).
4. Distinguish a checksum from a cryptographic message authentication code.
5. What does a ≡ b (mod n) mean in terms of divisibility?

Long Answer Questions

1. Explain prime factorization, gcd, lcm, and their relationship. Include a worked numerical example.
2. Describe the Euclidean and extended Euclidean algorithms and explain why they matter in cryptography.
3. Explain how linear congruences are solved when gcd(a, n) equals 1 and when it is greater than 1.
4. Compare simple hash-table indexing, checksums, and cryptographic hash functions in terms of purpose and security.
5. Explain the RSA key-generation outline and identify the mathematical and engineering assumptions required for secure use.

Analytical / Application Questions

1. A data packet contains values 17, 24, 9, and 16. Compute its additive checksum modulo 11. Explain one type of alteration that this checksum may fail to detect.
2. Solve the system x ≡ 4 (mod 7) and x ≡ 1 (mod 5), giving the least nonnegative solution and the combined modulus.
3. A developer proposes using key mod 10 as a secure password hash. Analyze the proposal, identifying its functional use, security weaknesses, and a more appropriate design.

Multiple Choice Questions with Answers

Question 1

Which statement correctly defines a ≡ b (mod n), where n is positive?

A. a and b are equal as ordinary integers

B. n divides a − b

C. a divides b

D. a + b is divisible by n

Correct Answer: B. n divides a − b

Question 2

What is gcd(252, 105)?

A. 7

B. 14

C. 21

D. 42

Correct Answer: C. 21

Question 3

Which number is the modular inverse of 7 modulo 26?

A. 9

B. 13

C. 15

D. 21

Correct Answer: C. 15

Question 4

What is 3^13 mod 7?

A. 1

B. 2

C. 3

D. 6

Correct Answer: C. 3

Question 5

A modular inverse of a modulo n exists exactly when:

A. a is prime

B. n is even

C. gcd(a, n) = 1

D. a is greater than n

Correct Answer: C. gcd(a, n) = 1

Question 6

What is the standard residue of −4 modulo 7?

A. −4

B. 2

C. 3

D. 4

Correct Answer: C. 3

Question 7

What checksum results from values 12, 8, 19, and 7 modulo 10?

A. 4

B. 5

C. 6

D. 7

Correct Answer: C. 6

Question 8

For a hash table using h(k) = k mod 13, what is h(428)?

A. 10

B. 11

C. 12

D. 13

Correct Answer: C. 12

Question 9

The congruence 6x ≡ 4 (mod 8) has which solutions modulo 8?

A. x ≡ 1 and 5

B. x ≡ 2 and 6

C. x ≡ 3 and 7

D. Only x ≡ 4

Correct Answer: B. x ≡ 2 and 6

Question 10

Which statement about a simple additive checksum is correct?

A. It guarantees authentication against attackers

B. It always uniquely identifies the original data

C. It can detect some accidental errors but may have collisions

D. It requires two large prime numbers

Correct Answer: C. It can detect some accidental errors but may have collisions