In
number theoryNumber theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
, the
prime factors of a positive
integerThe integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
are the
prime numberA prime number 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 called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
s that divide that integer exactly, without leaving a remainder. The process of finding these numbers is called
integer factorizationIn number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
, or prime factorization. A prime factor can be visualized by understanding Euclid's geometric position. He saw a whole number as a line segment, which has a smallest line segment greater than 1 that can divide equally into it.
For a prime factor
p of
n, the
multiplicity of
p is the largest exponent
a for which
pa divides
n. The
prime factorizationIn number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
of a positive integer is a list of the integer's prime factors, together with their multiplicity. The
fundamental theorem of arithmeticIn number theory, the fundamental theorem of arithmetic states that any integer greater than 1 can be written as a unique product of prime numbers...
says that every positive integer has a unique prime factorization.
To shorten prime factorization, numbers are often expressed in powers, so
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 functionIn number theory, an arithmetic function is a real or complex valued function ƒ defined on the set of natural numbers In number theory, an arithmetic (or arithmetical) function is a real or complex valued function ƒ(n) defined on the set of natural numbers In number theory, an arithmetic (or...
s of
n that are
additiveIn mathematics the term additive function has two different definitions, depending on the specific field of application.In algebra an additive function is a function that preserves the addition operation:for any two elements x and y in the domain. For example, any linear map is 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
encryptionIn cryptography, encryption is the process of transforming information using an algorithm to make it unreadable to anyone except those possessing special knowledge, usually referred to as a key. The result of the process is encrypted information...
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 UniverseThe age of the universe is the time elapsed since the Big Bang posited by the most widely accepted scientific model of cosmology. The best current estimate of the age of the universe is 13.75 ± 0.13 billion years within the Lambda-CDM concordance model...
to calculate on current computers using current algorithms.
Two positive integers are
coprimeIn number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...
if and only ifIn logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
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 productIn mathematics, an empty product, or nullary product, is the result of multiplying no factors. It is equal to the multiplicative identity 1, given that it exists for the multiplication operation in question, just as the empty sum—the result of adding no numbers—is zero, or the additive...
. 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 function
represents the number of
distinct prime factors of n, while
represents the
total number of prime factors.
If
,
then
.
For example,
, so:
and
.
ω(
n) for n = 1, 2, 3, ... is 0, 1, 1, 1, 1, 2, 1, 1, 1, ...
Ω(
n) for n = 1, 2, 3, ... is 0, 1, 1, 2, 1, 2, 1, 3, 2, ...
External links