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;
Legendre Symbol —
