Prime number/Citable Version

A prime number is a whole number (i.e, one having no fractional or decimal part) that cannot be evenly divided by any numbers but 1 and itself. The first few prime numbers are 2, 3, 5, 7, 11, 13, and so on. With the exception of $2$, the first few numbers on this list are odd numbers, but not every odd number is prime. For example, $9=3\cdot 3$ and $15=3\cdot 5$, so neither 9 nor 15 is prime. The study of prime numbers has a long history, going back to ancient times, and it remains an active part of number theory (a branch of mathematics) today. It is commonly believed that the study of prime numbers is an interesting, but not terribly useful, area of mathematical research. This, however, is a misundertanding. For example, it is now well known that understanding properties of prime numbers and their generalizations is essential to modern cryptography, and to public key ciphers that are crucial to Internet commerce, wireless networks, telemedicine and, of course, military applications. But while it is commonly known that knowledge of prime numbers is important to cryptography, it is less well known that other computer algorithms depend on properties of prime numbers. These algorithms allow computers to run faster, computer networks to carry more data with a greater degree of reliability, and are basic to the operation of many consumer electronics devices, such as television sets, DVD players, GPS devices, and more. Life as we know it today would not be possible without an understanding of prime numbers.

Definition

Prime numbers are usually defined to be positive integers (other than 1) with the property that are only (evenly) divisible by 1 and themselves. In other words, a number $n\in \mathbb {N}$ is said to be prime if for any $m\in \mathbb {N}$ such that $m|n$, either $m=1$ or $m=n$.

Aside on mathematical notation: The second sentence above is a translation of the first into mathematical notation. It may seem difficult at first (perhaps even a form of obfuscation!), but mathematics relies on precise reasoning, and mathematical notation has proved to be a valuable, if not indispensible, aid to the study of mathematics. It is commonly noted while ancient Greek mathematicians hd a good understanding of prime numbers, and indeed Euclid was able to show that there are infinitely many prime numbers, the study of prime numbers (and algebra in general) was hampered by the lack of a good notation, and this is one reason ancient Greek mathematics (or mathematicians) excelled in geometry, making comparitively less progress in algebra and number theory.

There is another way of defining prime numbers, and that is that a number is prime if whenever it divides the product of two numbers, it must divide one of those numbers. A nonexample (if you will) is that 4 divides 12, but 4 does not divide 2 and 4 does not divide 6 even though 12 is 2 times 6. This means that 4 is not a prime number. We may express this second possible definition in symbols (a phrase commonly used to mean "in mathematical notation") as follows: A number $p\in \mathbb {N}$ is prime if for any $a,b\in \mathbb {N}$ such that $p|ab$, either $p|a$ or $p|b$.

If the first characterization of prime numbers is taken as the definition, the second is derived from it as a theorem, and vice versa. In elementary accounts of number theory, it is common to take the first of these two characterizations as definitional, whereas the latter is preferred in more advanced work.

There are infinitely many primes

One basic fact about the prime numbers is that there are infinitely man of them. In other words, the list of prime numbers 2, 3, 5, 7, 11, 13, 17, ... doesn;t ever stop. There are a number of ways of showing that this is so, but one of the oldest and most familiar proofs goes back go Euclid.

Euclid's Proof

Suppose the set of prime numbers is finite, say $\{p_{1},p_{2},p_{3},\ldots ,p_{n}\}$, and let

$N=p_{1}p_{2}\cdots p_{n}+1$

then for each $i\in 1,\ldots$ n we know that $p_{i}\not |N$ (because the remainder is 1). This means that N is not divisible by an prime, which is impossibe. This contradiction shows that our assumption that there must only be a finite number of primes must have been wrong and thus proves the theorem.