Prime factor
Published February 27th, 2008 in UncategorizedIn 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.
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 iff 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 length of the number - it is relatively easy to construct a problem that would take longer than the known age of the Universe to calculate on current computers.
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 = 22 × 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 the empty product)
See also
- Divisor
- Composite number
- Table of prime factors
External links
- A Javascript Prime Factor Calculator. Can handle numbers up to about 9×1015
- 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).
53 Comments to “Prime factor”
Please Wait
Leave a Reply
You must log in to post a comment.