|
#Redirect [[Prime number#Unique factorization]]
{{Redirect|Prime factors|the television episode|Prime Factors (Star Trek: Voyager)}}
{{R to section}}
[[Image:PrimeDecompositionExample.svg|right|thumb|200px|This image demonstrates how to find the prime factorization of 864. A shorthand way of writing the resulting prime factors is 2<sup>5</sup> × 3<sup>3</sup>]]
{{R from merge}}
In [[number theory]], the '''prime factors''' of a positive [[integer]] are the [[prime number]]s that divide that integer exactly.<ref>
{{cite book
| last = Jensen
| first = Gary R.
| year = 2004
| title = Arithmetic for Teachers: With Applications and Topics from Geometry
| publisher = American Mathematical Society
}}</ref> The [[integer factorization|prime factorization]] of a positive integer is a list of the integer's prime factors, together with their [[Multiplicity (mathematics)|multiplicities]]; the process of determining these factors is called [[integer factorization]]. The [[fundamental theorem of arithmetic]] says that every positive integer has a single unique prime factorization.<ref name="Riesel">{{Citation | last1=Riesel | first1=Hans | title=Prime numbers and computer methods for factorization | publisher=Birkhäuser | location=Basel, Switzerland | isbn=978-0-8176-3743-9 | year=1994}}</ref>
To shorten prime factorizations, factors are often expressed in [[prime power|powers]] (multiplicities). For example,
:<math> 360 = 2 \times 2 \times 2 \times 3 \times 3 \times 5 = 2^3 \times 3^2 \times 5,</math>
in which the factors 2, 3 and 5 have multiplicities of 3, 2 and 1, respectively.
For a prime factor ''p'' of ''n'', the multiplicity of ''p'' is the largest [[Exponentiation|exponent]] ''a'' for which ''p<sup>a</sup>'' divides ''n'' exactly.
For a positive integer ''n'', the ''number'' of prime factors of ''n'' and the ''sum'' of the prime factors of ''n'' (not counting multiplicity) are examples of [[arithmetic function]]s of ''n'' that are [[additive function|additive]] but not completely additive.<ref>{{cite book | title=Additive Number Theory: the Classical Bases | volume=234 | series=Graduate Texts in Mathematics | author=Melvyn B. Nathanson | publisher=Springer-Verlag | year=1996 | isbn=0-387-94656-X }}</ref>
==Perfect squares==
[[Square number|Perfect square numbers]] can be recognized by the fact that all of their prime factors have even multiplicities. For example, the number 144 (the square of 12) has the prime factors
:<math> 144 = 2 \times 2 \times 2 \times 2 \times 3 \times 3 = 2^4 \times 3^2.</math>
These can be rearranged to make the pattern more visible:
:<math> 144 = 2 \times 2 \times 2 \times 2 \times 3 \times 3 = (2 \times 2 \times 3) \times (2 \times 2 \times 3) = (2 \times 2 \times 3)^2 = (12)^2.</math>
Because every prime factor appears an even number of times, the original number can be expressed as the square of some smaller number. In the same way, [[Cube number|perfect cube numbers]] will have prime factors whose multiplicities are multiples of three, and so on.
==Coprime integers==
Positive integers with no prime factors in common are said to be [[coprime]]. Two integers ''a'' and ''b'' can also be defined as coprime if their [[greatest common divisor]] gcd(''a'', ''b'') = 1. [[Euclid's algorithm]] can be used to determine whether two integers are coprime without knowing their prime factors; the algorithm runs in a [[Time complexity#Polynomial time|time that is polynomial]] in the number of digits involved.
The integer 1 is coprime to every positive integer, including itself. This is because it has no prime factors; it is the [[empty product]]. This implies that gcd(1, ''b'') = 1 for any ''b'' ≥ 1.
==Cryptographic applications==
Determining the prime factors of a number is an example of a problem frequently used to ensure cryptographic security in [[encryption]] systems;<ref>{{cite book
| last = Menezes | first = Alfred
| last2 = van Oorschot | first2 = Paul C. | last3 = Vanstone | first3 = Scott A.
| url = http://www.cacr.math.uwaterloo.ca/hac/
| title = Handbook of Applied Cryptography
| publisher = CRC Press |date=October 1996
| isbn = 0-8493-8523-7 }}</ref> this problem is believed to require [[Time complexity#Superpolynomial time|super-polynomial time]] in the number of digits — it is relatively easy to construct a problem that would take longer than the known [[age of the universe]] to solve on current computers using current algorithms.
== {{anchor|Omega function}} Omega functions ==
The function, {{math|''ω''(''n'')}} (omega), represents the number of ''distinct'' prime factors of ''n'', while the function, {{math|Ω(''n'')}} (big omega), represents the number of prime factors of {{math|''n''}} counted by multiplicities.<ref name ="Riesel" />
If
:<math>n = \prod_{i=1}^{\omega(n)} p_i^{\alpha_i},</math>
then
:<math>\Omega(n) = \sum_{i=1}^{\omega(n)} \alpha_i.</math>
For example, {{math|1=24 = 2<sup>3</sup> × 3<sup>1</sup>}}, so {{math|1=''ω''(24) = 2}} and {{math|1=Ω(24) = 3 + 1 = 4}}.
*{{math|''ω''(''n'')}} for {{math|''n''}} = 1, 2, 3, … is respectively 0, 1, 1, 1, 1, 2, 1, 1, 1, … {{OEIS|id=A001221}}.
*{{math|Ω(''n'')}} for {{math|''n''}} = 1, 2, 3, … is respectively 0, 1, 1, 2, 1, 2, 1, 3, 2, … {{OEIS|id=A001222}}.
== See also ==
* [[Composite number]]
* [[Integer factorization]] – the algorithmic problem of finding the prime factors of a given number
* [[Divisor]]
* [[Table of prime factors]]
* [[Sieve of Eratosthenes]]
* [[Erdős–Kac theorem]]
* [[Arithmetic function#Ω(n), ω(n), νp(n) – prime power decomposition|Ω(n), ω(n), νp(n) – prime power decomposition]]
== References ==
{{reflist}}
{{Divisor classes}}
[[Category:Prime numbers]]
| 