Transcript Chapter 2, Section 2.4

Chapter 2, Section 2.4
The Integers and Division
Recall that the integers are not closed under division. That is,
when we divide one integer by another we are not guaranteed to
get another integer.
Sometimes we do get another integer, ex. 39 divided by 3 is 13.
Other times we end up with a rational number that is not an
integer, ex. 25 divided by 8 is 3.125.
Other times we don’t even get a real number, ex. 5 divided by 0.
Def: Let a and b be 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. To denote that
a divides b we use a | b. We slash through the | symbol to
denote that a does not divide b. [Don’t get confused, a|b and a/b]
Ex: 4 divides 12 since 12 = 4*3. So 4 is a factor of 12 and 12 is
a multiple of 4.
5 does not divide 12 since there is no integer c such that 12 = 5c.
Ex: Let n and d be positive integers. How many positive
integers not exceeding n are divisible by d? That is, how many
members of the set {1, 2, …, n} are divisible by d?
The positive integers divisible by d are d itself, 2*d, 3*d, …
So what we’re really asking is, what is the largest positive
integer k, such that k*d  n. Or equivalently, such that k  n/d.
Recall the floor function: there are n/d positive integers not
exceeding n that are divisible by d.
Ex: Based on the previous example, there are 100/7 =
14.285714… = 14 positive integers not exceeding 100 that are
divisible by 7. They are 7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77,
84, 91, and 98.
Ex: Does 11 divide 0?
Yes. 0 = 11*c (where c = 0) so 11 does divide 0.
Remark: k divides 0 for any k  Z since 0 = k*0 always.
Theorem: Let a, b, and c be integers. Then
1. If a | b and a | c, then a | (b + c).
[Division of Sum]
2. If a | b, then a | bx for all integers x.
[Division of Multiples]
3. If a | b and b | c, then a | c.
[Transitivity]
Proof (of 1): Let a, b, c  Z such that a | b and a | c.
Since a | b, then a  0 and b = a*r for some r  Z.
Since a | c, then a  0 and c = a*s for some s  Z.
Now b + c = a*r + a*s = a(r + s).
So a | b + c since a  0 and b + c = a*(r + s), where r + s  Z.
Corollary: If a, b, and c are integers such that a | b and a | c,
then a | (mb + nc) for all m, n  Z.
Justification: Let a, b, c  Z such that a | b and a | c. Then by (2)
it follows that a | mb and a | nc for all m, n Z. Then apply (1).
Consider a positive integer k. Since k = 1*k and k = k*1 we can
see that it is always the case that 1 | k and k | k. That is, every
positive integer has at least 2 divisors, 1 and itself. [except 1]
Some positive integers, such as 7, have only these two positive
integer divisors. No other positive integer divides 7.
Other positive integers, such as 8, have additional positive integer
divisors. In addition to 1 and 8, both 2 and 4 also divide 8.
Def: A positive integer p greater than 1 is called prime if the only
positive factors of p are 1 and p. A positive integer greater than 1
that is not prime is called composite.
Remark: A positive integer n > 1 is composite if and only if there
exists an integer a such that a | n where 1 < a < n. Such an a is
called a proper factor of n. 1 and n are called trivial factors of n.
Remark: What we have done is to partition the set of positive
integers greater than 2 into two disjoint sets, the primes ({2, 3, 5,
7, 11, 13, …}) and the composites ({4, 6, 8, 9, 10, 12, 14, 15, …}).
Ex: Is 57 prime?
No. 57 = 3*19 so 3 | 57. So 57 is not prime. [Also 19 | 57]
Ex: Is 59 prime?
Yes. We have to determine that no positive integer n, 1 < n < 59,
divides 59. [If you try this you will start to find shortcuts.]
Ex: The number 1 is neither prime nor composite. Only
positive integers greater than 1 are prime or composite.
Ex: The set of primes less than 100 is {2, 3, 5, 7, 11, 13, 17, 19,
23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}.
If you take any of these numbers you will find that the only two
positive divisors of the number are 1 and itself.
Observation: If a | b then |a|  |b|. When we are looking for
possible divisors of a number, we only need to check integers of
lesser magnitude.
Theorem (Fundamental Theorem of Arithmetic): Every positive
integer greater than 1 can be written uniquely as a prime or as
the product of two or more primes where the prime factors are
written in order of nondecreasing size.
Ex: 100 = 2 * 2 * 5 * 5 = 2252
999 = 3 * 3 * 3 * 37 = 3337
59 = 59
1024 = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 = 210
The unique factorization into a product of primes for a number is
called its prime factorization. The unique factorization of a
prime number is simply the number itself. The unique
factorization of a composite number is a product of two or more
primes.
Theorem: If n is a composite integer, then n has a prime
divisor less than or equal to n.
Proof: Let n be a composite integer.
Then n has a (proper) factor r with 1 < r < n.
That is, n = r*q for some integer r where 1 < r < n.
It must be the case that 1 < q < n as well since n = r*q.
In fact, either r or q must be  n because if both were greater
than n then their product would exceed n, which it doesn’t.
So we have established that n has a proper factor less than or
equal to n (call it z).
Now apply the Fundamental Theorem of Arithmetic to z to get
its prime factorization. Each prime factor in the prime
factorization of z must be less than or equal to z. Any one of
these primes is hence  n. So n has a prime factor  n.
Ex: 1000 = 10 * 100. So 10 and 100 are factors of 1000. The
square root of 1000 is about 31.6. And we see that 10  31.6.
10 is not prime, but its prime factorization is 2*5. So 5 is a
prime factor of 1000 not exceeding 1000.
Ex: 101 is prime.
The square root of 101 is just a bit over 10. So we can check
only the prime numbers not exceeding 10. We can see that
none of 2, 3, 5, or 7 divides 101. So 101 is prime since it
doesn’t have a prime factor  101.
Ex: Find the prime factorization of 7007.
2 does not divide 7007. 3 does not divide 7007. 5 does not
divide 7007. But 7007 = 7*1001. Now we continue to factor
1001. Start with 7. [Why?]. 1001 = 7*143. Now continue to
factor 143. Start with 7. 7 does not divide 143. But 143 =
11*13. So the prime factorization of 7007 = 7*7*11*13.
Preliminaries
• Reminder: HW5 is due Wednesday
• Pass back HW4
– average: 90%, median: 91%
• Emmanuel graded 1.5: 27, 30, and 64 (green)
• Pascal graded the rest -- S1.6, S1.7 (red)
• http://www.cs.virginia.edu/~cmt5n/cs202/hw4/
Theorem: For any positive integer n, there is a prime number
greater than n.
Proof: Let n be a positive integer.
Consider the number n! + 1.
Recall n! + 1 = 1*2*3*…*n + 1.
By the FTOA, this number has a unique prime factorization.
It turns out that none of the numbers 2, …, n can divide n! + 1.
This is because we know any such number divides n!. So if that
number also divided n! + 1 then it would have to also divide the
sum (-1)*(n!) + 1*(n! + 1) = -(n!) + n! + 1 = 1. (Recall “if a | b and
a | c, then a | (mb + nc) for all m, n  Z”). But none of these
numbers divides 1. Hence no number 2, …, n can divide n! + 1.
So all of the factors in the prime factorization of n! + 1 must be
greater than n. Hence there must be a prime greater than n.
Corollary: There are infinitely many primes.
Theorem (The Division Algorithm): Let a, d  Z with d > 0.
Then there are unique integers q and r, with 0  r < d, such that
a = dq + r. We call d the divisor, a the dividend, q the quotient,
and r the remainder. [This is what we do in long division]
Ex: Let a = 101 and d = 11. The unique q and r which satisfy
the division algorithm are q = 9 and r = 2 since 101 = 11*9 + 2.
Ex: Let a = -11 and d = 3. The unique q and r which satisfy the
division algorithm are q = -4 and r = 1 since -11 = 3*(-4) + 1.
It is tempting to say q = -3 and r = -2 since -11 = 3*(-3) + (-2)
however this r does not satisfy 0  r < d.
Remark: The integer a is divisible by the integer d if and only if
the remainder r is zero when a is divided by d.
Def: Let a and b be integers, not both 0. The largest integer d
such that d | a and d | b is called the greatest common divisor of
a and b. We denote this as gcd(a, b).
Remark: The greatest common divisor of two integers which
are not both zero exists because this set of common divisors is
always finite and non-empty. This is due to the fact that the set
of divisors of a non-zero integer is always finite and non-empty.
Ex: Let a = 24 and b = 36. The set of positive divisors of 24 is
{1, 2, 3, 4, 6, 8, 12, 24} and for 36 is {1, 2, 3, 4, 6, 9, 12, 18, 36}.
So the set of common divisors of 24 and 36 is the intersection
of these two sets {1, 2, 3, 4, 6, 12}. So gcd is 12.
Ex: Let a = 17 and b = 22. Then the set of positive divisors of
17 is {1, 17} and for 22 is {1, 2, 11, 22}. So the set of common
divisors of 17 and 22 is {1}. So gcd is 1.
There is an efficient algorithm (called the Euclidean algorithm) for
finding the gcd of two numbers. It is discussed in Section 2.5.
Def: The integers a and b are relatively prime if gcd(a, b) = 1.
Ex: We saw that 17 and 22 are relatively prime.
Ex: 35 and 49 are not relatively prime since gcd(35, 49) = 7.
Def: The integers a1, a2, …, an are pairwise relatively prime if
gcd(aj, ak) = 1 whenever 1  i < j  n. That is, the integers are
pairwise relatively prime if every pair of them is relatively prime.
Ex: The integers 10, 19, and 24 are not pairwise relatively
prime since gcd(10, 24) = 2.
Ex: The integers 10, 19, and 21 are pairwise relatively prime
since gcd(10, 19) = 1, gcd(10, 21) = 1, and gcd(19, 21) = 1.
Note that a group of integers is pairwise relatively prime if and
only if there is no positive integer greater than 1 which divides
more than one of the integers in the group.
We can take advantage of the prime factorizations of two
integers to find their gcd. Of course this method will only apply
if both integers are nonzero since 0 has no prime factorization.
Ex: 120 = 23 * 3 * 5 and 500 = 22 * 53. What is gcd(120, 500)?
gcd(120, 500) = 22 * 5 = 20. We simply take the minimum of the
exponents that each prime is raised to in the prime factorization.
If we had taken the maximum of the exponents that each prime
is raised two then we would get the least common multiple.
Def: The least common multiple of two positive integers a and b
is the smallest positive integer that is divisible by both a and b.
Ex: lcm(120, 500) = 23 * 3 * 53 = 3000.
Theorem: Let a and b be positive integers. Then
a*b = gcd(a, b) * lcm(a, b).
Def: Let a, b, m  Z with m > 0. 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.
Remark: Don’t confuse this notation with the notation a mod m
which denotes the remainder when a is divided by m. The
following theorem indicates the connection between the two.
Theorem: Let a, b, m  Z with m > 0. Then a  b (mod m) if
and only if a mod m = b mod m. That is, two integers are
congruent modulo m if and only if they have the same
remainder when divided by m.
Ex: 17  5 (mod 6) by the definition since 6 | (17 – 5). We also
see that 17 and 5 both leave the same remainder when divided
by 6. So by the previous theorem we also see 17  5 (mod 6).
Ex: 24 is not congruent to 14 modulo 6. We see that 6 does not
divide (24 – 14) = 10. Further, 24 leaves a remainder of 0 when
divided by 6 while 14 leave a remainder of 2 when divided by 6.
Theorem: Let a, b, m  Z with m > 0. Then a is congruent to b
modulo m if and only if there is an integer k such that a = b + km.
Proof: Let a, b, m  Z with m > 0.
() Assume that m | (a – b). Then a – b = mk for some k  Z.
So a = b + mk for some integer k.
() Assume that there exists an integer k such that a = b + km.
Then a – b = km, so m | (a – b).
[We could have shown 1  2  3  1 to show the 3 equivalent]
Def: Let a, m  Z with m > 0. The set of all integers congruent
to a modulo m is called the congruence class of a modulo m.
Ex: The congruence class of 2 modulo 6 is
{…, -10, -4, 2, 8, 14, …} = {6k + 2 | k  Z }.
Ex: The congruence class of 0 modulo 8 is
{…, -16, -8, 0, 8, 16, …} = {8k + 0 | k  Z }. [all multiples of 8]
Theorem: Let a, b, c, d, m  Z with m > 0. If a  b (mod m) and
c  d (mod m) then
(1) a + c  b + d (mod m)
(2) ac  bd (mod m)
Ex: If it is 1700 hours now, what time will it be in 60 hours?
(17 + 60) mod 24 = 77 mod 24 = 5. So it will be 0500 hours.
We could have applied the above theorem instead to find that
since 17  17 (mod 24) and 60  12 (mod 24) then (17 + 60) 
(17 + 12) (mod 24). So instead of computing (17 + 60) mod 24,
we can use (17 + 12) mod 24 = 29 mod 24 = 5.