## You are here

Homeinteger factorization

## Primary tabs

# 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}}^{{\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, 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 $n<0$ 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\ldots$ (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.

## Mathematics Subject Classification

11A41*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## Contrasting and comparing PrimeFan, CompositeFan

I just noticed that CompositeFan attached her entry on trial division to the entry on composite numbers, while PrimeFan attached his entry on the Fermat method to the entry on primes. (I think attaching to integer factorization would make more sense).

There are other interesting similarities and differences between the two: PrimeFan will contribute something to Wikipedia first and then PlanetMath, while CompositeFan will contribute something to PlanetMath first and then Wikipedia. PrimeFan is an old man who served in the Navy in the pointful Second World War, while CompositeFan is a young woman who served in the Navy in the pointless First Gulf War. PrimeFan hates classical music but is interested in opus sequences, while CompositeFan loves classical music but couldn't care less for opus sequences. etc.

## Re: Contrasting and comparing PrimeFan, CompositeFan

Marine Corps, which is technically Department of the Navy (Marines are sticklers for those kinds of details); just because the current Gulf War is "pointless" doesn't mean the first one was too (in fact, the Kuwaiti were actually grateful to us); "hates" is too strong a word for it, "doesn't like it" would be more accurate; though it appears that for some reason the vast majority of professional mathematicians as well as amateurs really love classical music. Gowers's book briefly mentioned this, if I recall correctly.