# integer factorization

Given an integer $n$, its integer factorization (or prime factorization) consists of the primes ${p}_{i}$ which multiplied together give $n$ as a result. To put it algebraically,

$$n=\prod _{i=1}^{\omega (n)}p_{i}{}^{{a}_{i}},$$ |

with each ${p}_{i}$ distinct, all ${a}_{i}>0$ but not necessarily distinct, and $\omega (n)$ being the value of the number of distinct prime factors function. Theoretically, an integer is a product of all the prime numbers^{},

$$n=\prod _{i=1}^{\mathrm{\infty}}p_{i}{}^{{a}_{i}},$$ |

with many ${a}_{i}=0$.

For example, the factorization of 32851 is $7\times 13\times 19\times 19$, more usually expressed as $7\times 13\times {19}^{2}$. Because of the commutative property of multiplication, it does not matter in what order the prime factors^{} are stated in, but it is customary to give them in ascending order (http://planetmath.org/AscendingOrder), and to group them together by the use of exponents.

The factorization of a positive integer is unique (this is the fundamental theorem of arithmetic). For a negative number $$ one could take the factorization of $|n|$ and randomly give negative signs to one (or any odd number^{}) of the prime factors. Alternatively, the factorization can be given as $-1\cdot p_{1}{}^{{a}_{1}}\cdot \mathrm{\dots}$ (this is what Mathematica opts for).

The term “factorization” is often used to refer to the actual process of determining the prime factors. There are several algorithms^{} to choose from, with trial division^{} being the simplest to implement.

Title | integer factorization |
---|---|

Canonical name | IntegerFactorization |

Date of creation | 2013-03-22 16:39:09 |

Last modified on | 2013-03-22 16:39:09 |

Owner | PrimeFan (13766) |

Last modified by | PrimeFan (13766) |

Numerical id | 8 |

Author | PrimeFan (13766) |

Entry type | Definition |

Classification | msc 11A41 |

Synonym | prime factorization |