Unique factorization: Difference between revisions
imported>Jitse Niesen m (move Category:Mathematics Workgroup from talk page to article) |
imported>Subpagination Bot m (Add {{subpages}} and remove any categories (details)) |
||
Line 1: | Line 1: | ||
{{subpages}} | |||
In [[mathematics]], the '''unique factorization theorem''', also known as the '''fundamental theorem of arithmetic''' states that every integer can be expressed as a product of [[prime number]]s in essentially only one way. | In [[mathematics]], the '''unique factorization theorem''', also known as the '''fundamental theorem of arithmetic''' states that every integer can be expressed as a product of [[prime number]]s in essentially only one way. | ||
Line 26: | Line 28: | ||
Continuing in this way, we obtain a sequence of numbers <math>N = N_0 > N_1 > N_2 > \cdots > N_n = 1</math> where each <math>N_{\alpha}</math> is obtained by dividing <math>N_{\alpha - 1}</math> by a prime factor. In particular, we see that <math>m = n</math> and that there is some permutation ("rearrangement") σ of the indices <math>1, 2, \ldots n</math> such that <math>p_i = q_{\sigma(i)}</math>. Said differently, the two factorizations of ''N'' must be the same up to a possible rearrangement of terms. | Continuing in this way, we obtain a sequence of numbers <math>N = N_0 > N_1 > N_2 > \cdots > N_n = 1</math> where each <math>N_{\alpha}</math> is obtained by dividing <math>N_{\alpha - 1}</math> by a prime factor. In particular, we see that <math>m = n</math> and that there is some permutation ("rearrangement") σ of the indices <math>1, 2, \ldots n</math> such that <math>p_i = q_{\sigma(i)}</math>. Said differently, the two factorizations of ''N'' must be the same up to a possible rearrangement of terms. | ||
Revision as of 08:03, 15 November 2007
In mathematics, the unique factorization theorem, also known as the fundamental theorem of arithmetic states that every integer can be expressed as a product of prime numbers in essentially only one way.
Proof
Every integer can be written in a unique way as a product of prime factors, up to reordering. To see why this is true, assume that can be written as a product of prime factors in two ways
We may now use a technique known as mathematical induction to show that the two prime decompositions are really the same.
Consider the prime factor . We know that
Using the second definition of prime numbers, it follows that divides one of the q-factors, say . Using the first definition, is in fact equal to
Now, if we set , we may write
and
In other words, is the product of all the 's except .
Continuing in this way, we obtain a sequence of numbers where each is obtained by dividing by a prime factor. In particular, we see that and that there is some permutation ("rearrangement") σ of the indices such that . Said differently, the two factorizations of N must be the same up to a possible rearrangement of terms.