Prime Numbers

    From a certain point of very, the prime numbers are the building blocks for the integers; that is to say, every integer greater than 1 has a prime factor. Indeed, every positive integer is a product of primes. This result was known to the ancient Greeks and is sometimes referred to as Euclid’s lemma. One of the first questions that comes to mind is: "how many prime numbers are there?" or maybe even "why are primes so important to talk about?".  What about these questions, "without using trial division, how can one determine whether a given integer is prime or composite?", "is it possible for given a function to find all the prime numbers?", "are there arbitrarily long sequences of integers, all of which are not primes?". These simple questions have kept mathematicians busy for thousands of years.
    One of the first methods: the sieve of Eratosthenes is well known, simple to understand, but not very practical. The idea is to list all positive integers less than a given positive integer; then passing over 1, we find a prime number and then cross out all of the multiples of this prime number. For example, 2 is prime but every even number is not and so cross all even numbers off the list. Next, 3 is prime and so cross out every multiple of three, because they are not prime. Continue in this fashion, and then the numbers left are the prime numbers. Of course this is not practical if your time is limited. Since the time of Eratosthenes, sophisticated versions of this algorithm have achieved new results.
    This topic is a brief introduction to prime numbers, composite numbers, the sieve of Eratosthenes, and gives one of the most beautiful theorems in all of mathematics: Euclid’s proof of the infinitude of the primes. There are many proofs of this result, but Euclid's proof remains popular because of its simplicity and elegance.

Definition (Prime Number) A prime number is a positive integer greater than 1 that is divisible by no positive integers other than 1 and itself.

Definition (Composite Number) A positive integer greater than 1 that is not prime is called a composite number.

Example (Sieve of Eratosthenes) Using the sieve of Eratosthenes, find the prime numbers less than 100.

    Solution.    
    


The idea, passing over 1,  is to find a prime number and then cross out all of the multiples of this prime number. For example, 2 is prime but every even number is not and so cross all even numbers off the list. Next, 3 is prime and so cross out every multiple of three, because they are not prime. Continue in this fashion, and then the numbers left are the prime numbers. Of course for a given large integer this is not practical, if your time is limited. Since the time of Eratosthenes, sophisticated versions of this algorithm have achieved new results.
    Consider the first 5 rows in the above array. In the first 5 rows there are 16 primes, and in the last five rows there are only 10 prime numbers. If one carries out the  sieve of Eratosthenes between 10,000 and 10,050, you will find that there are just 4 prime numbers. Can you find 5 rows where there are no prime numbers? What is the last prime number?

    One of the first questions that comes to mind is: How many prime numbers are there? or maybe even "why are primes so important to talk about? From a certain point of view, the prime numbers are the building blocks for all the integers. That is to say, every integer greater than 1 has a prime factor. This result was known to the ancient Greeks and is sometimes referred to as Euclid’s lemma.

Proposition (Prime Divisor) Every positive integer greater than 1 has a prime divisor.

    Proof. Assume (for a contradiction) that there exists an integer greater than 1 that does not have a prime divisor. Then since the set of all integers greater than 1 without a prime divisor is nonempty, the Well-Ordering Principle states that this set must have a least positive integer, say that does not have a prime divisor and is greater than 1. Since does not have a prime divisor and divides , must not be prime. Thus, and since must have a prime divisor and similarly for Therefore, must have a prime divisor. This contradiction, leads us to the desired conclusion that every integer greater than 1 must have a prime divisor.

Proposition (Infinitude of Primes) There are infinitely many primes.

    Proof. Assume that the prime numbers are listed in ascending order with and so on; and assume (for a contradiction) that is the last prime. Consider the integer,



Since every positive integer greater than 1 has a prime divisor, has a prime divisor, say However, can not divide since is of the form, Therefore, , the last prime number cannot exist.

    The above proof can be found in Euclid's The Elements. Many people believe it to be one of the most beautiful proofs in all of mathematics.

Proposition (Bounding Factors) If is a composite integer, then has a prime factor not exceeding

    Proof. Since is composite, we can write where and are integers with We must have since otherwise and Since must have a prime divisor, which is also a prime divisor of and is clearly less than or equal to   we have thus shown has a prime factor not exceeding

• print this page
• pages linking here
• related pages

Cite this as:
Prime Numbers
Published by Library of Math -- Online math organized by subject into topics.
Written by Smith, David A.
http://www.libraryofmath.com/prime-numbers.html