PRIMES AND DIVISIBILITY: PRACTICE PROBLEMS

1) True or False? If false, then correct with a similar statement. (In this
problem, assume that variables stand for natural numbers.)

(a) If n is even, then n/2 is even.
(b) If n is even, then 4|2n.
(c) If n is even, then 4|n².
(d) The general form for a multiple of three is 2a + 1.
(e) If 2|a and 5|b, then a²b is a multiple of 50.
(f) The sum of two odd numbers is never a multiple of three.
(g) If 3|a and 7|b, then 10|a + b.
(h) If 3|a and 9|b, then 3|a + b.
(i) The sum of any three consecutive numbers is divisible by three.
(j) The product of any three consecutive numbers is divisible by six.
(k) If c|ab, then c|a or c|b.
(l) If d|a, then d²|a³.
(m) The square of any odd number leaves remainder 1 when you divide it
by 8.
(n) The least common multiple of a and b always divides ab.

(2) Is 101 prime? Explain how to check this efficiently.

(3) (Venn diagrams and divisibility) For each of the following, use a Venn-type
diagram to efficiently represent the relationship between the following kinds
of number.

(a) Multiples of 2, Multiples of 3, Multiples of 6
(b) Multiples of 8, Multiples of 6, Multiples of 5
(c) Multiples of 4, Multiples of 16, Multiples of 64
(d) Multiples of 15, Multiples of 25
(What is a description of the intersection?)

(4) Any four digit palindrome ( like 1331 or 2772) is divisible by 11. Why? Is
it true for five- or six-digit palindromes?

(5) Give the prime factorization of each of the following numbers: 48, 100, 66,
504.

(6) Devise and justify a divisibility rule for the following numbers: 18, 24, 25
in base 10; 2 and 4 in base 5; 3 in base 12. Give some examples of easy
divisibility rules in other bases.

(7) Give an example of a number with exactly five divisors. Give an example
of a number with exactly 100 divisors.

(8) Find the smallest natural number that is divisible by all of the numbers up
to 10. How else could this question have been worded?

(9) What is the smallest composite number that is not divisible by 2, 3, 5, or
7?

(10) What is the ones digit of 7¹⁰⁰?

(11) Find the gcd and lcm of the following pairs: (30, 75), (20, 40), (105, 132), (902, 908).
(You don’t have to simplify your answer .)

(12) The gcd of two numbers is 18. Their lcm is 630. What are the two numbers?

(13) * Suppose there is a row of one million pennies, all with the heads side
facing up. Now someone goes through and flips over every second coin
(that is, the ones numbered 2, 4, 6, and so on are flipped to the tails side).
Now someone goes through and flips over every third coin (so they turn
over 3, 6, 9, and so on: now 3 is tails up but 6 is turned back to heads
up). This process is continued for every divisor from two to a million. Will
the coin numbered 2008 be heads up or tails up at the end of the process?
Which coins are heads up?

(14) * Find five consecutive composite numbers over 1000. Give a method for
finding ten consecutive composite numbers.