Prime Number - Fundamental Theorem of Arithmetic

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:

    “It is a fundamental characteristic of civilization that man most profoundly mistrusts those living outside his own milieu, so that not only does the Teuton regard the Jew as an incomprehensible and inferior being, but the football player likewise so regards the piano player.”
    —Robert Musil (1880–1942)

    “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)

    “I hope I may claim in the present work to have made it probable that the laws of arithmetic are analytic judgments and consequently a priori. Arithmetic thus becomes simply a development of logic, and every proposition of arithmetic a law of logic, albeit a derivative one. To apply arithmetic in the physical sciences is to bring logic to bear on observed facts; calculation becomes deduction.”
    —Gottlob Frege (1848–1925)