Transcript Integers and Division

Section 2.4
The Integers and Division
1
Number Theory
• Branch of mathematics that includes
(among other things):
– divisibility
– greatest common divisor
– modular arithmetic
2
Division
• Division of one integer by another (e.g a/b)
produces 2 results:
– quotient: number of time b “goes into” a
– remainder: what’s left over if the values don’t
divide evenly
3
Division
• If a and b are integers and a  0, a divides b
if there exists an integer c such that b = ac
• This also means that c divides b
– a and c are factors of b
– b is a multiple of both a and c
• The notation a|b means a divides, or is a
factor, of b
4
Division
• If n and d are integers, how many positive
integers <= n are divisible by d?
– All integers divisible by d are of the form dk
(where k is a positive integer)
– So the positive integers divisible by d which are
<= n are is the set of all k’s such that:
• 0 < dk <= n or 0 < k <= n/d
• Thus, there are n/d positive integers <= n
which are divisible by d
5
Theorem 1
• Let a, b & c be integers. Then:
– if a|b and a|c, then a|(b+c)
– if a|b then a|bc, for all integers c
– if a|b and b|c, then a|c
6
Proof of Theorem 1
• Part 1: if a|b and a|c, then a|(b+c)
– If a|b and a|c, there must be integers s & t such
that b = as and c = at
– So b+c = as+at = a(s+t)
– Then by definition of divisibility, a|(b+c)
• Part 2: if a|b then a|bc for all integers c
– If a|b, then b = at for some integer t
– so bc = a(tc) and, by definition, a|bc
7
Prime Numbers
• A positive integer that has only 2 positive
integer factors (1 and itself) is a prime
number
• A positive integer > 1 that is not prime is a
composite
8
Theorem 2: Fundamental
Theorem of Arithmetic
• Every positive integer can be written as the
product of primes
• Usually, the prime factors are written in
increasing order, for example:
2 x 3 x 103 = 618
9
Theorem 3
• If n is a composite integer, then n has a
prime divisor <= n
• For example, 103 is prime because:
103 = 10 and
the primes < 10 are 2, 3, 5 and 7
• Since none of these is a factor of 103, 103
must be prime
10
Procedure for determining prime
factors of and integer n
• Divide n by successive primes, beginning
with 2
• If n has a prime factor, then some prime
number p <= n will be found divisible by n
• If such a value p is found, continue by
factoring n/p
– look for value q such that p < q <= n/p
– if found, continue by factoring n/pq, etc.
11
Example
Find prime factorization of 65238:
65238 = 2 x 32619 = 2 x 3 x 10873
Testing prime numbers:
5, 7, 11, 13, 17, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79
Finally, a factor is found:
65238 = 2 x 3 x 83 x 131
Since 131 < 83, no further testing required - 131 is prime
12
Theorem 4: the Division
Algorithm
• For any integer a and positive integer d,
there exist unique integers q and r such that:
a = dq + r
with 0 <= r <= d
• In the above expression:
–
–
–
–
a is the dividend
d is the divisor
q is the quotient
r is the remainder (always positive)
13
Greatest Common Divisors
• For two non-zero integers a and b, the
largest integer d such that d|a and d|b is the
greatest common divisor of a & b, denoted
gcd (a,b)
14
Finding gcd: method 1
• Find all possible divisors of both numbers,
and choose the largest one they have in
common
• Example: find gcd(81, 99)
– factors of 81: 1, 3, 9, 27, 81
– factors of 99: 1, 3, 9, 11, 33, 99
– so gcd(81, 99) = 9
15
Relatively prime numbers
• Two numbers are relatively prime if their
gcd is 1
• Integers in a set {a1, a2, … an} are pairwise
relatively prime if:
gcd(ai,aj) = 1 whenever
1 <= i <= j <=n
16
Relative prime examples
• (14,15,21):
gcd(14,15) = 1
gcd(14, 21) = 7
gcd(15,21) = 3 so they are not relatively prime
• (7,8,9,11)
gcd(7,8) = 1
gcd(7,9) = 1
gcd(7,11) = 1
gcd(8,9) = 1
gcd(9,11) = 1
gcd(8,11) = 1
so they are relatively prime
17
Method 2 for finding gcd
• Use prime factorizations of integers:
a = p1a1*p2a2* … *pnan
b = p1b1*p2b2* … *pnbn
– each exponent is non-negative
– all primes occurring in the factorizations of either
a or b are included in both factorizations, with 0
exponents where necessary
• gcd(a,b) = p1min(a1,b1)*p2min(a2,b2)*…*pnmin(an,bn)
18
Example
a = 12, b = 9
12 = 21 * 21 * 31 * 30 = 22 * 31
9 = 20 * 20 * 31 * 31 = 20 * 32
So gcd(12,9) = 2min(0,2) *3min(1,2) = 20 * 31 = 3
19
Least Common Multiple
• For two positive integers a and b, the
lcm(a,b) is the smallest positive integer that
is divisible by both a and b
• In other words,
lcm(a,b)=p1max(a1,b1)*p2max(a2b2)*…*pnmax(an,bn
)
• For example:
lcm(12,9) = 2max(0,2) * 3max(1,2) = 22 * 32 = 36
20
Theorem 5
• For positive integers a and b, the product of
a and b is equal to gcd(a,b) * lcm(a,b)
• For example, if a=12 and b=9:
12 * 9 = 108
gcd(12,9) = 3 and lcm(12,9) = 36
3 * 36 = 108
21
Modular Arithmetic
• Modulus: operation that finds the remainder
when one positive integer is divided by
another
• a mod m = r when:
a = qm + r and
0 <= r < m
22
Congruence
• For two integers a and b, and positive
integer m, a is congruent to b mod m if
m|(a-b)
This congruence is denoted: a  b (mod m)
a  b (mod m) if and only if a mod m = b mod m
Therefore congruence occurs between a and b
(mod m) if both a and b have the same
remainder when divided by m
23
Congruence Examples
• Determine if 80 is congruent to 5 modulo
17
– Translation: divide 80 by 17 and see if the
remainder is 5
– It isn’t: 17 goes into 80 4 times, with a
remainder of 12
• Is -29 congruent to 5(mod 17)?
– 29 = 17 * (- 2) + 5 so -29  5 (mod 17)
24
Theorems 6 & 7
• Theorem 6:
– Let m be a positive integer:
– Integers a and b are congruent modulo m if and
only if there is an integer k such that a = b + km
• 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)
25
Section 2.4
The Integers and Division
- ends -
26