Excerpted from Beachy/Blair, Abstract Algebra, 2nd Ed., © 1996

Chapter 1

1.1, 1.2 Divisors; prime factorization
1.3, 1.4 Congruences

Forward | Table of Contents | About this document

Divisors; prime factorization

The set {..., -2, -1, 0, 1, 2, 3, ...} is called the set of integers, and will be denoted by Z.

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

aZ = { 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.
We will use the notation gcd(a,b), or simply (a,b), for the greatest common divisor of a and b.

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 = bq1 + r1,   with 0 r1< b
b = r1q2 + r2,   with 0 r2< r1,

Since r1 > r2 > . . . , the remainders get smaller and smaller, and after a finite number of steps we obtain a remainder rn+1 = 0. Thus gcd(a,b) = gcd(b,r1) = . . . = rn.

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 .

1.2.3 Proposition. Let a,b,c be integers.
(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.4. Definition. An integer p>1 is called a prime number if its only divisors are ± 1 and ± p. An integer a > 1 is called composite if it is not prime.

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 = p1m1 p2m2 · · · pnmn

where p1 < p2 < · · · < pn and the exponents m1, m2 , . . . , mn are all positive.

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.
We will use the notation lcm[a,b] for the least common multiple of a and b.

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

a = p1a1 p2a2 · · · pnan     and     b = p1b1 p2b2 · · · pnbn ,

where ai 0 and bi 0 for all i (allowing use of the same prime factors.)
For each i let di =min { ai, bi } and let mi =max { ai, bi }. Then we have the following factorizations:
(a) gcd(a,b) = p1d1 p2d2 · · · pndn

(b) lcm[a,b] = p1m1 p2m2 · · · pnmn


1.3.1. Definition. Let n be a positive integer. Integers a and b are said to be congruent modulo n if they have the same remainder when divided by n. This is denoted by writing a b (mod n).

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), then

then 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.4. Proposition. Let a and n>1 be integers. There exists an integer b such that ab 1 (mod n) if and only if (a,n)=1.

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

The collection of all congruence classes modulo n is called the set of integers modulo n, denoted by Zn.

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.3. Definition. If [a]n belongs to Zn, and [a]n[b]n = [0]n for some nonzero congruence class [b]n, then [a]n is called a divisor of zero, modulo n.

1.4.4. Definition. If [a]n belongs to Zn, 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 Zn, or units of Zn.

1.4.5. Proposition. Let n be a positive integer.

(a) The congruence class [a]n has a multiplicative inverse in Zn if and only if (a,n)=1.

(b) A nonzero element of Zn either has a multiplicative inverse or is a divisor of zero.
1.4.6. Corollary. The following conditions on the modulus n > 0 are equivalent:
(1) The number n is prime.

(2) Zn has no divisors of zero, except [0]n.

(3) Every nonzero element of Zn has a multiplicative inverse.
1.4.7. Definition. Let n be a positive integer. The number of positive integers less than or equal to n which are relatively prime to n will be denoted by (n). This function is called Euler's phi-function, or the totient function.

1.4.8. Proposition. If the prime factorization of n is n = p1m1 p2m2 · · · pnmn , then

(n) = n(1-1/p1)(1-1/p2) · · · (1-1/pk).

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

The following theorem shows that raising any congruence class in Zn× 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 ap a (mod p), for any integer a.

Forward | Table of Contents | About this document