## Twee maanden rekenen

Een PDF versie hier (of rechts-clikken de scherm vor een grote versie):

A field is a *set* of elements that is *closed* under, and satisfies the axioms of, *associativity*, *commutativity*, *distributivity*, identity and *inverse*, for addition and multiplication. The number of elements in a field *Z _{p}* is

A field with a finite number of elements is called a *Galois* Field. As an aside to this aside, in looking at error correcting codes, a binary code (alphabet {*0*, *1*}) with codewords of length *n* has all its codes in the field *GF*(2^{n}). *GF*(2^{n}) is a vector space of *n*-tuples over *GF*(*2*).

Number theory deals with, well, the theory of numbers and relations or *congruences* between them. In the same way that in physics one may talk about matter in terms of elementary particles, in number theory the elementary particles in number theory are prime numbers; indeed, this is the subject of the *fundamental theorem of arithmetic*. But first, here are some notes from the book *Number Theory* by George E. Andrews.

**[Principle of Mathematical Induction]**

A statement about integers is true for all integers *≥ 1* if

(i) it is true for the integer *1*

(ii) whenever it is true for all the integers *1, 2, …, k*, then it is true for the integer k+1

**[The basis representation theorem]**

Let *k* be any integer larger than *1*. Then, for each positive integer *n*, there exists a representation

n = a_{0}k^{s}+ a_{1}k^{s-1}+ … + a_{s}

where *a _{0}≠ 0*, and where each

**[Euclid's division Lemma]**

For any integers *k > 0* and *j*, there exist unique integers *q* and *r* such that

0 ≤ r < k

j = qk + r

**[The Division Algorithm]**[from Baylis, ch. 3]

∀ a ∈ Z

∃ b ∈ {0, 1, 2, …, m-1}

such thata ≡ b mod m

**[Greatest Common Divisor (gcd)]**

Definition: If

(i)

d > 0

(ii)dis a common divisor ofaandb

(iii) each integerfthat is a common divisor of bothaandbis also a divisor ofd.

Alternatively [Baylis]: For any integers *a*, *b* not both zero, the set of all integer linear combinations of *a* and *b* is the set of all multiples of *gcd(a,b)*.

**[Theorem]**

If *a = bq + r* and *b ≠ 0*, then *gcd(a,b) = gcd(b,r)*.

**[Euclid's Algorithm (for gcd( a,b)]**

gcd(a, b)

{

if (b == 0) return a;

return gcd(b, a mod b)

}

**[note 1]**

If *d = gcd(a,b)* then there exists integers *x* and *y* such that

ax + by = d

**[Primality]**

Definition: A positive integer *p*, other than *1*^{†}, is said to be *prime* if its onle positive divisors are *1* and *p*.

^{†}Note: 1 is not a prime, though one could just as well argue that it is. The reason for this special cas in the definition of primes, is that, it makes other definitions in number theory, particularly the fundamental theorem of arithmetic much easier to define.

**[note 3 (Euclid's Lemma)]**

If *a* and *b* are integers, *p* is prime, *p|ab* and *p* does not divide *a*, then *p|b*.

Equivalently, we could state this as [Baylis]: if *a*|*bc* and *(a, b)* is a coprime pair, then *a*|*c*.

**[note 4]**

If *p|a _{1}a_{2}…a_{n}*, then there exists

**[The Fundamental Theorem of Arithmetic]**

For each integer *n > 1*, there exist primes

p_{1}≤p_{2}≤…≤p_{r}

such that

n = p_{1}p_{2}…p_{r}

and this factorization is unique.

such that

and this factorization is unique.

**[note 5]**

An equivalence relation is symmetric, reflexive and transitive.

**[Congruence]**

*a ≡ b (mod c)* if *c |(a-b)*. A perhaps more intuitive definition of congruence [Baylis, ch. 3] can be made as follows:

If

a, b, ∈ Z

and

m ∈ Z^{+}

then

a ≡ b (mod m)

ifaandbdiffer by a multiple ofm.

Some properties of congruences:

(i)

a ≡ a (mod m)(reflexivity)

(ii) Ifa ≡ b (mod m)thenb ≡ a (mod m)(symmetry)

(iii) Ifa ≡ b (mod m)andb ≡ c (mod m)thena ≡ c (mod m)(transitivity)

(iv) Ifa ≡ b (mod m)andc ≡ d (mod m)thena + c ≡ b + d (mod m), and ac ≡ bd (mod m)

Congruence is an equivalence relation.

**[Theorem]**

If

ax ≡ ay (mod m)

then

x ≡ y (mod m/d)

whered = gcd(a, m)

**[Linear Congruences in one variable and Equations]**

The congruence

ax ≡ c (mod m)

is equivalent to the equation

ax – my = c

[Theorem]

The linear congruence *ax *≡* c (mod m)* has a solution iff *gcd(a,m)*|*c*.

**[Theorem]**

If the congruence *ax *≡* c (mod m)* has a solution, it has precisely *d* solutions which are distinct *mod m*, where *d = gcd(a, m)*.

**[Diophantine Equations]**

An equation in which only integral solutions are allowed is called a *Diophantine* equation.

An equation in which only integral solutions are allowed is called a *Diophantine* equation.

**[Theorem]**

In order that there exist integers x and y satisfying

ax + by = c

it is necessary and sufficient that

gcd(a,b) | c

**[Theorem]**

Suppose *a ≡ a’(mod c)* and *b ≡ b’ (mod c)* then

a ± b ≡ a’ ± b’ (mod c)

and

ab ≡ a’b’ (mod c)

**[Theorem]**

If *bd ≡ bd’ (mod c)* and *gcd(b,c) = 1*, then *d ≡ d’ (mod c)*.

**[Theorem]**

If *p* is prime and *a*, *b* ∈ Z_{p} and *ab = 0*, then *a* or *b* (or both) are zero.

(Z_{p} is a finite field of size *p*, and *p* is prime)

**[Theorem]**

If *p* is prime, and *x* is a non-zero member of the field *Z _{p}*, then

At this point, we can start talking about residue systems, and what it means for *j* to be a *residue* of *h* *modulo m*, of *complete residue systems* and also of *partial residue systems*; I however think we have already digressed a bit from out initial goals of reviewing number theory.

steal compass, drive north, disappear...