## Primes
Every positive integer other than 1 can be written in a unique way as a product of primes.
^{1} 1 mod p. (From this it immediately follows that when p is a prime, a ^{p}a mod p for any integer a.)
^{1} 1 mod m. It turns out that for each choice of a base b, there are pseudoprimes for b. However, things are much worse. When a^{m-}^{1} 1 mod m for every choice of positive a (where a and m are such that the only number which divides both is 1), it does not follow that m must be prime. Such composite numbers m are called Carmichael Numbers, after Robert Daniel Carmichael (1879-1967). An example of a Carmichael Number is 561. Not only do there exist Carmichael Numbers, but like the primes themselves, there are infinitely many of the "varmints." What the discovery of Fermat's Little Theorem set in motion is typical of many parts of mathematics. An interesting result is proven and it encourages a detailed investigation of ideas in the intellectual vicinity of that result. For example, Euler (1707-1783) studied an important relative of the Little Theorem. To state Euler's result we need a very useful concept, that of two positive integers being relatively prime. We say that j and k are relatively prime if the only integer that divides both j and k is 1. Thus, any two primes are relatively prime and, for example, 14 and 15 are relatively prime, while 10 and 14 are not, since 2 divides both 10 and 14. Euler's result states that for any positive integers n and a with the property that the largest integer which divides them both is 1, then a^{phi(n)} 1 mod n. Here, phi(n) (n at least 1) denotes the number of positive integers no more than n which are relatively prime to n. Hence, for a prime p, phi(p) = p-1, while for, say, the composite number 20, phi(20) = 8. (The numbers relatively prime to 20 are 1, 3, 7, 9, 11, 13, 17, and 19.)
n^{2} + 1). Another tantalizing problem is whether or not for every integer n there is always a prime in the interval from n^{2} to (n+1)^{2}. (For example, when n is 10 this question asks if between 100 and 121 there is a prime, and in fact, there are several.) There are many other simple-to-state open problems about primes.Another pattern that quickly becomes apparent when one carefully looks at the sequence of primes is the occurrence of "twins." Twin primes are primes which differ by 2. Thus, 3 and 5; 11 and 13; 17 and 19; 29 and 31; 41 and 43 are examples of twin primes. The Norwegian mathematician Viggo Brun (1885-1978), shown below, raised the specific question as to whether or not there are infinitely many twin primes.(This photograph was made available with the kind permission of Harald Hanche-Olsen)
His work makes more specific the earlier family of problems raised by Alphonse de Polignac, who raised the question in 1849 if, for any even integer |
Welcome to the These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics. Search Feature Column Feature Column at a glance |