document.write (document.title)

 Math Help > Number Theory > Theorems

This section provides a quick summary of the basics of Number Theory.

Theorems in Number Theory

The following theorems proceed in an orderly way, each depending on the previous ones for their proofs.

Index of theorems

Division — Unique division theorem; prime divisor: If a|b and b|c then a|c; the only positive multiples of a that are divisible by prime p are a·p, a·2p, a·3p, ...; If p|ab then p|a or p|b; Infinitude of primes;

Fundamental Theorem of Arithmetic — Every natural number, n, n>1, can be expressed as the product of primes (called prime factors of n) in the form n = p1 p2 ... pr,  (r ≥ 1), and this expression is unique up to order of factors;

GCD, LCM, B�zout's Identity — definition of GCD; def. of LCM; Linear combination property; Euclidean Algorithm Property a.k.a. B�zout's Identity;

Totient — def. of Totient, a.k.a. phi(n), φ(n); calculating φ(n); The Sum of Totients of Divisors of n is n; If GCD(a,n) = 1 then aφ(n) = 1 (mod n);

Divisors, Tau — def. of divisor function, a.k.a. tau(n), τ(n), which is the number of positive divisors of n; Calculating τ(n); A surprising identity: the sum over k=1 to n of τ(k) is equal to the sum over h=1 to n of [n/h]

M�bius function — def. of μ(n): μ(n)=0 if p2|n, else μ(n)=1 if n has an even number of prime factors; else μ(n)=-1; Sum for all d|n of μ(d) is 0, when n>1; M�bius Inversion Formula: if G(n) is the sum over d|n of F(d), then F(n) is the sum over d|n of μ(n/d) G(d); Application of the M�bius Inversion Formula to show an infinite sequence of functions, the value of each one at n being the sum over d|n of the one before it in one direction, and the value of each one at n being the sum over d|n of μ(n/d) times the one before it in the other direction.  An example of this sequence of functions is M�bius, unit, constant, tau.

Floor function identities — Definition of "floor": [x] ≤ x, and if k is an integer, k ≤ x, then k ≤ [x]; Lemma 1: if y ≤ x then [y] ≤ [x]; Lemma 2: [x]+1 > x; Theorem 1: [x/a] = [[x]/a];

Prime Factorization of n! — Theorem: N =  [n/p] + [n/p2] + [n/p3] + ...;

Euclid's Algorithm — Well-ordering principle; Division algorithm, a.k.a. unique division theorem; Euclid's algorithm; Theorem: m*GCD(a,b) = GCD(ma,mb)

Factorial Divisors — Application of floor function identities and Prime Factorization of n!: Highest power of p that divides n! is N = [n/p] + [n/p2] + [n/p3] + ...;

Congruences — Definitions and fundamental properties of congruences; Residue classes and residue systems; Fermat's Theorem, and the Totient Theorem; Algebraic congruences; Wilson's Theorem and its generalization;

Euler's Criterion — Coprimes of n form a group; Primitive Root; Quadratic Residue; Euler's Criterion is: If p is an odd prime, and a is an integer coprime to p, then a is a quadratic residue (mod p) iff a(p-1)/2 ≡ 1 (mod p); Its corollary for quadratic nonresidue;

 If n is an integer and p is an odd prime, then ( n p ) is { 0 if n≡0 (mod p), 1 if n is a square (mod p), and -1 otherwise
 If p,q are odd primes, then ( p q )( q p ) = (-1)(p-1)/2(q-1)/2

Related pages in this website

The webmaster and author of this Math Help site is Graeme McRae.