Topics for Number Theory (MATH 58)

DETAILED LIST

Divisibility

Definition and basic rules

Partial orderings in general

(a, b) and [a, b]

Linear combinations of a and b are just multiples of (a, b)

The “division algorithm”: b = a q + r with 0 ≤ r < a

The Euclidean algorithm for finding (a ,b)

Floor and ceiling functions

Proof techniques

Axioms for the integers

cancellation laws

ordering axioms

Well-ordering and induction

Some interesting sequences

Arithmetic sequences

Fibonacci sequence

Primes

Definition

Sieve of Eratosthenes

Distribution of primes (first cut)

Twin primes

Primes in arithmetic sequence

Unique factorization (complete proof)

The p-content of a number

The infinity of primes

The infinity of primes of form 4n+3

Dirichlet’s theorem

Binomial coefficients

Factorials, rising powers, falling powers

Congruences

Definition and basic rules

Congruence as an equivalence relation

Integers mod m as an algebraic system

Solving linear congruences

Chinese remainder theorem

Solving systems of congruences

Polynomial congruences

Powers and roots mod m or mod p

The cyclic structure of powers mod p

Primitive roots

Quadratic residues: when is x a square mod m

Special congruences

Fermat’s little theorem

Euler’s theorem about phi(n)

Wilson’s theorem about (p-1)!

The quadratic reciprocity theorem

Legendre symbols

Jacobi symbols

Proof of reciprocity

Solving quadratic equations mod m

Classical problems

Representing integers as sums of squares

Quadratic forms (the 15 theorem)

Pythagorean triples

Perfect numbers

Mersenne primes

Fermat primes

Pell’s equation

Multiplicative functions

The phi function

Sum of divisors

Number of divisors

Mobius inversion

Recognizing primes

Factoring large numbers

Pollard’s rho

Quadratic sieve

Applications (scattered throughout)

Divisibility tricks

Decimal expansions

Check digits and ISBN

RSA encryption

Irrational numbers

Riemann’s zeta function

The prime number theorem