A prime number is a natural number greater than 1 that has no positive integer divisors other than 1 and itself. For example, 5 is a prime number because it has no positive divisors other than 1 and 5.
The first 49 prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, and 227.
In contrast to prime numbers, a composite number is a positive integer greater than 1 that has more than two positive divisors. For example, 4 is a composite number because it has three positive divisors: 1, 2, and 4. All positive integers greater than 1 are either prime or composite. 1 is the only positive integer that is neither prime nor composite.
Prime numbers are critical for the study of number theory. Nearly all theorems in number theory involve prime numbers or can be traced back to prime numbers in some way. Prime numbers are also important for the study of cryptography. The RSA method of encryption relies upon the factorization of a number into primes. Finally, prime numbers have applications in essentially all areas of mathematics. Prime numbers act as "building blocks" of numbers, and as such, it is important to understand prime numbers to understand how numbers are related to each other.
Main Article: Fundamental Theorem of Arithmetic
See Also: Prime Factorization
The fundamental theorem of arithmetic separates positive integers into two classifications: prime or composite.
Fundamental Theorem of Arithmetic
Every integer greater than 1 is either prime (it has no divisors other than 1 and itself) or composite (it has more than two divisors). Furthermore, every integer greater than 1 has a unique prime factorization up to the order of the factors.
The prime factorization of a positive integer is that number expressed as a product of powers of prime numbers. Prime factorizations are often referred to as unique up to the order of the factors. This means that each positive integer has a prime factorization that no other positive integer has, and the order of factors in a prime factorization does not matter.
Give the prime factorization of 48.
48 is divisible by the prime numbers 2 and 3. The highest power of 2 that 48 is divisible by is The highest power of 3 that 48 is divisible by is Thus, the prime factorization of 48 is
The fundamental theorem of arithmetic guarantees that no other positive integer has this prime factorization.
Prime factorization is the primary motivation for studying prime numbers. Many theorems, such as Euler's theorem, require the prime factorization of a number. Prime factorization can help with the computation of GCD and LCM. Prime factorization is also the basis for encryption algorithms such as RSA encryption. In order to develop a prime factorization, one must be able to efficiently and accurately identify prime numbers.
The simplest way to identify prime numbers is to use the process of elimination. List out numbers, eliminate the numbers that have a prime divisor that is not the number itself, and the remaining numbers will be prime. This process can be visualized with the sieve of Eratosthenes.
Another way to Identify prime numbers is as follows:
- First, choose a number, for example, 119.
- Now, note that prime numbers between 1 and 10 are 2, 3, 5, 7. (Why between 1 and 10? This question is answered in the theorem below.) Divide the chosen number 119 by each of these four numbers.
- If it's divisible by any of the four numbers, then it isn't a prime number; if it's not divisible by any of the four numbers, then it is prime.
- 119 is divisible by 7, so it is not a prime number.
Fortunately, one does not need to test the divisibility of each smaller prime to conclude that a number is prime. The number of primes to test in order to sufficiently prove primality is relatively small.
If is a composite number, then it must be divisible by a prime such that
Proof by Contradiction:
Suppose that is a composite number, and it is only divisible by prime numbers that are greater than Let two of its factors be and with Then where is a positive integer. However, if and are both greater than then This cannot be true, because and is a positive integer. Thus, must be divisible by a prime that is less than or equal to
One can apply divisibility rules to efficiently check some of the smaller prime numbers. Long division should be used to test larger prime numbers for divisibility. It is helpful to have a list of prime numbers handy in order to know which prime numbers should be tested.
Is 211 a prime number?
If 211 is a prime number, then it must not be divisible by a prime that is less than or equal to is between 14 and 15, so the largest prime number that is less than is 13. It is therefore sufficient to test 2, 3, 5, 7, 11, and 13 for divisibility. 211 is not divisible by any of those numbers, so it must be prime.
What is the sum of the two largest two-digit prime numbers?
If a two-digit number is composite, then it must be divisible by a prime number that is less than or equal to Therefore, it is sufficient to test 2, 3, 5, and 7 for divisibility.
- 99 is divisible by 3;
- 98 is divisible by 2;
- 97 is not divisible by 2, 3, 5, or 7, implying it is the largest two-digit prime number;
- 96 is divisible by 2;
- 95 is divisible by 5;
- 94 is divisible by 2;
- 93 is divisible by 3;
- 92 is divisible by 2;
- 91 is divisible by 7;
- 90 is divisible by 2;
- 89 is not divisible by 2, 3, 5, or 7, implying it is the second largest two-digit prime number.
The sum of the two largest two-digit prime numbers is
What is the largest 3-digit prime number?
If a a three-digit number is composite, then it must be divisible by a prime number that is less than or equal to is between 31 and 32, so it is sufficient to test all the prime numbers up to 31 for divisibility.
Counting backward, we have the following:
- 999 is the largest 3-digit number, but as it is divisible by , it is not prime.
- 998 is the second largest 3-digit number, but as it is divisible by , it is not prime.
- 997 is not divisible by any prime number up to so it must be prime.
Which prime number follows 1997?
1998 is divisible by 2.
If 1999 is composite, then it must be divisible by a prime number that is less than or equal to . is between 44 and 45, so the possible prime numbers to test are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, and 43. 1999 is not divisible by any of those numbers, so it is prime.
Sometimes, testing a number for primality does not involve exhaustively searching for prime factors, but instead making some clever observation about the number that leads to a factorization. The next couple of examples demonstrate this.
In the following sequence, how many prime numbers are present?
So, no numbers in the given sequence are prime numbers.
How many numbers in the following sequence are prime numbers?
We have the following factorization:
- has no factors other than 1 and itself. So, it is a prime number.
So, there is only prime number in the given sequence.
Is 12345 a prime number?
We have So 12345 is divisible by 5 and therefore is not prime.
Main Article: Primality Testing
There are other methods that exist for testing the primality of a number without exhaustively testing prime divisors. These methods are called primality tests. One of these primality tests applies Wilson's theorem.
A positive integer is prime if and only if
Show that 7 is prime using Wilson's theorem.
Therefore, 7 must be prime.
Testing primes with this theorem is very inefficient, perhaps even more so than testing prime divisors. However, this theorem does give insight that a number's primality is not linked purely to the divisors of that number. There are other "traces" in a number that can indicate whether the number is prime or not.
Most primality tests are probabilistic primality tests. These kinds of tests are designed to either confirm that the number is composite, or to use probability to designate a number as a probable prime. A probable prime is a number that has been tested sufficiently to give a very high probability that it is prime. An example of a probabilistic prime test is the Fermat primality test, which is based on Fermat's little theorem.
Fermat Primality Test
Given a positive integer
- Choose a positive integer at random that is coprime to .
- Compute If the result is not then is composite. Otherwise, may or may not be prime. If the result is at this step, but is composite, then is pseudoprime to base
- Repeat these steps any number of times. Each repetition of these steps improves the probability that the number is prime. However, this process can never guarantee that a number is prime. A composite number that gets a result of in the second step for all less than is called a Carmichael number.
Show that 91 is composite using the Fermat primality test with the base .
The goal is to compute
Use the method of repeated squares. Compute 90 in binary:
Compute the residues of the repeated squares of 2:
The result is not Therefore, is not prime.
This process might seem tedious to do by hand, but a computer could perform these calculations relatively efficiently. Thus, the Fermat primality test is a good method to screen a large list of numbers and eliminate numbers that are composite. Then, a more sophisticated algorithm can be used to screen the prime candidates further.
In general, identifying prime numbers is a very difficult problem. This, along with integer factorization, has no algorithm in polynomial time. In fact, it is so challenging that much of computer cryptography is built around the fact that there is no known computationally feasible way to find the factors of a large number.
Main Article: Distribution of Primes
See Also: Infinitely Many Primes
It has been known for a long time that there are infinitely many primes. However, the question of how prime numbers are distributed across the integers is only partially understood. The prime number theorem gives an estimation of the number of primes up to a certain integer.
Prime Number Theorem
Let be the prime counting function. For any real number gives the number of prime numbers that are less than or equal to Then
This implies that for sufficiently large
There are many open questions about prime gaps. A prime gap is the difference between two consecutive primes. For example, the prime gap between 13 and 17 is 4. Bertrand's postulate gives a maximum prime gap for any given prime.
For any integer there always exists at least one prime number such that
This implies that for the prime number, the next consecutive prime number is subject to
This is, unfortunately, a very weak bound for the maximal prime gap between primes. Prime gaps tend to be much smaller, proportional to the primes. For example, the first occurrence of a prime gap of at least 100 occurs after the prime 370261 (the next prime is 370373, a prime gap of 112).
The most famous problem regarding prime gaps is the twin prime conjecture. This conjecture states that there are infinitely many pairs of primes for which the prime gap is 2, but as of this writing, no proof has been discovered.
Another famous open problem related to the distribution of primes is the Goldbach conjecture. This conjecture states that every even integer greater than 2 can be expressed as the sum of two primes.
One of the most significant open problems related to the distribution of prime numbers is the Riemann hypothesis. Although the Riemann hypothesis has wide-reaching implications in number theory, Riemann's original motivation for formulating the conjecture was to better understand the distribution of prime numbers. The Riemann hypothesis relates the real parts of the zeros of the Riemann zeta function to the oscillations of the prime numbers about their "expected" positions given the estimation of the prime counting function above.
Main Article: Mersenne Primes
A Mersenne prime is a prime that can be expressed as where is a prime number.
The first five Mersenne primes are listed below:
Note that having the form of does not guarantee that the number is prime. is not a prime number; its prime factorization is
From the list above, it might seem as though Mersenne primes are relatively easy to find by simply plugging in prime numbers into . However, Mersenne primes are exceedingly rare. As of January 2018, only 50 Mersenne primes are known, the largest of which is . This number is also the largest known prime number. In fact, many of the largest known prime numbers are Mersenne primes. This is due to the Lucas-Lehmer primality test, which is an efficient algorithm that is specific to testing primes of the form . Although Mersenne primes continue to be discovered, it is an open problem whether or not there are an infinite number of them.
Another notable property of Mersenne primes is that they are related to the set of perfect numbers. A perfect number is a positive integer that is equal to the sum of its proper positive divisors. Each Mersenne prime corresponds to an even perfect number:
Let be a Mersenne prime. Then is an even perfect number. Furthermore, all even perfect numbers have this form.
Give the perfect number that corresponds to the Mersenne prime 31.
The perfect number is given by the formula above:
This number can be shown to be a perfect number by finding its prime factorization:
Then listing out its proper divisors gives
Summing these divisors, we have
One of the most fundamental theorems about prime numbers is Euclid's lemma.
Let be prime. If , then or .
Suppose does not divide . Since the only divisors of are and and doesn't divide we must have By Bezout's identity, there exist some and such that . Multiplying both sides of this equation by gives . Now divides since it is given that and also divides . Therefore, divides their sum, which is . Without loss of generality, if does not divide then it must divide
Euclid's lemma can seem innocuous, but it is incredibly important for many proofs in number theory. For example, it is used in the proof that the square root of 2 is irrational.
GCD and LCM using Prime Factorizations
Given positive integers and let their prime factorizations be given by
where are distinct primes and each and are integers.
Then the GCD of these integers is given by
and the LCM of these integers is given by
Using prime factorizations, what are the GCD and LCM of 36 and 48?
The prime factorizations are
Each number has the same primes, 2 and 3, in its prime factorization. The GCD is given by taking the minimum power for each prime number:
The LCM is given by taking the maximum power for each prime number:
Prime numbers are important for Euler's totient function.
Given a positive integer , Euler's totient function, denoted by gives the number of positive integers less than that are co-prime to
Listing out the positive integers that are less than 10 gives
Of those numbers, list the subset of numbers that are co-prime to 10:
This set contains 4 elements. Therefore,
If is a power of a prime, then Euler's totient function can be computed efficiently using the following theorem:
For any given prime and positive integer ,
Then, the value of the function for products of coprime integers can be computed with the following theorem:
Given co-prime positive integers and ,
The consequence of these two theorems is that the value of Euler's totient function can be computed efficiently for any positive integer, given that integer's prime factorization.
The prime factorization of 48 is
Euler's totient function is critical for Euler's theorem.
Let and be coprime integers with . Then,
If is a prime number, then this gives Fermat's little theorem.
Fermat's Little Theorem
Let be a prime number and let be an integer coprime to Then,
The properties of prime numbers can show up in miscellaneous proofs in number theory.
Let be a prime number greater than . Prove that is always divisible by 6.
Any integer can be written in the form .
cannot be a prime.
may be a prime.
cannot be a prime.
cannot be a prime.
cannot be a prime.
may be a prime.
Thus, any prime can be represented in the form or .
can be factored to
If this is the case, which implies
If this is the case, which implies
One of the factors, or , will be divisible by . Thus, is always divisible by .
is the greatest prime number less than 50, and is the least prime number greater than 50. What is the value of
Let's work backward for .
is divisible by , and from the property of primes it is enough information to conclude that the number is not prime.
is divisible by so cancel it.
When we look at it doesn't have any divisor other than one and itself. So it is indeed a prime:
We use the same process in looking for .
is divisible by .
is divisible by .
doesn't have any other divisor other than one and itself, so it is indeed a prime:
Consider the expression where is an integer greater than What are the least two values of for which the expression doesn't produce a prime number?
Let's check by plugging in numbers in increasing order.
- is prime.
- is prime.
- , which is divisible by 3, so it isn't prime.
- is prime.
- , which is divisible by 7, so it isn't prime.
Therefore, the least two values of are 4 and 6.
An emirp (prime spelled backwards) is a prime number that results in a different prime when its decimal digits are reversed. This definition excludes the related palindromic primes. The term reversible prime may be used to mean the same as emirp, but may also, ambiguously, include the palindromic primes.
The sequence of emirps begins 13, 17, 31, 37, 71, 73, 79, 97, 107, 113, 149, 157, 167, 179, 199, 311, 337, 347, 359, 389, 701, 709, 733, 739, 743, 751, 761, 769, 907, 937, 941, 953, 967, 971, 983, 991, ... (sequence A006567 in the OEIS).
All non-palindromic permutable primes are emirps.
As of November 2009, the largest known emirp is 1010006+941992101×104999+1, found by Jens Kruse Andersen in October 2007.
The term 'emirpimes' (singular) is used also in places to treat semiprimes in a similar way. That is, an emirpimes is a semiprime that is also a (distinct) semiprime upon reversing its digits.