Prime number/Citable Version: Difference between revisions
imported>Greg Woodhouse m (deleting comment about definitions of prime) |
imported>Greg Woodhouse (clarify notation and move aside on noation a bit) |
||
| Line 4: | Line 4: | ||
Prime numbers are usually defined to be positive [[integer]]s (other than 1) with the property that they are only (evenly) [[divisor|divisible]] by 1 and themselves. In other words, a number <math>n \in \mathbb{N}</math> is said to be prime if there are exactly two <math>m \in \mathbb{N}</math> such that <math>m | n</math>, namely <math>m = 1</math> and <math>m = n</math>. | Prime numbers are usually defined to be positive [[integer]]s (other than 1) with the property that they are only (evenly) [[divisor|divisible]] by 1 and themselves. In other words, a number <math>n \in \mathbb{N}</math> is said to be prime if there are exactly two <math>m \in \mathbb{N}</math> such that <math>m | n</math>, namely <math>m = 1</math> and <math>m = n</math>. | ||
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 <math>p \in \mathbb{N}</math> is prime if for any <math>a, b \in \mathbb{N}</math> such that <math>p | ab</math>, either <math>p | a</math> or <math>p | b</math>. | 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 <math>p \in \mathbb{N}</math> is prime if for any <math>a, b \in \mathbb{N}</math> such that <math>p | ab</math> (read ''p'' divides ''ab''), either <math>p | a</math> or <math>p | b</math>. If the first characterization of prime numbers is taken as the [[definition]], the second is derived from it as a [[theorem]], and ''vice versa''. | ||
:'''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 mathematics|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 comparatively less progress in algebra and number theory. | |||
==Unique Factorization== | ==Unique Factorization== | ||
Revision as of 06:01, 6 April 2007
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 17. With the exception of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2} , all prime numbers are odd numbers, but not every odd number is prime. For example, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 9 = 3\cdot3} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 15 = 3\cdot5} , 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. While this used to be the case, the theory of prime numbers has important applications now. 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 and, of course, military applications. Less well known is that other computer algorithms also depend on properties of prime numbers.
Definition
Prime numbers are usually defined to be positive integers (other than 1) with the property that they are only (evenly) divisible by 1 and themselves. In other words, a number Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \in \mathbb{N}} is said to be prime if there are exactly two Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m \in \mathbb{N}} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m | n} , namely Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m = 1} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m = n} .
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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p \in \mathbb{N}}
is prime if for any Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a, b \in \mathbb{N}}
such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p | ab}
(read p divides ab), either Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p | a}
or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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.
- 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 comparatively less progress in algebra and number theory.
Unique Factorization
Every integer N > 1 can be written in a unique way as a product of prime factors, up to reordering. to see why this is true, assume that N can be written as a product of prime factors in two ways
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N = p_1 p_2 \cdots p_m = q_1 q_2 \cdots q_n}
Given any prime divisor of N (call it p), we know that
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p | p_1 p_2 \cdots p_m}
and
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p | q_1 q_2 \cdots q_n}
Because p is prime, we know there are integers i and j such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p | p_i} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p | q_j} . On the other hand, since Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_i} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q_j} are prime, it must be that p is equal to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_i} and to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q_j} . This means we can "cancel" p, and obtain twwo factorizations of N/p. We continue this process until we are reduced to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 = 1} ; that is, until all primes have been removed from the list. This shows that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m = n} , and that both lists consist of the same prime factors. The argument we just gave is an example of mathematical induction, an import idea that occurs again and again. For example, we've just show that if a number can be expressed as a product of primes, then it can be so expressxed in only one way. But how do we know that it is even possible to express a number as a product of prime factors? Well, suppose that the only factors of N are 1 and itself. Then N must be prime, and we are done. If not, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N = a b} where both Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a < N} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b < N} a neither a nor b is equal to 1. If we already know that all numbers smaller than N can be expressed as product of prime factors, then the same must be true of N. Finally, 2 can be expressed as a product of prime factors, just take Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2 = 2} ! It follows that every number is a product of prime factors. Notice that this, too, is an argument using induction.
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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{ p_1, p_2, p_3, \ldots, p_n \}} , and let
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N = p_1 p_2 \cdots p_n +1}
then for each Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i \in 1, \ldots, n} we know that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_i \not| N} (because the remainder is 1). This means that N is not divisible by an prime, which is impossible. 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.