Prime factor

﻿
Prime factor

In number theory, the prime factors of a positive integer are the prime numbers that divide into that integer exactly, without leaving a remainder. The process of finding these numbers is called integer factorization, or prime factorization.

For a prime factor "p" of "n", the multiplicity of "p" is the largest exponent "a" for which "pa" divides "n". The prime factorization of a positive integer is a list of the integer's prime factors, together with their multiplicity. The fundamental theorem of arithmetic says that every positive integer has a unique prime factorization.

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 functions of "n" that are additive but not completely additive.

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 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 calculate on current computers using current algorithms.

Two positive integers are coprime if and only if they have no prime factors in common. The integer 1 is coprime to every positive integer, including itself. This is because it has no prime factors; it is the empty product. It also follows from defining a and b as coprime if gcd(a,b)=1, so that gcd(1,b)=1 for any 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 that is polynomial in the number of digits involved.

Examples

* The prime factors of 6 are 2 and 3 (6 = 2 &times; 3). Both have multiplicity 1.
* 5 has only one prime factor: itself (5 is prime). It has multiplicity 1.
* 100 has two prime factors: 2 and 5 (100 = 22 &times; 52). Both have multiplicity 2.
* 2, 4, 8, 16, etc. each have only one prime factor: 2. (2 is prime, 4 = 22, 8 = 23, etc.)
* 1 has no prime factors. (1 is a unit)

* Divisor
* Composite number
* Table of prime factors

* [http://people.revoledu.com/kardi/tutorial/BasicMath/Prime/PrimeFactor.htm Prime factors using spreadsheet]
* [http://www.btinternet.com/~se16/js/factor.htm A Javascript Prime Factor Calculator. Can handle numbers up to about 9&times;1015]
* [http://www.alpertron.com.ar/ECM.HTM Java applet: Factorization using the Elliptic Curve Method finding factors with 20+ digits]
* [http://naturalnumbers.org/composites.html Lists of composites with prime factorization (first 100, first 1000, first 10,000, first 100,000, and first 1,000,000).]

Wikimedia Foundation. 2010.

Look at other dictionaries:

• Prime factor — Prime Prime, a. [F., fr. L. primus first, a superl. corresponding to the compar. prior former. See {Prior}, a., {Foremost}, {Former}, and cf. {Prim}, a., {Primary}, {Prince}.] 1. First in order of time; original; primeval; primitive; primary.… …   The Collaborative International Dictionary of English

• prime factor — noun the prime factors of a quantity are all of the prime quantities that will exactly divide the given quantity • Hypernyms: ↑divisor, ↑factor * * * noun : a factor that is a prime number * * * prime factor, Mathematics. a factor that has no… …   Useful english dictionary

• prime factor — noun (C) a number that can be divided only by itself and the number one, and is a factor of another number: 7 is a prime factor of 21 …   Longman dictionary of contemporary English

• prime factor — 1. noun A factor of a given integer which is also a prime number. 2. verb to reduce an integer to its set of prime factors See Also: set, prime number, prime factorization …   Wiktionary

• prime factor — main cause, main factor …   English contemporary dictionary

• Prime-factor FFT algorithm — The Prime factor algorithm (PFA), also called the Good Thomas algorithm (1958/1963), is a fast Fourier transform (FFT) algorithm that re expresses the discrete Fourier transform (DFT) of a size N = N 1 N 2 as a two dimensional N 1 times; N 2 DFT …   Wikipedia

• F prime factor — F prime factor. = F factor (см.). (Источник: «Англо русский толковый словарь генетических терминов». Арефьев В.А., Лисовенко Л.А., Москва: Изд во ВНИРО, 1995 г.) …   Молекулярная биология и генетика. Толковый словарь.

• F-prime factor — F prime factor. См. F эписома. (Источник: «Англо русский толковый словарь генетических терминов». Арефьев В.А., Лисовенко Л.А., Москва: Изд во ВНИРО, 1995 г.) …   Молекулярная биология и генетика. Толковый словарь.

• Prime number — Prime redirects here. For other uses, see Prime (disambiguation). A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is… …   Wikipedia

• Prime — Prime, a. [F., fr. L. primus first, a superl. corresponding to the compar. prior former. See {Prior}, a., {Foremost}, {Former}, and cf. {Prim}, a., {Primary}, {Prince}.] 1. First in order of time; original; primeval; primitive; primary. Prime… …   The Collaborative International Dictionary of English