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:
“There can be a fundamental gulf of gracelessness in a human heart which neither our love nor our courage can bridge.”
—Patrick, Mrs. Campbell (1865–1940)
“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)
“‘Tis no extravagant arithmetic to say, that for every ten jokes,—thou hast got an hundred enemies; and till thou hast gone on, and raised a swarm of wasps about thine ears, and art half stung to death by them, thou wilt never be convinced it is so.”
—Laurence Sterne (1713–1768)