Prime factor

From Wikipedia, the free encyclopedia

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 p^a divides n.

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.

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 superpolynomial 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.

[edit] Examples

• The prime factors of 6 are 2 and 3 (6 = 2 × 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 = 2² × 5²). Both have multiplicity 2.
• 2, 4, 8, 16, etc. each have only one prime factor: 2. (2 is prime, 4 = 2², 8 = 2³, etc.)
• 1 has no prime factors. (1 is a unit)

[edit] See also

• Divisor
• Composite number
• Table of prime factors

[edit] External links

• A Javascript Prime Factor Calculator. Can handle numbers up to about 9×10¹⁵
• Java applet: Factorization using the Elliptic Curve Method finding factors with 20+ digits
• Lists of composites with prime factorization (first 100, first 1000, first 10,000, first 100,000, and first 1,000,000).