Chapter 3.
NUMBER THEORY
Summary
Definition: A prime number is a positive integer
that is divisible by exactly 2 positive integers: 1 and the
number itself. A composite number is a positive
integer that is divisible by some positive integer
besides 1 and the number itself.
Important: Fundamental Theorem of Arithmetic.
Every integer greater than 1 can be written as the
product of one or more primes in exactly one way
(disregarding the order of the prime in the product).
Definition: Let a and b be integers. We say that a is a
multiple of b if a equals b times some integer. In other
words, a is a multiple of b if there is an integer n such
that a = bn. If a is a multiple of b and b is nonzero, then
we say that b is a divisor, or factor, of a, and that a is
divisible by b.
Important: Let a, b, and c the numbers.
If a and b are multiples of c, then both a + b
and a – b are multiples of c.
If a is a multiple of b, then every multiple of a
is also a multiple of b.
We developed several useful divisibility tests:
Number Condition under which n is divisible by the
number
2 Units digit of n is 0, 2, 4, 6, or 8
3 Sum of the digits of n is a multiple of 3
4 Number formed by last two digits of n is a
multiple of 4
5 Units digits of n is 0 or 5
6 Divisible by 2 and by 3
8 Number formed by last three digits of n is
a multiple of 8
9 Sum of the digits of n is a multiple of 9
10 Units digit of n is 0
Important: To find the prime factorization of the least
common multiple of a group of numbers, we first find
the prime factorization of each of the numbers. The
prime factorization of the least common multiple is the
product of the highest power of each prime factor that
appears in the prime factorization of the numbers.
Important: We can find the greatest common divisor
of a group of numbers with the following process:
Step 1: Find the prime factorization of each
number.
Step 2: Identify the primes that appear in all of
the prime factorizations. If no primes appear in all of
the prime factorizations, then the greatest common
divisor of the numbers is 1.
Step 3: Among the prime factorizations, find the
smallest power of each prime from step 2.
Step 4: Multiply the powers of primes found in
Step 3.
Important: For any positive integers a, b, and n, we
have
lcm[na, nb] = n lcm[a, b],
gcd(na, nb) = n gcd(a, b).
Review Problems
3.47 Find the prime factorization of each of the
following numbers:
(a) 693
(b) 5423
(c) 35100
3.48 What is the remainder when (99)(237) is
divided by 9?
3.49 What is the sum of the two smallest
multiples of 6 that are greater than 103?
3.50 What is the largest multiple of 73 that is
less than 2000?
3.51 Which of the following numbers is
divisible by 9:
45,624 560,335 60,231,060
9,671,011?
3.52 Which one of the following four-digit
numbers is not divisible by 4: 2544, 2554,
2564, 2572, or 2576?
3.53 We learned that a number is divisible by
5 if its units digit is 0 or 5. What is a similar rule
that we can use to test if a number is divisible by
25?
3.54 Amanda arranges the digits 1, 3, 5, and 7
to write a four-digit number. The 7 is next to the
1 but not to the 5. The 3 is next to the 7 but not
to the 5. The four-digit number is divisible by 5.
What is Amanda’s four-digit number?
3.55 Compute each of the following:
(a) lcm[26, 65]
(b) lcm[96, 72]
(c) lcm[16, 21, 28]
(d) lcm[45, 60, 75]
3.56 Compute each of the following:
(a) gcd(45, 75)
(b) gcd(144, 405)
(c) gcd(238, 374)
(d) gcd(970, 485, 1330)
3.57 If the 4-digit number 7,2d2 is divisible by
6, then what is the largest possible value of the
digit d?
3.58 Which of the following numbers is not
divisible by 8:
8,024 168,640 8,648,034
720,032 64,856?
3.59 What is the units digit (ones digit) of the
product of any six consecutive positive integers?
3.60 What is the smallest prime factor of 117
+ 75?
3.61 If 12 is a factor of n, what other positive
numbers must be factors of n?
3.62 What is the greatest odd factor of 12,024
?
3.63 How many positive integers less than 20
have exactly two positive divisors?
3.64 If x, y, and z are integers such that
2x3y7z = 392, then what is xyz?
3.65 The number 206,496 is divisible by each
2, 3, 6, and 8. What is the next larger integer that
is divisible by 2, 3, 6, and 8?
3.66 A positive integer is 3 more than a
multiple of 4, and 4 more than a multiple of 5.
What is the least integer it could be?
3.67 A light flashes every 1 minute 15
seconds. Another flashes every 1 minute 40
seconds. Suppose they flash together at a certain
time. What is the shortest amount of time that
will elapse before both lights will again flash
together?
3.68 What is the difference between the
greatest positive factor of 121 and the least
positive factor of 6?
3.69 The number 6545 can be written as a
product of a pair of positive two-digit integers.
What are these two integers?
3.70 In the sequence 1, 7, 13, 19, …, each
number is 6 more than the number before it. In
the sequence 1, 9, 17, 25, …, each number is 8
more than the number before it. The two
sequences have infinitely many numbers in
common. Find the sum of the first three common
numbers.
3.71 Let a and b be the positive integers such
that a is a divisor of b.
(a) What is the greatest common divisor of a and
b?
(b) What is the least common multiple of a and
b?
Challenge Problems
3.72 When the six-digit number 3456n7 is
divided by 8, the remainder is 5. List both
possible value of the digit n.
3.73 If two positive integers have a greatest
common divisor of 1 and a least common
multiple of 57, what are the possible values of
the larger of the two integers?
3.74 What is the largest multiple of 12 that
can be written using each digit 0, 1, 2, …, 9
exactly once?
3.75 The four-digit number A55B is divisible by
36. What is the sum of A and B?
3.76 The number A4273B is a six-digit integer
in which A and B are digits, and the number is
divisible by 72. Find the value of A and the value
of B.
3.77 Find the largest factor of 2520 that is not
divisible by 6.