Integers

Chapter 1

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 = bq₁ + r₁, with 0 r₁< b
b = r₁q₂ + r₂, with 0 r₂< r₁,
etc.

Since r₁ > r₂ > . . . , the remainders get smaller and smaller, and after a finite number of steps we obtain a remainder r_n+1 = 0. Thus gcd(a,b) = gcd(b,r₁) = . . . = r_n.

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 = p₁^m₁ p₂^m₂ · · · p_n^m_n

where p₁ < p₂ < · · · < p_n and the exponents m₁, m₂ , . . . , m_n 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 = p₁^a₁ p₂^a₂ · · · p_n^a_n and b = p₁^b₁ p₂^b₂ · · · p_n^b_n ,

where a_i 0 and b_i 0 for all i (allowing use of the same prime factors.)
For each i let d_i =min { a_i, b_i } and let m_i =max { a_i, b_i }. Then we have the following factorizations:

(a) gcd(a,b) = p₁^d₁ p₂^d₂ · · · p_n^d_n

(b) lcm[a,b] = p₁^m₁ p₂^m₂ · · · p_n^m_n

Congruences

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 Z_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.3. Definition. If [a]_n belongs to Z_n, 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 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.4.6. Corollary. The following conditions on the modulus n > 0 are equivalent:

(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.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 = p₁^m₁ p₂^m₂ · · · p_n^m_n , then

(n) = n(1-1/p₁)(1-1/p₂) · · · (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⁽ⁿ⁾ 1 (mod n).

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

Forward | Table of Contents | About this document