The crucial importance of prime numbers to number theory and mathematics in general stems from the fundamental theorem of arithmetic, which states that every positive integer larger than 1 can be written as a product of one or more primes in a way that is unique except for the order of the prime factors. Primes can thus be considered the “basic building blocks” of the natural numbers. For example:
-
23244 = 2 · 2 · 3 · 13 · 149 = 22 · 3 · 13 · 149. (22 denotes the square or second power of 2.)
As in this example, the same prime factor may occur multiple times. A decomposition:
- n = p1 · p2 · ... · pt
of a number n into (finitely many) prime factors p1, p2, ... to pt is called prime factorization of n. The fundamental theorem of arithmetic can be rephrased so as to say that any factorization into primes will be identical except for the order of the factors. So, albeit there are many prime factorization algorithms to do this in practice for larger numbers, they all have to yield the same result.
If p is a prime number and p divides a product ab of integers, then p divides a or p divides b. This proposition is known as Euclid's lemma. It is used in some proofs of the uniqueness of prime factorizations.
Read more about this topic: Prime Number
Famous quotes containing the words fundamental, theorem and/or arithmetic:
“The science, the art, the jurisprudence, the chief political and social theories, of the modern world have grown out of Greece and Rome—not by favor of, but in the teeth of, the fundamental teachings of early Christianity, to which science, art, and any serious occupation with the things of this world were alike despicable.”
—Thomas Henry Huxley (1825–95)
“To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
—Albert Camus (1913–1960)
“O! O! another stroke! that makes the third.
He stabs me to the heart against my wish.
If that be so, thy state of health is poor;
But thine arithmetic is quite correct.”
—A.E. (Alfred Edward)