Things you should know about the integers:
The Well Ordering Principle:
Every nonempty set of positive integers has a smallest element
The Principle of Mathematical Induction
If S is a set of natural numbers containing 1 which has the property that, for any positive integer k, whenever k is in S then so is k+1, the S = N, the set of all natural numbers.
Equivalently, if P(n) is a statement about a natural numbered parameter n, and if both P(1) is true and whenever P(k) it true then so is P(k+1), then P(n) is true for all natural numbers n.
The Principle of Complete Induction (Strong Induction)
If S is a set of natural numbers which has the property that, for any positive integer m, whenever r is in S for every positive integer r < m then m is in S, then S = N, the set of all natural numbers.
Equivalently, if P(n) is a statement about a natural numbered parameter n, and if P(m) is true whenever P(r) it true for all r < m, then P(n) is true for all natural numbers n.
Induction may start at n0
If S is a set of natural numbers containing n0 which has the property that, for any positive integer k n0, whenever k is in S then so is k+1, then S = {nN | n n0}.
Equivalently, if P(n) is a statement about a natural numbered parameter n, and if both P(n0) is true and whenever P(k) it true for some k n0 then so is P(k+1), then P(n) is true for all natural numbers n n0.
Binomial coefficients (n choose r)
= the number of ways to select r objects from n given distinct objects
Facts about the binomial coefficients:
For any positive integers r n,
1) =
2) ==1
3) == n
4) +=
The Binomial Theorem
For any natural number n, (x+y)n =
Pascal’s Triangle
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
......
......
1 k … k 1
......
The Division Algorithm
For any integers a, b, with b > 0, there exist integers q and r such that
1) a = qb + r
2) 0 r < b
q is called the quotient and r is called the remainder (when a is divided by b)
Greatest common divisor
For any integers a and b, not both zero, there exists a positive integer d such that
1) d is a divisor or both a and b (denoted symbolically by d|a and d|b )
2) For any integer c if c|a and c|b , then c|d .
That is, d is a common divisor of a and b which is divisible by every common divisor
d is called the greatest common divisor of a and b, and is denoted by
d = gcd(a,b) or, more simply, d = (a,b)
Relatively prime
Two integers a and b are said to be relatively prime if (a,b) = 1
gcd as a linear combination
If d = (a,b) then there exist integers r and s such that d = ra + sb.
In fact, (a,b) is the smallest positive number which can be represented in the
form ra + sb. [Note that r and s need not both be positive.]
Euclidian Algorithm
This is a procedure for finding gcd(a,b) as well as for finding r and s as indicated above. See Proposition 0.3.18 for details.
Euclid’s Lemma
If p|bc, where p is prime, then either p|b or p|c (or both)
Fundamental Theorem of Arithmetic
Every positive integer n may be expressed in a unique way in the form
n = p1(r1) p2(r2)… pk(rk), where p1 < p2 < … < pk are primes
and where 0 < ri, for all i = 1, 2, … ,k
[Note: if we allow exponents to be 0, then we can throw in all the primes;
n = 2(r1) 3(r2) 5(r3)…, where 0 < ri, for all i = 1, 2, ….
Least common multiple
The least common multiple of two integers a and b, denoted by lcm(a,b) or <a,b> , is the smallest positive integer m such that a|m and b|m
In fact, if c is a common multiple of a and b (i.e., if a|c and b|c ) then lcm(a,b)|c
That is, the least common multiple is a divisor or every common multiple
How to find the gcd and lcm
If n = 2(r1) 3(r2) 5(r3)… and m = n = 2(s1) 3(s2) 5(s3)… then
gcd(m,n) = 2(t1) 3(t2) 5(t3)…, where ti = min{ ri,, si} for all i = 1, 2, …, and
lcm(m,n) = 2(u1) 3(u2) 5(u3)…, where ui = max{ ri,, si} for all i = 1, 2, ….
Congruence modulo n
Given a positive integer n, we say that two integers a, b are congruent modulo n, written a b (mod n) if n is a divisor of b-a, i.e., if n|(b-a)
Equivalently, a b (mod n) if a and b have the same remainder upon division by n; that is, a = q1n + r and b = q2n + r , where 0 r < n
Congruence modulo n is an equivalence relation
That is,
a a (mod n)
if a b (mod n), then b a (mod n)
and a b (mod n) and b c (mod n), then a c (mod n)
The equivalence classes are called remainder classes. Each equivalence class consists of all numbers having a given remainder modulo n.
For example, modulo 5, [7] = {…,-13,-8,-3,2,7,12,17,22,…} = [2] = [-8] etc.
Properties of congruence
Congruences may be added, subtracted or multiplied (but not divided)
That is, if a b (mod n) and c d (mod n), then a+c b+d (mod n),
a+c b+d (mod n ) and ac bd (mod n).
With regard to division, we have the following:
If ax ay (mod n), then x y (mod n/gcd(a,n) ).
In particular, if a and n are relatively prime and if ax ay (mod n), then
x y (mod n),.
Operations modulo n
We can add and multiply the equivalence classes modulo n.
For example, modulo 5, [3] + [4] = [7] = [2], and [3] [4] = [12] = [2]
To differentiate these operations from ordinary addition and multiplication, we sometimes denote them by and , respectively.
Thus [r] [s] = [r+s] and [r] [s] = [rs]
Zn
With respect to the operations and , {0,1,2,…,n-1} forms an algebraic system which we will denote by Zn, the integers modulo n.
We will often use the symbol Zn, to denote just the additive structure (Zn, ).
Properties of addition and multiplication modulo n
For all [r], [s] [t] in Zn, we have the following:
Commutative laws: [r] [s] = [s] [r];
[r] [s] = [s] [r]
Associative laws: ([r] [s]) [t] = [r] ([s] [t]);
([r] {s]) [t] = [r] ([s] [t])
Distributive law: [r] ([s] [t]) = ([r] [s]) ([r] [t]);
Identity laws: [0] [r] = [r] = [r] [0];
[1] [r] = [r] = [r] [1]
U(n) (units modulo n)
U(n) = { [r] Zn | gcd(r,n) = 1 }
The elements of U(n) are called units modulo n
For all [r] in U(n), there exists [s] in U(n) such that [r] [s] = [1].