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 = a0ks + a1ks-1 + … + as

where a0≠ 0, and where each ai is nonnegative and less than 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 that a ≡ 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) d is a common divisor of a and b
(iii) each integer f that is a common divisor of both a and b is also a divisor of d.

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

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

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|a1a2…an, then there exists i such that p | ai.

[The Fundamental Theorem of Arithmetic]
For each integer n > 1, there exist primes


such that

n = p1p2…pr

and this factorization is unique.

The Fundamental Theorem of Arithmetic: For each integer n > 1, there exist primes p1≤p2≤…≤pr
such thatn = p1p2…pr
and this factorization is unique.

[note 5]
An equivalence relation is symmetric, reflexive and transitive.

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
m ∈ Z+
a ≡ b (mod m)
if a and b differ by a multiple of m.

Some properties of congruences:

(i) a ≡ a (mod m)(reflexivity)
(ii) If a ≡ b (mod m) then b ≡ a (mod m)(symmetry)
(iii) If a ≡ b (mod m) and b ≡ c (mod m) then a ≡ c (mod m) (transitivity)
(iv) If a ≡ b (mod m) and c ≡ d (mod m) then a + c ≡ b + d (mod m), and ac ≡ bd (mod m)

Congruence is an equivalence relation.


ax ≡ ay (mod m)
x ≡ y (mod m/d)
where d = gcd(a, m)

[Linear Congruences in one variable and Equations]
The congruence

ax ≡ c (mod m)

is equivalent to the equation

ax – my = c

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

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.

In order that there exist integers x and y satisfying

ax + by = c

it is necessary and sufficient that

gcd(a,b) | c

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

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

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

If p is prime and a, b ∈ Zp and ab = 0, then a or b (or both) are zero.
(Zp is a finite field of size p, and p is prime)

If p is prime, and x is a non-zero member of the field Zp, then
Zp has a unique member 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.

Related Tags

Leave a Reply

You must be logged in to post a comment.

This entry was posted on Tuesday, February 21st, 2006 at 1:00 pm. You can follow any responses to this entry through the RSS 2.0 feed. If you're wondering how to get your own icon next to your comment, go visit gravatar.com and get yourself hooked up.
 steal compass, drive north, disappear...