العربية
中国
Français
Deutsch
Ελληνική
हिन्दी
Italiano
日本語
Português
Русский
EspañolPRIME 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''.
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.
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; since one must find not only the factors of a number, but prove that those factors are prime, this problem takes time exponentially proportional to 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.
★ 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)
★ Divisor
★ Composite number
★ Integer factorization
★ Table of prime factors
★ 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).
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.
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; since one must find not only the factors of a number, but prove that those factors are prime, this problem takes time exponentially proportional to 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.
| Contents |
| Examples |
| See also |
| External links |
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
★ Integer factorization
★ 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).
This article provided by Wikipedia. To edit the contents of this article, click here for original source.
psst.. try this: add to faves
