This section provides a quick summary of the basics of Number Theory.
The following theorems proceed in an orderly way, each depending on the
previous ones for their proofs.
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 —
| 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 |
Quadratic Reciprocity —
| If p,q are odd primes, then |
( |
p
q |
)( |
q
p |
) |
= (-1)(p-1)/2(q-1)/2 |
Jacobi Symbol —
Kronecker Symbol —