Unique factorization: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Barry R. Smith
(integer-->whole number, importance)
imported>Barry R. Smith
(removed proof (put it on "advanced" subpage))
Line 2: Line 2:


In [[mathematics]], the '''unique factorization theorem''', also known as the '''fundamental theorem of arithmetic''' states that every positive whole number can be expressed as a product of [[prime number]]s in essentially only one way.  It reveals that one may consider the prime numbers as "atoms" from which all other whole numbers can be assembled through multiplication.  Unique factorization is the foundation for most of the structure of whole numbers as described by [[elementary number theory]].  The formulation of many results would either be nonsensical, or at least more complicated, if unique factorization did not hold.  For instance, the assumption that many electronic financial transactions are secure is based on the belief that the product of two very large prime numbers is difficult to factor.  If several other prime factorizations were possible, perhaps some having small prime factors, finding a factorization might be much easier and such security methods would be ineffective.
In [[mathematics]], the '''unique factorization theorem''', also known as the '''fundamental theorem of arithmetic''' states that every positive whole number can be expressed as a product of [[prime number]]s in essentially only one way.  It reveals that one may consider the prime numbers as "atoms" from which all other whole numbers can be assembled through multiplication.  Unique factorization is the foundation for most of the structure of whole numbers as described by [[elementary number theory]].  The formulation of many results would either be nonsensical, or at least more complicated, if unique factorization did not hold.  For instance, the assumption that many electronic financial transactions are secure is based on the belief that the product of two very large prime numbers is difficult to factor.  If several other prime factorizations were possible, perhaps some having small prime factors, finding a factorization might be much easier and such security methods would be ineffective.
== Proof ==
Every integer <math>N > 1</math> can be written in a unique way as a product of prime factors, up to reordering. To see why this is true, assume that <math>N</math> can be written as a product of prime factors in two ways
:<math>N = p_1 p_2 \cdots p_m = q_1 q_2 \cdots q_n</math>
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 <math>p_1</math>. We know that
:<math>p_1 \mid q_1 q_2 \cdots q_n.</math>
Using the second definition of prime numbers, it follows that <math>p_1</math> divides one of the ''q''-factors, say <math>q_i</math>. Using the first definition, <math>p_1</math> is in fact equal to <math>q_i</math>
Now, if we set <math>N_1 = N/p_1</math>, we may write
:<math>N_1 = p_2 p_3 \cdots p_m</math>
and
:<math>N_1 = q_1 q_2 \cdots q_{i-1} q_{i+1} \cdots q_n</math>
In other words, <math>N_1</math> is the product of all the <math>q</math>'s except <math>q_i</math>.
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.

Revision as of 10:51, 6 April 2008

This article is developing and not approved.
 Main Article
 Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
Advanced [?]
 
https://en.citizendium.org/wiki/index.php?title=Unique_factorization&printable=yes
This editable Main Article is under development and subject to a disclaimer.

In mathematics, the unique factorization theorem, also known as the fundamental theorem of arithmetic states that every positive whole number can be expressed as a product of prime numbers in essentially only one way. It reveals that one may consider the prime numbers as "atoms" from which all other whole numbers can be assembled through multiplication. Unique factorization is the foundation for most of the structure of whole numbers as described by elementary number theory. The formulation of many results would either be nonsensical, or at least more complicated, if unique factorization did not hold. For instance, the assumption that many electronic financial transactions are secure is based on the belief that the product of two very large prime numbers is difficult to factor. If several other prime factorizations were possible, perhaps some having small prime factors, finding a factorization might be much easier and such security methods would be ineffective.

Retrieved from "https://citizendium.org/wiki/index.php?title=Unique_factorization&oldid=213094"