Arithmetics- Understanding Prime Numbers

Prime Number

Much of the theory of numbers is devoted to the study of primes. A number p (p≠ ±1) is a prime if its only divisors are ±1, ±p. A number a is composite if a = bc, in which neither b nor c is ±1. The first ten positive primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29; the first ten positive composite numbers are 4, 6, 8, 9, 10, 12, 14, 15, 16, 18. A composite number can be factored into a product of primes in only one way, apart from the order of the factors; thus, 9 = 3 × 3; 10 = 2 × 5; 12 = 2 × 2 × 3.

The ninth book of the Elements by the Greek mathematician Euclid contains the proof of the proposition that the number of primes is infinite; that is, no largest prime exists. The proof is remarkably simple: let p be a prime and q = 1 × 2 × 3 × ... × p + 1; that is, one more than the product of all the integers from 1 through p. The integer q is larger than p and is not divisible by any integer from 2 through p, inclusive. Any one of its positive divisors, other than 1, and any one of its prime divisors, therefore, must be larger than p. It follows that there must be a prime larger than p.

Although the number of primes is infinite, the primes become relatively scarce as one proceeds further and further out into the number system. Indeed, the number of primes between 1 and n, for very large values of n, is approximately n divided by the natural logarithm of n. Twenty-five percent of the numbers between 1 and 100, 17 percent of the numbers between 1 and 1000, and 7 percent of the numbers between 1 and 1,000,000 are primes.

Two primes that differ by 2 (for example, 5, 7; 17, 19; 101, 103) are called twin primes. It is not known whether the number of twin primes is infinite. Another conjecture is that every even number greater than 2 can be expressed as the sum of two primes; thus, 4 = 2 + 2; 6 = 3 + 3; 8 = 3 + 5; 10 = 5 + 5; 20 = 3 + 17; 100 = 3 + 97; however, a general proof is still lacking.

The greatest common divisor of two integers a and b is the largest positive integer that divides both a and b exactly. Euclid gave a method for finding this greatest common divisor for two integers. If the greatest common divisor of two integers is 1, the two numbers are said to be relatively prime, or one integer is said to be prime to the other. If p, q, ..., u are the distinct prime divisors of a positive integer n, the number of positive integers not exceeding and prime to n is given by the formula

If a, b, m are integers (m, positive) such that a - b is a multiple of m, then a is congruent to b with respect to the modulus m, which is written a:b (mod m) This expression itself is called a congruence; congruences behave in many respects like equations. The theory of congruences is very important in number theory; for example, congruence theory can be used to solve problems known as Chinese remainders. An illustrative problem of this type is: Find the first two positive integers having the remainders 2, 3, 2, when divided by 3, 5, 7, respectively. The answer, 23 and 128, was given by the Chinese mathematician Sun-Tsŭ in the 1st century ad.

Prime Numbers, integers greater than 1 that are not the products of the multiplication of any combination of positive integers other than themselves and 1. Of the first ten positive integers greater than 1 (2 through 11), for example, 2, 3, 5, 7, and 11 are prime, whereas 4 (= 2 × 2), 6 (= 2 × 3), 8 (= 2 × 4), 9 (= 3 × 3), and 10 (= 2 × 5) are not. Numbers that are not prime are known as composite numbers.

The importance of prime numbers arises from the Fundamental Theorem of Arithmetic: Every integer greater than 1 is a product of one or more prime numbers (possibly with repetitions), and this factorization is unique. For instance, 30 = 2 × 3 × 5, and 28 = 2 × 2 × 7 (or 2² × 7). This theorem reduces the complexity of many mathematical problems concerning integers by allowing them to be restated as problems concerning prime numbers.

Mersenne primes are a specific type of prime number that can be derived using the formula 2ⁿ - 1, where n is a prime number. When n = 2, for example, (2 × 2) – 1 = 3, which is also prime. Not every prime value of n results in a prime solution to the equation, but the chances of the solution being prime are much greater than for a randomly selected number. Mersenne primes are named after the 17th-century French mathematician Marin Mersenne who discovered them.

The ancient Greek mathematician Euclid proved that there are infinitely many prime numbers. The Prime Number Theorem states that large integers are less likely to be prime than small ones. This means that the average separation of consecutive prime numbers increases as the numbers get larger. Primes occur very irregularly among the integers, however, and there is no simple formula for producing them. Primes sometimes occur in very close proximity. Prime twins, for example, are primes with a difference of only 2, such as 11 and 13 or 29 and 31. Mathematicians believe there are an infinite number of prime twins, but it has not yet been mathematically proven. On the other hand, there are arbitrarily large gaps in which there are no primes. For example, by examining sufficiently large numbers it is possible to find a million consecutive numbers, not one of which is prime, immediately followed by a prime twin.

In recent years, computers have been applied extensively to the problems of finding new primes, testing whether a particular integer is prime, and factoring a given integer. All three of these processes require very laborious calculations when the numbers involved are large. Effective secret codes have been based on the computational difficulty of factoring very large prime numbers.