DEFINITION 1. If a and b are integers with a ¹ 0, we say that a divides b if there is an integer c such that b = ac. When a divides b we say that a is a factor of b and that b is a multiple of a. The notation a½b denotes that a divides b.

Example 2: Let n and d be positive integers. How many positive integers not exceeding n are divisible by d?

THEOREM 1: Let a, b, and c be integers. Then 1) if a½b and a½c, then a½(b+c);

2) if a½b, then a½bc for all integers c;

3) if a½b and b½c, then a½c.

DEFINITION 2:A positive integer p greater than 1 is called prime if the only positive factors of p are 1 and p. A positive integer that is greater than 1 and is not prime is called composite.

THEOREM 2: THE FUNDAMENTAL THEOREM OF ARITHMETIC:

Every positive integer can be written uniquely as the product of primes, where the prime factors are written in order of increasing size. (Here a product can have zero, one, or more than one prime factor).

THEOREM 3: If n is a composite integer, then n has a prime divisor less than or equal to Ön.

EXAMPLE 5: Show that 101 is prime.

EXAMPLE 6: Find the prime factorization of 7007.

DEFINITION: Primes of the form 2^p – 1 are called Mersenne primes.

THEOREM 4: THE DIVISION ALGORITHM Let a be an integer and d a positive integer. Then there are unique integers q and r, with 0 £ r < d, such that

A = dq + r.

DEFINITION 3: In the equality given in the division algorithm, d is called the divisor, a is called the dividend, q is called the quotient, and r is called the remainder.

EXAMPLE 8: What is the quotient and remainder when 101 is divided by 11?

EXAMPLE 9: What is the quotient and remainder when -11 is divided by 3?

GREATEST COMMON DIVISIORS AND LEAST COMMON MULTIPLES

DEFINITION 4: Let a and b be integers, not both zero. The largest integer d such that d½a and d½b is called the greatest common divisor of a and b. The greatest common divisor of a and b is denoted by gcd(a,b).

EXAMPLE 10: What is the greatest common divisor of 24 and 36?

DEFINITION 5: The integers a and b are relatively prime if their greatest common divisor is 1.

DEFINITION 6: The integers a₁, a₂, …, a_n are pairwise relatively prime if gcd(a_i, a_j) = 1 whenever 1 £ i < j £ n.

EXAMPLE 13: Determine whether the integers 10, 17, and 21 are pairwise relatively prime and whether the integers 10, 19, and 24 are relatively prime.

Suppose the prime factorizations of the integers a and b are

a = p₁^a1p₂^a2…p_n^an and b = p₁^b1p₂^b2…p_n^bn

where each exponent is a nonnegative integer, and where all primes occurring in the prime factorization of either a or b are included in both factorizations, with zero exponents if necessary. Then gcd(a,b) is given by

gcd(a,b) = p₁^min(a1,b1)p₂^min(a2,b2)…p_n^min(an,bn)

EXAMPLE 14; Find the greatest common divisor of 120 and 500 using their prime factorizations.

DEFINITION 7. The least common multiple of the positive integers a and b is the smallest positive integer that is divisible by both a and b. The least common multiple of a and b is denoted by lcm(a,b).

Analogous to gcd,

lcm(a,b) = p₁^max(a1,b1)p₂^max(a2,b2)…p_n^max(an,bn)

Find the least common multiple of 120 and 500 using their prime factorizations.

THEOREM 5; Let a and b be positive integers. Then ab = gcd(a,b) x lcm(a,b).

MODULAR ARITHMETIC

DEFINITION 8. let a be an integer and m be a positive integer. We denote by a mod m the remainder when a is divided by m.

EXAMPLE 16 17 MOD 5 = 2,

-133 MOD 9 = 2, AND 2001 MOD 101 = 82.

The following notation indicates that two integers have the same remainder when they are divided by the positive integer m.

DEFINITION 9. If a and b are integers and m is a positive integer, then a is congruent to b modulo m if m divides a – b. We use the notation a º b (mod m) to indicate that a is congruent to b modulo m.

Note that a º b (mod m) if and only if

a mod m = b mod m.

EXAMPLE 17: Determine whether 17 is congruent to 5 modulo 6 and whether 24 and 14 are congruent modulo 6.

THEOREM 6: Let m be a positive integer. The integers a and b are congruent modulo m if and only if there is an integer k such that

a = b + km.

Proof: If a º b (mod m), then m½(a – b). This means that there is an integer k such that

A – b = km, so that a = b + km. Conversely, if there is an integer k such that a = b + km, then km = a – b. Hence, m divides a – b, so that a º b (mod m).

THEOREM 7: Let m be a positive integer. If a º b (mod m) and c º d (mod m), then

a + c º b + d (mod m) and ac º bd (mod m). Proof: Since a º b (mod m) and

c º d (mod m), there are integers s and t with

b = a + sm and d = c +tm. Hence,

b + d = (a + sm) + (c + tm) = (a + c) + m(s + t)

bd = (a+sm)(c+tm) = ac + m(at+cs+stm).

Hence,

a + c º b + d (mod m) and ac º bd (mod m).

EXAMPLE 18: Since 7 º 2 (mod 5) and

11 º 1 (mod 5), it follows from Theorem 7 that 18 = 7+11 º 2+1 =3 (mod 5) and that

77 = 7 x 11 º 2 x 1 = 2 (mod 5).

APPLICATIONS OF CONGRUENCES:

· HASHING FUNCTIONS

· PSEUDORANDOM NUMBERS

· CRYPTOLOGY

EXAMPLE 19 (hashing functions): How can memory locations be assigned so that student records can be retrieved quickly?

Choose a suitable hashing function. A hashing function h assigns memory location h(k) to the record that has k as its key.

A common hashing function is

h(k) = k mod m where m is the number of available memory locations.

For m = 111 the SS# 064212848 is assigned to location 14 since

h(064212848) = 064212848 mod 111 = 14.

Since h is not 1-1, more than one file may be assigned to a memory location. This is called collision.

EXAMPLE 20 (pseudorandom numbers):

Used in computer simulations.

The most commonly used procedure for generating pseudorandom numbers is the linear congruential method. Choose four integers: the modulus m, multiplier a, increment c, and seed x₀, with 2 £ a < m,

0 £ c < m, and 0 £ x₀ < m. We generate a sequence of pseudorandom numbers {x_n},

with 0 £ x_n < m for all n, by successively using the congruence

x_n+1 = (ax_n + c) mod m.

If the pseudorandom numbers must be between 0 and 1, we divide numbers generated with a linear congruential generator by the modulus: that is, we use the numbers x_n/m.

For instance, the sequence of pseudorandom numbers generated by choosing m = 9, a = 7, c = 4, and x₀ = 3, can be found as follows:

x₁ = 7x₀ + 4 = 7x3 + 4 = 25 mod 9 = 7

x₂ = 7x₁ + 4 = 7x7 + 4 = 53 mod 9 = 8

x₃ = 7x₂ + 4 = 7x8 + 4 = 60 mod 9 = 6

x₄ = 7x₃ + 4 = 7x6 + 4 = 46 mod 9 = 1

x₅ = 7x₄ + 4 = 7x1 + 4 = 11 mod 9 = 2

x₆ = 7x₅ + 4 = 7x2 + 4 = 18 mod 9 = 0

x₇ = 7x₆ + 4 = 7x0 + 4 = 4 mod 9 = 4

x₈ = 7x₇ + 4 = 7x4 + 4 = 32 mod 9 = 5

x₉ = 7x₈ + 4 = 7x5 + 4 = 39 mod 9 = 3

Since x₀ = x₉ repeating!

If c = 0, then the generator is called a pure multiplicative generator. For example, the pure multiplicative generator with

m = 2³¹ – 1 and a = 7⁵ = 16,807 is widely used.

For this generator, it can be shown that

2³¹ – 2 numbers are generated before repetition begins.

CRYPTOLOGY

Julius Caesar made messages by shifting each letter three to the right (the last three letters are sent to the first three), e.g., B is encrypted to an E and X is encrypted to an A. To do this mathematically replace each letter with an integer from 0 to 25. Caesar’s encryption method can be represented by the function f that assigns to the nonnegative integer p,

p £ 25, the integer f(p) in the set {0,1,2,…, 25} with f(p) = (p + 3) mod 26. In the encrypted version of the message, the letter represented by p is replaced with the letter represented by

(p + 3) mod 26. This is called a shift cipher. To decrypt or decode the message use the inverse function f^-1(p) = (p – 3) mod 26.

One way to enhance this scheme is to use a function of the form

f(p) = (ap + b) mod 26 where a and b are integers, chosen such that f is a bijection (Such a mapping is called an affine transformation).

EXAMPLE 22: What letter replaces the letter K when the function

f(p) = (7p+3) mod 26 is used for encryption?

Solution: First, note that 10 represents K. Then using the encryption function specified, it follows that f(10) = (7x10+3) mod 26 = 21. Since 21 represents V, K is replaced by V in the encrypted message.

COMMENT:Encryption methods of this kind are vulnerable to attacks based on the frequency of occurrence of letters in the message. More sophisticated encryption methods are based on replacing blocks of letters with other blocks of letters. There are a number of techniques based on modular arithmetic for encrypting blocks of letters.