Number Systems, Algebra and Number Theory

Introduction

Mathematics for computing begins with the study of numbers, operations, relationships, and structures. Number systems provide the language for representing data; algebra provides methods for describing relationships and solving problems; number theory supplies the foundations of hashing, error detection, coding, authentication, and public-key cryptography.

A computer application may manipulate integers, floating-point approximations, complex values, polynomial expressions, logarithms, and modular residues within the same program. Understanding the mathematical properties of these objects helps a programmer select suitable algorithms, identify invalid assumptions, analyze efficiency, and reason about correctness.

Learning Objectives

After completing this chapter, you should be able to:

• classify real and complex numbers and perform operations on them;
• solve equations, inequalities, polynomial expressions, and logarithmic equations;
• explain divisibility, prime factorization, greatest common divisors, and least common multiples;
• apply the Euclidean algorithm and modular arithmetic;
• solve basic linear congruences;
• explain how number theory supports hashing, coding, and cryptography;
• recognize limitations such as overflow, rounding, collisions, and weak cryptographic parameters.

1. Number Systems

1.1 Classification of numbers

The principal number sets are shown below.

The inclusions are

A decimal that terminates or repeats is rational. For example, 0.125 = 1/8 and 0.333… = 1/3. A nonterminating, nonrepeating decimal is irrational.

1.2 Properties of real-number operations

For real numbers a, b, and c:

• Commutative: a + b = b + a and ab = ba.
• Associative: (a + b) + c = a + (b + c) and (ab)c = a(bc).
• Distributive: a(b + c) = ab + ac.
• Identity: a + 0 = a and a × 1 = a.
• Inverse: a + (−a) = 0; if a ≠ 0, then a × 1/a = 1.

Subtraction and division are derived operations: a − b means a + (−b), while a ÷ b means a × 1/b, provided b ≠ 0. Division by zero is undefined.

1.3 Powers and roots

For a nonzero base a and integers m and n, exponent laws include:

The quotient rule requires a ≠ 0. For positive a, fractional powers are defined by

For even n, a real even root requires a ≥ 0. In computer systems, exponentiation may additionally be limited by finite precision and overflow.

1.4 Complex numbers

The imaginary unit i satisfies i² = −1. A complex number is z = a + bi, where a is the real part and b is the imaginary part. Its conjugate is z̄ = a − bi, and its modulus is

The modulus is the distance from the origin in the complex plane. Complex division is simplified by multiplying numerator and denominator by the conjugate. For example,

Thus the result is −1/2 + 5i/2. Complex numbers are used in signal processing, electrical engineering, graphics, control systems, and the analysis of algorithms involving oscillation.

2. Algebraic Expressions and Equations

An algebraic expression combines variables, constants, and operations. A term such as 4x²y has coefficient 4 and degree 3. Like terms have identical variable parts and can be combined.

2.1 Linear equations

A linear equation in one variable has the form

Its solution is x = (c − b)/a. The restriction a ≠ 0 is essential; if a = 0, the equation either has no solution or infinitely many solutions.

Worked example. Solve 5x − 7 = 18.

5x = 25, so x = 5. Substitution gives 5(5) − 7 = 18, confirming the result.

A pair of linear equations can be solved by substitution, elimination, or matrices. For

adding the equations gives 3x = 8, so x = 8/3. Substitution gives y = 1/3.

2.2 Quadratic equations

A quadratic equation has the form ax² + bx + c = 0, with a ≠ 0. The quadratic formula is

The discriminant Δ = b² − 4ac determines the real roots:

Worked example. For x² − 5x + 6 = 0, factorization gives (x − 2)(x − 3) = 0. Therefore x = 2 or x = 3. The formula gives the same results.

2.3 Inequalities

An inequality compares quantities using <, ≤, >, or ≥. Adding or subtracting the same quantity preserves its direction. Multiplying or dividing by a negative number reverses the direction.

For example, solve −3x + 4 ≥ 10:

−3x ≥ 6. Dividing by −3 reverses the sign, giving x ≤ −2.

Polynomial inequalities are often solved by locating roots and testing intervals. Rational inequalities additionally require that denominator zeros be excluded from the domain.

2.4 Polynomials

A polynomial in x is

where coefficients a_i belong to a chosen number system and a_n ≠ 0. The degree is n. Polynomial operations include addition, multiplication, division, and evaluation.

The remainder theorem states that the remainder when p(x) is divided by x − r is p(r). Consequently, if p(r) = 0, then x − r is a factor. The factor theorem is useful for finding roots and simplifying expressions.

The polynomial x² + 1 has no real roots but has complex roots i and −i. This illustrates that a polynomial’s roots depend on the number system under consideration.

3. Logarithms and Exponentials

For b > 0, b ≠ 1, and x > 0,

The logarithm is the inverse of exponentiation. Important laws are

These laws require positive logarithm arguments. The change-of-base formula is

where ln denotes the natural logarithm, base e.

Worked example. Solve 2^(x+1) = 16. Since 16 = 2⁴, x + 1 = 4 and x = 3. For 5^x = 12, an exact elementary solution is not available; taking logarithms gives x = ln(12)/ln(5) ≈ 1.544.

Logarithms are important in algorithm analysis. Binary search examines approximately log₂ n levels for n ordered items, and logarithmic scales are used for data size, sound intensity, and information measures.

4. Divisibility and Prime Numbers

For integers a and b, a divides b, written a | b, if there is an integer k such that b = ak. If a does not divide b, we write a ∤ b.

Divisibility is transitive: if a | b and b | c, then a | c. If a | b and a | c, then a | (mb + nc) for any integers m and n.

A prime number is an integer greater than 1 with exactly two positive divisors: 1 and itself. Every integer greater than 1 has a unique prime factorization, apart from the order of factors. For example,

This is the Fundamental Theorem of Arithmetic.

A trial-division primality test checks possible divisors up to √n. If n has a factor greater than √n, the paired factor must be less than √n. For large values, probabilistic tests such as Miller–Rabin are preferred because trial division becomes inefficient.

5. Greatest Common Divisors and the Euclidean Algorithm

The greatest common divisor of integers a and b, not both zero, is the largest positive integer dividing both, written gcd(a, b). The least common multiple, lcm(a, b), is the smallest positive integer divisible by both.

For positive a and b,

The identity depends on using positive values for the lcm and gcd.

The Euclidean algorithm uses

when b ≠ 0. The process ends when the remainder is zero.

Worked example. Find gcd(252, 105):

252 = 2(105) + 42

105 = 2(42) + 21

42 = 2(21) + 0

Therefore gcd(252, 105) = 21. Since lcm(252, 105) × 21 = 252 × 105, the lcm is 1260.

The extended Euclidean algorithm also finds integers s and t satisfying

These coefficients are called Bézout coefficients and are central to computing modular inverses.

6. Modular Arithmetic

For integers a, b, and positive modulus n, a is congruent to b modulo n if n divides a − b:

Thus 17 ≡ 5 (mod 12), because 12 divides 12. Congruence is an equivalence relation: it is reflexive, symmetric, and transitive.

Arithmetic can be performed on residues:

This permits calculations with very large integers while retaining only remainders. Exponentiation modulo n is efficiently computed by repeated squaring.

6.1 Modular inverses

An integer a has a multiplicative inverse modulo n if there is an integer x such that

Such an inverse exists exactly when gcd(a, n) = 1. For example, the inverse of 3 modulo 7 is 5 because 3 × 5 = 15 ≡ 1 (mod 7).

6.2 Linear congruences

For ax ≡ b (mod n), a solution exists if and only if gcd(a, n) divides b. If d = gcd(a,n), there are d distinct residue solutions modulo n when a solution exists.

Worked example. Solve 4x ≡ 8 (mod 12). Here gcd(4,12) = 4, and 4 divides 8, so solutions exist. Dividing the congruence by 4 gives x ≡ 2 (mod 3). The solutions modulo 12 are x = 2, 5, 8, and 11.

The Chinese Remainder Theorem states that if moduli n₁, n₂, …, n_k are pairwise coprime, then a system of congruences has a unique solution modulo n₁n₂⋯n_k.

7. Applications in Computing

7.1 Hashing

A hash function maps data to a fixed-size value. A simple integer hash might use

where k is an integer key and m is the table size. If two keys produce the same value, a collision occurs. Collision handling includes chaining and open addressing. A good practical design distributes likely keys uniformly; modulo a poorly chosen table size can create patterns and clustering.

A hash is not automatically a cryptographic hash. Cryptographic hashes require preimage resistance, second-preimage resistance, and collision resistance under defined threat models. MD5 and SHA-1 should not be selected for collision-resistant security applications; modern systems commonly use SHA-256 or SHA-3, subject to current standards and threat analysis.

7.2 Error detection and coding

Parity uses arithmetic modulo 2. A parity bit makes the total number of 1 bits even or odd. It detects any odd number of bit errors but cannot reliably detect every even number of errors.

Checksums and cyclic redundancy checks use polynomial arithmetic over binary coefficients. Error-correcting codes add structured redundancy so that a receiver can detect or correct selected errors. The coding scheme determines its distance and therefore its error-detection and correction capability.

7.3 Cryptography

Many public-key systems rely on the computational difficulty of number-theoretic problems. In RSA, two large primes p and q form n = pq. A simplified key-generation outline is:

1. Select large primes p and q.
2. Compute n = pq and φ(n) = (p − 1)(q − 1).
3. Select e with gcd(e, φ(n)) = 1.
4. Compute d satisfying ed ≡ 1 (mod φ(n)).

The public key is commonly (n, e), while d is private. Textbook RSA is not secure by itself: practical RSA requires standardized randomized padding such as OAEP, appropriate key sizes, secure prime generation, and careful implementation. Modern applications often use elliptic-curve or post-quantum mechanisms rather than designing cryptosystems from scratch.

8. Illustrative Case: A Secure Student-Record Service

Background

A university application stores student identifiers, validates records, and transmits protected data between a web server and a mobile client.

Problem

The initial design uses the student ID directly as a database index, a weak modulo hash table, and an obsolete hash algorithm for passwords. It also performs arithmetic using fixed-width integers without checking overflow.

Analysis

Using an identifier directly can reveal sensitive information and may create predictable access patterns. A simple modulo hash can produce collisions when identifiers share patterns. Passwords should not be stored with a general-purpose hash; they require a password-specific, salted, deliberately expensive function. Integer overflow can corrupt record counts or security limits.

Approach and solution

The redesigned service uses:

• a random internal identifier rather than exposing sequential student IDs;
• a collision-resistant hash only where a hash is appropriate;
• a password-hashing function such as Argon2id with unique salts and a tested configuration;
• validated integer ranges and checked arithmetic;
• authenticated encryption for confidential and tamper-resistant communication;
• access control, logging, key rotation, and security testing.

Modular arithmetic remains relevant in the implementation of cryptographic primitives, but developers use established, peer-reviewed libraries rather than implementing RSA or elliptic-curve arithmetic independently.

Outcome

The design reduces information leakage, improves resistance to offline password attacks, detects invalid inputs, and makes arithmetic failures explicit. It also separates ordinary indexing and hashing from cryptographic protection.

Learning points

1. A mathematical operation is not automatically a secure algorithm.
2. Collision behavior matters in both hash tables and cryptographic hashes.
3. Correctness requires domain restrictions, overflow checks, and validated inputs.
4. Security depends on algorithms, parameters, implementation, and operational governance.

9. Limitations, Governance, and Best Practices

Mathematical models often assume exact arithmetic, whereas computers use finite representations. Floating-point values may introduce rounding error; integer operations may overflow; and language-specific remainder behavior may differ for negative operands. Requirements should define accepted ranges and edge cases.

Cryptographic governance includes approved algorithms, key management, access control, auditability, privacy protection, and compliance with applicable institutional and legal requirements. Never use predictable random numbers for cryptographic keys. Never treat an ordinary checksum as evidence of authenticity. Do not publish sensitive values merely because they are hashed: weak inputs may be guessed.

Best practice is to state domains and assumptions, test boundary cases, use exact integer arithmetic where appropriate, reduce modular values during large calculations, and rely on maintained cryptographic libraries. Mathematical literacy supports responsible engineering, but security assurance also requires threat modeling, review, testing, and monitoring.

Chapter Summary

Number systems progress from natural numbers and integers through rational, real, and complex numbers. Algebra supplies rules for manipulating expressions, solving equations and inequalities, analyzing polynomials, and using logarithms. Divisibility and prime factorization establish the structure of integers. The Euclidean algorithm computes greatest common divisors and, through its extended form, modular inverses. Modular arithmetic permits controlled computation with remainders and forms a foundation for hashing, coding theory, and public-key cryptography.

Computing applications must distinguish mathematical correctness from implementation security. Hash collisions, finite precision, overflow, weak randomness, and inappropriate cryptographic choices can invalidate an otherwise correct formula. Reliable practice combines mathematical reasoning with validated algorithms, secure libraries, explicit assumptions, and governance.

Key Terms

Number system: A set of numbers together with defined operations and properties.

Integer: A positive or negative whole number, including zero.

Rational number: A number expressible as p/q with integers p and q ≠ 0.

Irrational number: A real number that cannot be expressed as a ratio of integers.

Complex number: A number of the form a + bi, where i² = −1.

Modulus: The nonnegative magnitude of a complex number or, in modular arithmetic, the base modulus n.

Polynomial: An expression formed from variables and nonnegative integer powers.

Discriminant: The quantity b² − 4ac in a quadratic equation.

Logarithm: The inverse operation of exponentiation.

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

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

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

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

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

Congruence: Equality of integer remainders modulo a positive integer.

Modular inverse: A value x satisfying ax ≡ 1 (mod n).

Hash collision: An event in which two inputs produce the same hash value.

Parity: The property of being even or odd, often used for error detection.

Cryptographic hash: A hash designed to provide security properties such as collision resistance.

Overflow: A result exceeding the representable range of a numeric data type.

Review Questions

5 Short Answer Questions

1. What distinguishes a rational number from an irrational number?
2. State the condition under which a modular inverse of a modulo n exists.
3. What does the discriminant tell us about a quadratic equation?
4. Define a prime number.
5. Why can a hash table contain collisions?

5 Long Answer Questions

1. Explain the inclusion relationship among ℕ, ℤ, ℚ, ℝ, and ℂ, giving examples.
2. Derive and apply the quadratic formula to a suitable quadratic equation.
3. Explain the Euclidean algorithm and use it to compute gcd(414, 276).
4. Describe modular arithmetic and explain how it supports efficient computation.
5. Compare ordinary hashing, password hashing, and cryptographic hashing.

3 Analytical / Application Questions

1. A system uses h(k) = k mod 10 for identifiers ending in 0 or 5. Analyze the likely distribution and recommend a better design.
2. Solve 6x ≡ 15 (mod 21), justify whether solutions exist, and list the distinct solutions modulo 21.
3. Design a mathematical and engineering checklist for selecting arithmetic and cryptographic operations in a student-record application.

Multiple Choice Questions with Answers

Question 1

Which set contains all integers, rational numbers, irrational numbers, and complex numbers?

A. ℕ

B. ℤ

C. ℝ

D. ℂ

Correct Answer: D. ℂ

Question 2

What is the discriminant of 2x² + 3x − 2 = 0?

A. −7

B. 25

C. 13

D. 9

Correct Answer: B. 25

Question 3

What is gcd(252, 105)?

A. 7

B. 21

C. 42

D. 63

Correct Answer: B. 21

Question 4

Which statement defines a ≡ b (mod n)?

A. n divides a + b

B. a divides b − n

C. n divides a − b

D. a and b are both prime

Correct Answer: C. n divides a − b

Question 5

What is the inverse of 3 modulo 7?

A. 2

B. 3

C. 5

D. 6

Correct Answer: C. 5

Question 6

Which condition is necessary and sufficient for ax ≡ b (mod n) to have a solution?

A. a is prime

B. gcd(a,n) divides b

C. n divides a

D. b is less than n

Correct Answer: B. gcd(a,n) divides b

Question 7

What is 17 mod 12?

A. 3

B. 5

C. 7

D. 12

Correct Answer: B. 5

Question 8

Which property is specifically required of a cryptographic hash but not necessarily of a basic hash-table function?

A. Collision resistance

B. Fast indexing

C. Integer input

D. Fixed table size

Correct Answer: A. Collision resistance

Question 9

What is the prime factorization of 360?

A. 2² × 3² × 10

B. 2³ × 3² × 5

C. 2 × 3 × 5³

D. 2⁴ × 3 × 5

Correct Answer: B. 2³ × 3² × 5

Question 10

Why does division by a negative number reverse an inequality sign?

A. It changes the order of points on the real-number line

B. It always makes the result positive

C. It removes the variable

D. It converts the inequality into an equation

Correct Answer: A. It changes the order of points on the real-number line