Transcript Chapter 5 Number Theory

Chapter 5
Properties of Whole Numbers
Some preliminary definitions
If we have whole numbers a, b, and c such that
a×b=c
then we say that
1. a divides c or
2. a is a factor of c or
3. a is a divisor of c and
4. c is a multiple of a or
5. c is divisible by a
(We can always interchange a with b.)
Properties of Divisibility
Suppose that a, m, n, k are whole numbers where a ≠ 0.
1. If a divides m and a divides n, then a divides (m + n).
2. If a divides m but a does not divide n, then a does not
divide (m + n).
3. If a divides both m and n, and m ≥ n, then a divides
(m – n).
4. If a divides m but a does not divide n, and m ≥ n, then a
does not divide (m – n).
5. If a divides m, then a divides km.
Transitive Property of Divisibility
If a, b, c are non zero whole numbers such that
a divides b and b divides c, then a divides c.
Important remarks:
1. 0 is divisible by any non-zero number,
2. No number is divisible by 0.
Different types of whole numbers
a. Prime numbers
A number is prime if it is > 1 and it is only
divisible by 1 and itself.
e.g. 2, 3, 5, 7, 11, …
b. Composite numbers
A number is composite if it can be written as the
product of two smaller whole numbers.
e.g. 4 (=2×2), 6 (=2×3), 10 (=2×5), …
c. Identities
The numbers 0 and 1 are not prime nor composite,
they are just identities for respective operations.
Prime numbers play an important role within the whole
numbers because they are the primary components. More
precisely, we have the following
Theorem
Every whole number bigger than 1 is either a prime
number or a product of prime numbers.
(in other words, the prime numbers can generate all whole
numbers bigger than 1 by multiplication.)
Factorization Trees
According to the previous theorem, if a number n
is not prime, we must be able to break it down to
a product of prime numbers. Here is how,
60
6
2
3
This tree is by no
means unique, we
can easily make
another one, such as
10
2
5
However, the collection of prime numbers we get
from the “leaves” of the tree is always the same.
In other words, 60 = 2×2×3×5 no matter how
we factorize it.
60
2
30
5
6
2
3
Unique Factorization Theorem
Any whole number bigger than 1 can be factorized
into a product of prime numbers in exactly one
way if we list its prime factors from small to large.
Example: 3780 = 2×2×3×3×3×5×7
Test for Primeness
(i.e. a faster way to determine whether a whole
number is prime or not)
Theorem A whole number n ( >1) is prime if it is not divisible by
any prime number 
n
Example: Is 179 a prime number?
a. compute 179 which is approx. 13.379
b. all prime numbers  13.3 are 2, 3, 5, 7, 11, 13
c. Is 179 divisible by 2? No
Is 179 divisible by 3? No
Is 179 divisible by 5? No
Is 179 divisible by 7? No
Is 179 divisible by 11? No
Is 179 divisible by 13? No
Therefore 179 is prime.
(Note: this reduce the work from checking 177 numbers to just
6 numbers!)
Divisibility Tests
Test of divisibility for 2:
A whole number n is divisible by 2 if and only if
its last digit is divisible by 2 (i.e. even)
Test of divisibility for 5:
A whole number n is divisible by 5 if and only if
its last digit is divisible by 5 (i.e. 0 or 5)
Divisibility Tests
Test of divisibility for 4:
A whole number n is divisible by 4 if and only if
the number represented by its last two digits is divisible by 4.
Examples:
21732 is divisible by 4 because 32 is divisible by 4.
Note that neither the digit 3 nor 2 is divisible by 4. It is the
number 3×10+2 that is divisible by 4.
Hence it is wrong to say that the last two digits are divisible
by 4.
44442 is not divisible by 4 because 42 is not.
Divisibility Tests
Test of divisibility for 8:
A whole number n is divisible by 8 if and only if
The number represented by its last three digits is
divisible by 8.
Examples:
201432 is divisible by 8 because 432 is divisible by 8,
716510 is not divisible by 8 because 510 is not
divisible by 8
Divisibility Tests
Test of divisibility for 3:
A whole number n is divisible by 3 if and only if
the sum of its digits is divisible by 3.
Example: 71653092 is divisible by 3 because
7 +1 + 6 + 5 + 3 + 0 + 9 + 2 = 33
Test of divisibility for 9:
A whole number n is divisible by 9 if and only if
the sum of its digits is divisible by 9.
Divisibility Tests
Test of divisibility for 11:
A whole number n is divisible by 11 if and only if
the alternate sum of its digits is divisible by 11.
Examples:
Let’s first look at all 2-digit multiples of 11,
11, 22, 33, 44, 55, 66, 77, 88, 99
The difference of the two digits is 0, hence divisible by
11.
Divisibility Tests
Test of divisibility for 11:
A whole number n is divisible by 11 if and only if
the alternate sum of its digits is divisible by 11.
Examples:
3-digit multiples of 11
121, 132, 154, 165, …,
957, 968, 979, 990.
You should see that
1st digit – 2nd digit + 3rd digit
is divisible by 11.
Divisibility Tests
Test of divisibility for 11:
A whole number n is divisible by 11 if and only if
the alternate sum of its digits is divisible by 11.
More examples:
72952 is divisible by 11 because
7 – 2 + 9 – 5 + 2 = 11, which is divisible by 11.
56823 is not divisible by 11 because
5 – 6 + 8 – 2 + 3 = 8, which is not divisible by 11.
Greatest Common Factor (GCF)
Definition:
The GCF of two whole numbers a and b is the largest whole
number c that can divide into both a and b.
Methods for finding GCF(a, b)
(I) Set intersection method –
depends on listing all factors of a and b.
Greatest Common Factor (GCF)
Definition:
The GCF of two whole numbers a and b is the largest whole
number c that can divide into both a and b.
Methods for finding GCF(a, b)
(I) Set intersection method –
depends on listing all factors of a and b.
example: to find the GCF(12, 18)
Greatest Common Factor (GCF)
Definition:
The GCF of two whole numbers a and b is the largest whole
number c that can divide into both a and b.
Methods for finding GCF(a, b)
(I) Set intersection method –
depends on listing all factors of a and b.
example: to find the GCF(12, 18)
factors of 12: 1, 2, 3, 4, 6, 12.
Greatest Common Factor (GCF)
Definition:
The GCF of two whole numbers a and b is the largest whole
number c that can divide into both a and b.
Methods for finding GCF(a, b)
(I) Set intersection method –
depends on listing all factors of a and b.
example: to find the GCF(12, 18)
factors of 12: 1, 2, 3, 4, 6, 12.
factors of 18: 1, 2, 3, 6, 9, 18.
Greatest Common Factor (GCF)
Definition:
The GCF of two whole numbers a and b is the largest whole
number c that can divide into both a and b.
Methods for finding GCF(a, b)
(I) Set intersection method –
depends on listing all factors of a and b.
example: to find the GCF(12, 18)
factors of 12: 1, 2, 3, 4, 6, 12.
factors of 18: 1, 2, 3, 6, 9, 18.
Clearly the red numbers are the common factors and
6 is the largest,  GCF(12, 18) = 6
Greatest Common Factor (GCF)
Methods for finding GCF(a, b)
(method I is straight forward and easy to learn but slow for larger numbers)
(II) Factorization method –
depends on the complete factorization of a and b.
example: to find the GCF(24, 180)
24 = 2×2×2×3,
180 = 2×2×3×3×5
and by the “Greedy algorithm”, we pick all the prime
factors common to both numbers (including multiplicities)
 GCF(24, 180) = 2×2×3
(method II is still difficult to use if the numbers are too large and difficult
to factorize.)
(III) Euclidean Algorithm –
depends on reducing large numbers to smaller ones.
Theory: if a > b, then GCF(a, b) = GCF(a - b, b)
in other words, we can reduce the larger number by
subtracting it with the smaller one, without changing
the GCF.
(click to scroll up)
(method II is still difficult to use if the numbers are too large and difficult
to factorize.)
(III) Euclidean Algorithm –
depends on reducing large numbers to smaller ones.
Theory: if a > b, then GCF(a, b) = GCF(a - b, b)
in other words, we can reduce the larger number by
subtracting it with the smaller one, without changing
the GCF.
(III) Euclidean Algorithm –
depends on reducing large numbers to smaller ones.
Theory: if a > b, then GCF(a, b) = GCF(a - b, b)
in other words, we can reduce the larger number by
subtracting it with the smaller one, without changing
the GCF.
Example:
GCF(481, 296) = GCF(481 – 296, 296)
= GCF(185, 296)
= GCF(185, 296 – 185)
= GCF(185, 111)
= GCF(74, 111)
= GCF(74, 37)
= GCF(37, 37)
= 37
Lowest Common Multiple (LCM)
Definition:
The LCM of two whole numbers a and b is the smallest
whole number c that is divisible by both a and b.
Methods for finding LCM(a, b)
(I) Set intersection method –
depends on listing small multiples of a and b.
example: to find the LCM(15, 24)
multiples of 15:
multiples of 24:
Lowest Common Multiple (LCM)
Definition:
The LCM of two whole numbers a and b is the smallest
whole number c that is divisible by both a and b.
Methods for finding LCM(a, b)
(I) Set intersection method –
depends on listing small multiples of a and b.
example: to find the LCM(15, 24)
multiples of 15: 15, 30, 45, 60, 75, 90, 105,
multiples of 24: 24, 48, 72, 96, 120,
Lowest Common Multiple (LCM)
Definition:
The LCM of two whole numbers a and b is the smallest
whole number c that is divisible by both a and b.
Methods for finding LCM(a, b)
(I) Set intersection method –
depends on listing small multiples of a and b.
example: to find the LCM(15, 24)
multiples of 15: 15, 30, 45, 60, 75, 90, 105, 120.
multiples of 24: 24, 48, 72, 96, 120,
Lowest Common Multiple (LCM)
Definition:
The LCM of two whole numbers a and b is the smallest
whole number c that is divisible by both a and b.
Methods for finding LCM(a, b)
(I) Set intersection method –
depends on listing small multiples of a and b.
example: to find the LCM(15, 24)
multiples of 15: 15, 30, 45, 60, 75, 90, 105, 120.
multiples of 24: 24, 48, 72, 96, 120,
Therefore LCM(15, 24) = 120.
Lowest Common Multiple (LCM)
Methods for finding LCM(a, b)
(II) Factorization method –
a “thrifty” algorithm
example: to find the LCM(875, 1225)
875 = 5×5×5×7
1225 = 5×5×7×7
Analogy: Your math teacher requires you to bring 3 pencils and 1
highlighter to class, your History teacher requires you to bring 2
pencils and 2 highlighters. What is the minimum set of pens you
need to bring if you have both classes in one day?
Ans: 3 pencils and 2 highlighters.
Lowest Common Multiple (LCM)
Methods for finding LCM(a, b)
(II) Factorization method –
a “thrifty” algorithm
example: to find the LCM(875, 1225)
875 = 5×5×5×7
1225 = 5×5×7×7
Analogy: Your math teacher requires you to bring 3 pencils and 1
highlighter to class, your History teacher requires you to bring 2
pencils and 2 highlighters. What is the minimum set of pens you
need to bring if you have both classes in one day?
Ans:
3 pencils and
2 highlighters.
 LCM(875,
1225)
= 5×5×5×7×7
Lowest Common Multiple (LCM)
Methods for finding LCM(a, b)
(II) Factorization method –
Another example: to find the LCM(60, 126)
60 = 2×2×3×5
126 = 2×3×3×7
Answer: 2×2×3×3×5×7
Lowest Common Multiple (LCM)
Methods for finding LCM(a, b)
(III) “Mechanical method” – using a formula
ab
LCM (a, b) =
GCF (a, b)
Example:
Find the LCM of 481 and 296.
Answer: we have calculated before that GCF(481, 296) = 37,
therefore
LCM(481, 296) = (481×296) ÷ 37 = 3848
Lowest Common Multiple (LCM)
Example:
Your neighbor has two dogs - one named Sparky and one
named Skippy. They both like to bark and both have a
pattern. Sparky will bark for a while every 15 minutes once
started, and Skippy does the same every 18 minutes.
One night they both started barking at 9pm because a cat
passed by. When did they bark together again that night?