User:JustBerry/Math/Prime Factorization/sandbox

Status: Work In Progress

[http://en.wikipedia.org/wiki/Integer_factorization]

Prime decomposition

This image demonstrates the prime decomposition of 864. A shorthand way of writing the resulting prime factors is $2^{5}\times 3^{3}$

Finding the prime factorization of 42 via the 'Factor Tree method'

By the fundamental theorem of arithmetic, every positive integer has a unique prime factorization. (A special case for 1 is not needed using an appropriate notion of the empty product.) However, the fundamental theorem of arithmetic gives no insight into how to obtain an integer's prime factorization; it only guarantees its existence.

Given a general algorithm for integer factorization, one can factor any integer down to its constituent prime factors by repeated application of this algorithm. However, this is not the case with a special-purpose factorization algorithm, since it may not apply to the smaller factors that occur during decomposition, or may execute very slowly on these values. For example, if N is the number (2⁵²¹ − 1) × (2⁶⁰⁷ − 1), then trial division will quickly factor 10N as 2 × 5 × N, but will not quickly factor N into its factors.

When a prime factorization has the same prime factor (f) appearing x number of times in a prime factorization, the factors can be written as f^x. There are several methods to performing a prime factorization. The "factor tree" method is one of the methods used to find a prime factorization. It represents the prime factors of a positive integer in a "family tree" layout or diagram.

External Link(s)

Prime Factorization Instructional Video