## A little Number Theory February 21, 2006

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

*a*is nonnegative and less than

_{i}*k*. This representation of

*n*is unique, and is called the

*representation of n to the base k*.

**[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

*a*and

*b*are integers, not both zero, then an integer

*d*is called the gcd of

*a*and

*b*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

*i*such that

*p | a*.

_{i}**[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.

**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.

**[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.

*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

*Z*has a unique member

_{p}*y*, such that

*xy = 1*.

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.

## Leave a Reply

You must be logged in to post a comment.