Prime factor: Difference between revisions
Content deleted Content added
PrimeHunter (talk | contribs) |
fixing target section Tag: Redirect target changed |
||
| (13 intermediate revisions by 9 users not shown) | |||
| Line 1: | Line 1: | ||
#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]] |
|||
Latest revision as of 19:20, 23 March 2018
Redirect to:
- To a section: This is a redirect from a topic that does not have its own page to a section of a page on the subject. For redirects to embedded anchors on a page, use {{R to anchor}} instead.
- From a merge: This is a redirect from a page that was merged into another page. This redirect was kept in order to preserve the edit history of this page after its content was merged into the content of the target page. Please do not remove the tag that generates this text (unless the need to recreate content on this page has been demonstrated) or delete this page.
- For redirects with substantive page histories that did not result from page merges use {{R with history}} instead.