# PRIMES AND DIVISIBILITY: PRACTICE PROBLEMS

1) True or False? If false, then correct with a similar
statement. (In this

problem, as sume 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^{2}.

(d) The general form for a multiple of three is 2a + 1.

(e) If 2|a and 5|b, then a^{2}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^{2}|a^{3}.

(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 re present the relationship between the fol lowing 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^{100}?

(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.