- 1.1, 1.2 Divisors; prime factorization
- 1.3, 1.4 Congruences

Forward | Table of Contents | About this document

**1.1.1. Definition.**
An integer a is called a
**multiple**
of an integer b if a=bq for some integer q.
In this case we also say that b is a
**divisor**
of a, and we use the notation b | a.

In the above case we can also say that b is a
**factor**
of a, or that a is
**divisible**
by b. If b is not a divisor of a, meaning that
a bq for all
q **Z**,
then we write b a.
The set of all multiples of an integer a will be denoted by

a**Z** = {
m **Z** | m=aq for
some q **Z** }.

**1.1.2. Axiom. [Well-Ordering Principle]**
Every nonempty set of natural numbers contains a smallest element.

**1.1.3 Theorem. [Division Algorithm]**
For any integers a and b, with b>0,
there exist unique integers q (the
**quotient**)
and r (the
**remainder**)
such that a=bq+r, with 0 r<b.

**1.1.4. Theorem.**
Let I be a nonempty set of integers
that is closed under addition and subtraction.
Then I either consists of zero alone or else contains
a smallest positive element,
in which case I consists of all multiples
of its smallest positive element.

**1.1.5. Definition.**
A positive integer d is called the
**greatest common divisor**
of the nonzero integers a and b if

**(i)**d is a divisor of both a and b, and**(ii)**any divisor of both a and b is also a divisor of d.

**1.1.6. Theorem.**
Any two nonzero integers a and b have a greatest common divisor,
which can be expressed as the smallest positive linear combination of a and b.

Moreover, an integer is a linear combination of a and b
if and only if it is a multiple of their greatest common divisor.

The greatest common divisor of two numbers
can be computed by using a procedure known as the
**Euclidean algorithm**.
First, note that if a 0 and
b | a, then gcd(a,b) = |b|.
The next observation provides the basis for the Euclidean algorithm.
If a=bq+r, then (a,b)=(b,r).
Thus given integers a>b>0,
the Euclidean algorithm uses the division algorithm repeatedly to obtain

a = bq_{1} + r_{1}, with
0 r_{1}< b

b = r_{1}q_{2} + r_{2}, with
0 r_{2}< r_{1},

etc.

**1.2.1. Definition.**
The nonzero integers a and b are said to be
**relatively prime**
if (a,b)=1.

**1.2.2 Proposition.**
Let a,b be nonzero integers.
Then (a,b)=1 if and only if there exist integers m,n such that

ma + nb = 1 .

**(a)**If b | ac, then b | (a,b)c.**(b)**If b | ac and (a,b)=1, then b | c.**(c)**If b | a, c | a and (b,c)=1, then bc | a.**(d)**(a,bc)=1 if and only if (a,b)=1 and (a,c)=1.

**1.2.5. Lemma. [Euclid]**
An integer p>1 is prime if and only if it satisfies the following property:
If p | ab for integers a and b, then either p | a or p | b.

**1.2.6. Theorem. [Fundamental Theorem of Arithmetic]**
Any integer a>1 can be factored uniquely
as a product of prime numbers, in the form

a =
p_{1}^{m1}
p_{2}^{m2}
** · · ·**
p_{n}^{mn}

**1.2.7. Theorem. [Euclid]**
There exist infinitely many prime numbers.

**1.2.8. Definition.**
A positive integer m is called the
**least common multiple**
of the nonzero integers a and b if

**(i)**m is a multiple of both a and b, and**(ii)**any multiple of both a and b is also a multiple of m.

**1.2.9. Proposition.**
Let a and b be positive integers with prime factorizations

a =
p_{1}^{a1}
p_{2}^{a2}
** · · · **
p_{n}^{an}
and b =
p_{1}^{b1}
p_{2}^{b2}
** · · · **
p_{n}^{bn} ,

For each i let d

**(a)**gcd(a,b) = p_{1}^{d1}p_{2}^{d2}**· · ·**p_{n}^{dn}**(b)**lcm[a,b] = p_{1}^{m1}p_{2}^{m2}**· · ·**p_{n}^{mn}

**1.3.2. Proposition.**
Let a,b, and n>0 be integers. Then
a b (mod n)
if and only if n | (a-b).

When working with congruence modulo n, the integer n is called the
**modulus**.
By the preceding proposition,
a b (mod n)
if and only if a-b=nq for some integer q.
We can write this in the form a=b+nq, for some integer q.
This observation gives a very useful method of replacing
a congruence with an equation (over **Z**).
On the other hand, Proposition 1.3.3 shows that
any equation can be converted to a congruence modulo n
by simply changing the = sign to .
In doing so, any term congruent to 0 can simply be omitted.
Thus the equation a=b+nq would be converted back to
a b (mod n).

**1.3.3 Proposition.**
Let n>0 be an integer.
Then the following conditions hold for all integers a,b,c,d:

**(a)**If a c (mod n) and b d (mod n), thenthen a b c d (mod n), and ab cd (mod n).

**(b)**If a+c a+d (mod n), then c d (mod n).If ac ad (mod n) and (a,n)=1, then c d (mod n).

**1.3.5. Theorem.**
The congruence ax b (mod n)
has a solution if and only if b is divisible by d, where d=(a,n).

If d | b, then there are d distinct solutions modulo n,
and these solutions are congruent modulo n / d.

**1.3.6. Theorem. [Chinese Remainder Theorem]**
Let n and m be positive integers, with (n,m)=1.
Then the system of congruences

x a (mod n) x b (mod m)

has a solution. Moreover, any two solutions are congruent modulo mn.
**1.4.1. Definition.**
Let a and n>0 be integers.
The set of all integers which have the same remainder as a
when divided by n is called the
**congruence class**
of a modulo n, and is denoted by
[a]_{n}, where

[a]_{n} =
{ x **Z** |
x a (mod n) }.

**1.4.2 Proposition.**
Let n be a positive integer, and let a,b be any integers.
Then the addition and multiplication of congruence classes
given below are well-defined:

[a]_{n} + [b]_{n} = [a+b]_{n} ,
[a]_{n}[b]_{n} = [ab]_{n}.

**1.4.4. Definition.**
If [a]_{n} belongs to
**Z**_{n}, and
[a]_{n}[b]_{n} = [1]_{n},
for some congruence class [b]_{n}, then
[b]_{n} is called a
** multiplicative inverse **
of [a]_{n} and is denoted by
[a]_{n}^{-1}.

In this case, we say that
[a]_{n} and [b]_{n} are
**invertible**
elements of
**Z**_{n}, or
**units**
of **Z**_{n}.

**1.4.5. Proposition.**
Let n be a positive integer.

**(a)**The congruence class [a]_{n}has a multiplicative inverse in**Z**_{n}if and only if (a,n)=1.**(b)**A nonzero element of**Z**_{n}either has a multiplicative inverse or is a divisor of zero.

**(1)**The number n is prime.**(2)****Z**_{n}has no divisors of zero, except [0]_{n}.**(3)**Every nonzero element of**Z**_{n}has a multiplicative inverse.

**1.4.8. Proposition.**
If the prime factorization of n is
n =
p_{1}^{m1}
p_{2}^{m2}
** · · · **
p_{n}^{mn} ,
then

(n)
= n(1-1/p_{1})(1-1/p_{2})
** · · · **
(1-1/p_{k}).

**1.4.9. Definition.**
The set of units of
**Z**_{n},
the congruence classes
[a]_{n},
such that (a,n)=1, will be denoted by

**Z**_{n}^{×}.

The following theorem shows that raising any congruence class in
**Z**_{n}^{×}
to the power (n)
yields the congruence class of 1.
It is possible to give a purely number theoretic proof at this point, but in
Example 3.2.12
there is a more elegant proof using elementary group theory.

** 1.4.11. Theorem. [Euler] **
If (a,n)=1, then a^{
(n)}
1 (mod n).

**1.4.12 Corollary. [Fermat]**
If p is prime, then
a^{p} a (mod p),
for any integer a.