PRIME NUMBERS 1/3

1. PRIME NUMBERS

What do the numbers 2, 3, 5, and 7 have in common? They are the first four prime numbers. A prime number is a number that has no exact divisor other than itself and the number 1. Numbers that are not prime are called composite. Clearly, 2 is the only even prime. Also, the number 1 is considered neither prime nor composite. In this way, we can group the natural numbers into three sets of numbers. The first group is the prime numbers (A), the second is the composite numbers ( B ), and the third ( C ) consists of only a single element—the number 1 since it is neither a prime number nor a composite number.
Let’s divide the numbers 1-30 into the three groups:
A (prime numbers) = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29} B (composite numbers) = {4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30} C = {1}
If you want to check to see if a number is prime or not, you must find its divisors. In this discussion, when we use the term “divisors” we shall mean “exact divisors.” If the only divisors are 1 and the number itself, then the number is a prime number. The search is made easier for you if you know some basic rules:

DIVISOR RULE
2 if the last digit is 0, 2, 4, 6 or 8
3 if the sum of it's digits can be divided by 3 evenly
4 if the number’s last two digits can be divided by 4 evenly
5 if the last digit is 0 or 5
7 if after subtraction of a number consisting of the last three digits from a number consisting of the rest of its digits the product is a number that can be divided by 7 evenly*
8 if the number’s last three digits can be divided by 8 evenly
9 if the sum of the digits can be divided by 9 evenly
10 if the last digit is 0
11 if, after subtraction of the sum of digits in odd places from the sum of digits in even places, you get a number that can be divided exactly by 11*

*Through the years, many different ways to test divisibility by seven have been devised. Some are long and complex, a few involve rewriting the digits, and one even consists of a grid-like box. We have chosen one of the more simplistic versions even though in almost every case it is quicker to merely perform long division. An example—582113 is divisible by 7 because 582-113=469 and 469/7=67.

**Another way of describing this divisibility test is to take the units digit minus the tens digit plus the hundreds digit, minus the thousands digit…etc and if this result is a number that can be divided by 11 evenly, then the original number is divisible by 11 as well.

While most of these divisibility rules are familiar, with the aid of a calculator, it is relatively easy to verify the divisors of a given number. A typical question asked by a student is, “If we can use a calculator, why must we learn such rules?” The answer is simple: by knowing a few of these little tricks, you will find that the search for divisors becomes quicker and easier. Many card games, magic tricks and other brain teasers are rooted in number theory and the basis for understanding many of these is the divisibility property of integers. Here's a quick little problem you can try on your friends:

Ask your friend to write his age three times (e.g., 131313). Challenge him to find a number that would divide evenly into it. Then, prove to him that it is divisible by seven. This trick will work for any two-digit age. (Why is this so?)

So, given a number n, how do we determine if it is prime or composite? If it is composite, what are all of its divisors? Do you have to begin by checking every number? Is there a secret to this madness? Well, actually, there is. You don’t have to check all divisors smaller than the number. You only need to test numbers smaller than . Now determine which of these numbers is prime:
25415, 10007, 45603, 22307, 13587