Unique factorization: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Michael Hardy
(The first sentence was not even a sentence and lacked any context setting. This article certainly needs work. Probably I'll be back.)
imported>Jitse Niesen
m (move Category:Mathematics Workgroup from talk page to article)
Line 26: Line 26:


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") &sigma; 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") &sigma; 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.
[[Category:CZ Live]]
[[Category:Mathematics Workgroup]]

Revision as of 02:35, 9 May 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.