Induction. Three different equivalent versions:
(b) if P(n-1) is true, then P(n) is true,
(b) if P(k) is true for every n0 £ k < n, then P(n) is true,
An integer p is prime if whenever p = ab with a,b Î \Bbb Z, either a = ±n or b = ±n .
[For sanity's sake, we will take the position that primes should also be ³ 2 .]
There are infinitely many distinct primes.
Every integer n ³ 2 can be expressed as a product of primes; n = p1·¼·pk .
If we insist that the primes are written in increasing order, p1 £ ¼ £ pk, then this representation is unique.
Exponential notation: any n ³ 2 can be uniquely expressed as n = p1a1·¼·prar with ai ³ 1 for each i and p1 < ¼ < pr .
The Division Algorithm: For any integers n ³ 0 and m > 0, there are unique integers q and r with n = mq+r and 0 £ r £ m-1 .
[Note: this is also true for any integers n,m with m ¹ 0, although you need to replace ``m-1'' with ``|m-1|'' .]
The basic idea: keep repeatedly subtracting m from n until what's left is less than m.
Notation: b|a = ``b divides a'' = ``b is a divisor of a'' = ``a is a multiple of b'', means a = bk for some integer k .
If b|a and a ¹ 0, then |b| £ |a| .
If a|b and b|c, then a|c
If a|c and b|d, then ab|cd
If p is prime and p|ab, then either p|a or p|b
Notation: (a,b) = gcd(a,b) = greatest common divisor of a and b
Different, equivalent, formulations for d = (a,b) :
(1) d|a and d|b, and if c|a and c|b, then c £ d .
(2) d is the smallest positive number that can be written as d = ax+by with a,b Î \Bbb Z .
(3) d|a and d|b, and if c|a and c|b, then c|d .
(4) d is the only divisor of a and b that can be expressed as d = ax+by with a,b Î \Bbb Z .
If c|a and c|b, then c|(a,b)
If c|ab and (c,a) = 1, then c|b
If a|c and b|c, and (a,b) = 1, then ab|c
If a = bq+r, then (a,b) = (b,r)
Euclidean Algorithm: This last fact gives us a way to compute (a,b), using the division algorithm:
Starting with a > b, compute a = bq1+r1, so (a,b) = (b,r1). Then compute b = r1q2+r2, and repeat: ri-1 = riqi+1 +ri+1 . Continue until rn+1 = 0, then (a,b) = (b,r1) = (r1,r2) = ¼ = (rn,rn+1) = (rn,0) = rn .
Since b > r1 > r2 > r3 > ¼ , this process must end, by well-orderedrness.
We can reverse these calculations to recover (a,b) = ax+by, by rewriting each equation in our algorithm as ri+1 = ri-1-riqi+1, and then repeatedly substituting the higher equations into the lowest one, in turn, working up through the list of equations.
Primality Testing:
If n ³ 2 is not prime, then it has a prime factor p £ Ön. So to test if a number n is prime, `just' check to see if p|n for any prime p £ Ön.
The Sieve of Eratosthenes: To find all primes between 2 and n, first make a list, then repeat the following procedure: circle the smallest number p not already either circled or crossed off, then cross off all other multiples of p. Continue until the number you are about to circle is larger than Ön . Then every number either circled or not crossed off is prime, while every number crossed off is not prime.
Congruence modulo n : Notation: a º b (mod n) (also written a\medspace \underset n® º \medspaceb) means n|(b-a)
Equivalently: the division algorithm will give the same remainder for a and b when you divide by n
Congruence mod n is an equivalence relation, which means
(Reflexive) a\medspace \underset n® º \medspacea for every a Î \Bbb Z
(Symmetric) If a\medspace \underset n® º \medspaceb , then b\medspace \underset n® º \medspacea
(Transitive) If a\medspace \underset n® º \medspaceb and b\medspace \underset n® º \medspacec , then a\medspace \underset n® º \medspacec
If a = b , then a\medspace \underset n® º \medspaceb for any n Î \Bbb Z
If a\medspace \underset n® º \medspaceb and k Î \Bbb Z, then ka\medspace \underset n® º \medspacekb
If a\medspace \underset n® º \medspaceb and m|n , then a\medspace \underset m® º \medspaceb
(*) If a\medspace \underset n® º \medspaceb and c\medspace \underset n® º \medspaced, then a+c\medspace \underset n® º \medspaceb+d and ac\medspace \underset n® º \medspacebd
The congruence class of a mod n is the collection of all integers congruent mod n to a:
[a]n = {b Î \Bbb Z : a\medspace \underset n® º \medspaceb} = {b Î \Bbb Z : n|(b-a)}
Because \medspace \underset n® º \medspace is an equivalnce relation, these sets are either disjoint or equal. And because every integer is congruent mod n to its remainder on division by n, there are exactly n congruence classes mod n, which can be represented as [0]n , [1]n , ¼, [n-1]n . The set of these n equivalence classes is denoted \Bbb Z/n\Bbb Z or \Bbb Zn, and is called the integers mod n
(*) tells us that it makes sense to add and multiply congruence classes:
[a]n + [b]n = [a+b]n , [a]n·[b]n = [ab]n
These facts can be used to carry out some otherwise fairly difficult calculations very quickly:
To compute [am]n, we note that [am]n = [a]mn , so we first write a = nq+r, so [am]n = [a]mn = [r]mn . Then we look at the list [r]1n,[r]2n,[r]3n,[r]4n,¼ , and continue until the power equals [0]n,[1]n or it repeates itself. All of these can be used to reduce m. For example,
[1071015]7 : [107]7 = [7·15 + 2]7 = [2]7, and [2]37 = [8]7 = [1]7, so since 1015 = 3·338 + 1, we have [1071015]7 = [2]10157 = [2]3·338+17 = ([2]37)338·[2]17 = [1]3387·[2]7 = [2]7 .
We can show that some equations have no integer solutions by showing that the `same' equations have no solutions in some \Bbb Zn (coefficients need to be interpreted as being in \Bbb Zn ...). The latter is far less difficult to do, in general, because \Bbb Zn has only n elements! For example,
In \Bbb Z5, 02 = 0, 12 = 1, 22 = 4, 32 = 4, and 42 = 1, and so x2 = [3]5 has no solution in \Bbb Z5. So the equation
has no solution with x,y Î \Bbb Z, since if it did, then
[x2-5y2]5 = [x]25-[5]5·[y]35 = [x]25-[0]5·[y3]5 = [x]25 = [531253]5 = [3]5
so [x]25 = [3]5 , which we know is impossible!