Unit 2: Number Theory-II

MTH381 — Number Theory And Cryptography 4 min read

Number theory in this unit is built on divisibility over the integers: for integers $a$ and $b$ with $a \neq 0$ , $a \mid b$ (" $a$ divides $b$ ") means $b = ak$ for some integer $k$ . Every result below—factorisation, prime detection, greatest common divisors—rests on this single relation and on the ordering of the positive integers.

Universe of discourse: the positive integers $\mathbb{Z}^+$ and, for gcd/lcm, the integers $\mathbb{Z}$ .
Divisor: $a \mid b$ iff $b/a$ is an integer; if $a \nmid b$ there is a nonzero remainder.
Division algorithm (foundational): for any integer $a$ and positive integer $d$ , there are unique integers $q$ (quotient) and $r$ (remainder) with $a = dq + r$ and $0 \le r < d$ .
Trivial divisors: every $n > 1$ has $1$ and $n$ as divisors; the theory classifies numbers by whether these are the only divisors.
Cryptographic stake: the practical hardness of factoring large integers, but the ease of multiplying primes, underlies public-key schemes such as RSA.

II. Primes and the Fundamental Theorem of Arithmetic

The atoms of multiplication and the uniqueness of their combination.

An integer's multiplicative structure is completely described by its prime constituents; this section defines those atoms and states the law that fixes them uniquely.

A. Primes

A prime is a building block that resists further multiplicative decomposition.

Definition: an integer $p > 1$ is prime if its only positive divisors are $1$ and $p$ ; e.g. $2, 3, 5, 7, 11, 13$ .
Composite: an integer $n > 1$ that is not prime, so $n = ab$ with $1 < a, b < n$ ; e.g. $12 = 3 \times 4$ .
Unit exclusion: $1$ is neither prime nor composite, so that factorisation is unique (allowing $1$ would let $6 = 2\cdot3 = 1\cdot2\cdot3$ ).
Only even prime: $2$ is prime; every other even number has $2$ as a proper divisor.
Infinitude (Euclid): primes never run out. Suppose $p_1,\dots,p_k$ were all of them; then $N = p_1p_2\cdots p_k + 1$ leaves remainder $1$ on division by each $p_i$ , so it has a prime factor outside the list—contradiction.

B. The fundamental theorem of arithmetic

Every integer above $1$ factors into primes in essentially one way.

Statement: every integer $n > 1$ can be written as a product of primes, and this factorisation is unique up to the order of the factors.
Canonical form:

TEXT

n = p1^a1 · p2^a2 · ... · pk^ak,   p1 < p2 < ... < pk

where each $p_i$ is prime and each exponent $a_i \ge 1$ .

Worked example: $600 = 2^3 \cdot 3 \cdot 5^2$ ; no other set of primes with exponents produces $600$ .
Existence: proved by strong induction—if $n$ is prime, done; if composite, $n = ab$ with smaller factors, each already a product of primes.
Uniqueness: relies on Euclid's lemma—if $p \mid ab$ then $p \mid a$ or $p \mid b$ .
Consequence for divisors and gcd: exponents in the factorisation drive every later computation; e.g. the number of positive divisors of $n$ is $(a_1+1)(a_2+1)\cdots(a_k+1)$ .

III. Locating Primes: Testing, Sieving, and Counting

Deciding primality, listing primes in bulk, and estimating how many there are.

Given the atoms of Section II, three procedures answer three distinct questions: is one number prime, which numbers up to a bound are prime, and roughly how dense are primes overall.

A. Trial division

Trial division tests a single integer for primality by attempting divisors directly.

Method: to test $n$ , divide by successive integers $d = 2, 3, 4, \dots$ ; if any $d$ divides $n$ evenly, $n$ is composite, else prime.
$\sqrt{n}$ bound: you need only test $d \le \sqrt{n}$ , because if $n = ab$ then the smaller factor is at most $\sqrt{n}$ .
Prime-only optimisation: it suffices to trial-divide by primes up to $\sqrt{n}$ .
Worked example: test $n = 97$ . $\sqrt{97} \approx 9.8$ , so try primes $2,3,5,7$ : none divides $97$ , so $97$ is prime.
Limitation: running time grows like $\sqrt{n}$ , roughly $10^{d/2}$ operations for a $d$ -digit number, so it is hopeless for the large integers used in cryptography.

B. The sieve of Eratosthenes

The sieve generates all primes up to a limit by repeatedly eliminating multiples.

Principle: every composite $\le N$ has a prime factor $\le \sqrt{N}$ ; strike out those multiples and the survivors are prime.
Procedure:

TEXT

list integers 2 .. N
p := 2
while p*p <= N:
    mark 2p, 3p, 4p, ... <= N as composite
    p := next unmarked number
unmarked numbers = primes

Start-at- $p^2$ optimisation: smaller multiples of $p$ (such as $2p, 3p$ ) are already struck by earlier primes, so crossing out may begin at $p^2$ .
Worked example (N = 30): cross multiples of $2$ , then $3$ , then $5$ (since $7^2 = 49 > 30$ , stop). Survivors: $2,3,5,7,11,13,17,19,23,29$ .
Efficiency: produces all primes below $N$ in about $N \log\log N$ operations—far cheaper per prime than trial-dividing each one separately.

C. The prime number theorem

The prime number theorem estimates how the primes thin out among large integers.

Notation: let $\pi(x)$ denote the number of primes $\le x$ ; e.g. $\pi(10) = 4$ (namely $2,3,5,7$ ).
Statement:

TEXT

π(x) ~ x / ln x     as x → ∞

meaning the ratio $\pi(x)\big/\!\big(x/\ln x\big) \to 1$ .

Density reading: near a large $x$ , roughly $1$ in every $\ln x$ integers is prime; primes get sparser but never stop.
Numeric check: for $x = 10^9$ , $x/\ln x \approx 4.83 \times 10^7$ , while the true $\pi(x) \approx 5.08 \times 10^7$ —close, and the fit improves for larger $x$ .
Refined estimate: the logarithmic integral $\mathrm{li}(x) = \int_2^x dt/\ln t$ approximates $\pi(x)$ even more accurately.
Significance: it guarantees a plentiful supply of large primes, so random search with a primality test reliably finds the primes cryptography needs.

IV. Greatest Common Divisors and Least Common Multiples

Shared and combined structure of two integers, and how to compute it.

Where Section II factored a single integer, this section relates a pair of integers through the divisors they share and the multiples they have in common.

A. Greatest common divisors and least common multiples

These two quantities capture the largest shared divisor and the smallest shared multiple.

gcd definition: $\gcd(a,b)$ is the largest positive integer dividing both $a$ and $b$ ; e.g. $\gcd(24,36) = 12$ .
lcm definition: $\operatorname{lcm}(a,b)$ is the smallest positive integer that both $a$ and $b$ divide; e.g. $\operatorname{lcm}(4,6) = 12$ .
Via factorisation: with $a = \prod p_i^{a_i}$ and $b = \prod p_i^{b_i}$ ,

TEXT

gcd(a,b) = ∏ p_i^{min(a_i, b_i)}
lcm(a,b) = ∏ p_i^{max(a_i, b_i)}

Product identity: $\gcd(a,b)\cdot\operatorname{lcm}(a,b) = ab$ , since $\min(a_i,b_i)+\max(a_i,b_i) = a_i + b_i$ .
Coprimality: $a$ and $b$ are relatively prime when $\gcd(a,b) = 1$ ; e.g. $\gcd(9,16) = 1$ .

B. The Euclidean algorithm

The Euclidean algorithm computes $\gcd(a,b)$ by repeated division, without any factorisation.

Key fact: $\gcd(a,b) = \gcd(b, r)$ where $r = a \bmod b$ , because any common divisor of $a,b$ also divides $r = a - qb$ .
Procedure:

TEXT

while b ≠ 0:
    r := a mod b
    a := b
    b := r
return a          # gcd

Worked example: $\gcd(252, 198)$ : $252 = 1\cdot198 + 54$ ; $198 = 3\cdot54 + 36$ ; $54 = 1\cdot36 + 18$ ; $36 = 2\cdot18 + 0$ . Last nonzero remainder $= 18$ .
Efficiency: the number of divisions is $O(\log(\min(a,b)))$ —worst case arises with consecutive Fibonacci numbers—making it vastly faster than factoring large numbers.

C. Greatest common divisors as linear combinations

The gcd can be expressed as an integer combination of the two inputs, a fact known as Bézout's identity.

Statement (Bézout): there exist integers $s$ and $t$ with

TEXT

gcd(a,b) = s·a + t·b

Extended Euclidean algorithm: run the divisions above, then back-substitute each remainder to write the gcd in terms of $a$ and $b$ ; the coefficients $s,t$ are called Bézout coefficients.
Worked example (continuing $\gcd(252,198)=18$ ):
- From $54 = 1\cdot36 + 18$ : $18 = 54 - 1\cdot36$ .
- Substitute $36 = 198 - 3\cdot54$ : $18 = 54 - (198 - 3\cdot54) = 4\cdot54 - 198$ .
- Substitute $54 = 252 - 198$ : $18 = 4\cdot252 - 5\cdot198$ . So $s = 4$ , $t = -5$ .
Uses:
- Modular inverses: if $\gcd(a,m) = 1$ then $sa \equiv 1 \pmod m$ , so $s$ is the inverse of $a$ modulo $m$ —the core computation for RSA key generation.
- Linear Diophantine equations: $ax + by = c$ has integer solutions iff $\gcd(a,b) \mid c$ , and Bézout supplies one.

Unit 2: Number Theory-II

Table of Contents

II. Primes and the Fundamental Theorem of Arithmetic

A. Primes

B. The fundamental theorem of arithmetic

III. Locating Primes: Testing, Sieving, and Counting

A. Trial division

B. The sieve of Eratosthenes

C. The prime number theorem

IV. Greatest Common Divisors and Least Common Multiples

A. Greatest common divisors and least common multiples

B. The Euclidean algorithm

C. Greatest common divisors as linear combinations

Did this save you a night before the exam?