What are prime and compositenumbers?
Prime numbersare positive integers (natural numbers) that are greater than 1 and
have only 1 and the prime number as divisors (factors). Another way to define a prime
number is an integer greater than 1 in which its only positive divisors are 1 and itself.
For example, prime numbers less than 20 are 2, 3, 5, 7, 11, 13, 17, and 19. All other
integers greater than 1 that are not prime are called composite numbers.
There are other rules: The number 1 is unique, and is not considered a prime or
composite number. And one of the basic theorems of arithmetic is that any positive inte-
ger is either a prime or the product of a unique set of prime numbers. For example, the
number 12 is not a prime, but it has a unique “prime calculation” written as: 2 2 3.
What is the Sieve of Eratosthenes?
The smallest prime numbers—those less than 1 million—can be determined using
something invented circa 240 BCE: the Sieve of Eratosthenes. This method was named
after astronomer and mathematician Eratosthenes of Cyrene (276–196 BCE), who was
actually more famous for calculating the circumference of the Earth than for his work
with prime numbers.
To determine primes using this method, make a list of all the integers less than or
equal to n(numbers greater than 1) and get rid of all the multiples of all primes less
than or equal to the square root of n. The numbers that are left are all primes. For
example, to determine primes less than 100, start with 2 as the first prime; then write
all odd numbers from 3 to 100 (there is no need to write the even numbers). Take 3 as
the first prime and cross out all its multiples in the numbers you listed. Take the next
number, 5, and then 7, and cross out all their multiples. By the time you reach 11,
many numbers will be eliminated and you will have reached a number greater than
the square root of 100 (11 is greater than 10, the square root of 100). Thus, all the
numbers you have left will be primes. 83
MATH BASICS
What are some examples of “clock arithmetic”?
A
s stated above, the clock would be considered arithmetic modulo, with cal-
culations including such statements as shown below. (Note: In all of the first
calculations, the equal sign can be replaced with the congruence sign , or
three lines instead of the two for an equal sign.)11 1 0, also written as 11 1 0 (mod 12)
7 8 3, also written as 7 8 3 (mod 12)
5 7 11, also written as 5 7 11 (mod 12)