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:
“Wisdom is not just knowing fundamental truths, if these are unconnected with the guidance of life or with a perspective on its meaning. If the deep truths physicists describe about the origin and functioning of the universe have little practical import and do not change our picture of the meaning of the universe and our place within it, then knowing them would not count as wisdom.”
—Robert Nozick (b. 1938)
“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 (19131960)
“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)