Mayer–Vietoris sequence

2014-01-22T10:51:29Z

81.65.121.64: /* Derivation */

{{For|the ''[[Star Trek: Voyager]]'' episode|Prime Factors (Star Trek: Voyager)}}
{{refimprove|date=July 2013}}

In [[number theory]], the '''prime factors''' of a positive [[integer]] are the [[prime number]]s that divide that integer exactly. 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.

To shorten prime factorizations, factors are often expressed in 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 ''pa'' 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.

==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; 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 ''total'' number of prime factors of {{math|''n''}}.
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 = 23 × 31}}, so {{math|1=ω(24) = 2}} and {{math|1=Ω(24) = 3+1 = 4}}.

{{math|ω(''n'')}} for {{math|''n''}} = 1, 2, 3, ... is 0, 1, 1, 1, 1, 2, 1, 1, 1, ... {{OEIS|id=A001221}}.

{{math|Ω(''n'')}} for {{math|''n''}} = 1, 2, 3, ... is 0, 1, 1, 2, 1, 2, 1, 3, 2, ... {{OEIS|id=A001222}}.

== See also ==
* [[Composite 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}}

== External links ==
* [http://www.virtuescience.com/prime-factor-calculator.html Prime Factor Calculator at the Database of Number Correlations]
* [http://www.se16.info/js/factor.htm A Javascript Prime Factor Calculator. Can handle numbers up to about 9×1015]
* [http://www.javascripter.net/math/calculators/primefactorscalculator.htm Fast Prime Factorization Calculator in JavaScript. Can handle numbers up to 1020]
* [http://www.alpertron.com.ar/ECM.HTM Java applet: Factorization using the Elliptic Curve Method finding factors with 20+ digits]
* [http://factors.evalwave.com/fHome.html Millions of factors and prime factors on html pages.]
* [http://dvneo.com/trivia/0505_prime_factors/ List of prime factors for numbers from 2 - 5 million and growing.]
* [http://primefactorizationcalculator.org Prime Factorization Calculator. Can handle numbers up to about 9×1015]
* [http://www.academia.edu/1066276/Prime_Factorisation_A_New_Approach Prime Factorization A New Approach]

{{Divisor classes}}

[[Category:Prime numbers]]

formulasearchengine - User contributions [en]

Mayer–Vietoris sequence