Legendre’s formula for valuations of factorials
E695819
Legendre’s formula for valuations of factorials is a number-theoretic result that expresses the exponent of a prime in the prime factorization of n! as a sum of integer divisions of n by successive powers of that prime.
All labels observed (1)
| Label | Occurrences |
|---|---|
| Legendre’s formula for valuations of factorials canonical | 1 |
Statements (46)
| Predicate | Object |
|---|---|
| instanceOf |
number-theoretic formula
ⓘ
result in elementary number theory ⓘ |
| alsoKnownAs |
Legendre’s formula
NERFINISHED
ⓘ
Legendre’s formula for the p-adic valuation of n! NERFINISHED ⓘ |
| appearsIn |
courses on p-adic valuations and factorials
ⓘ
textbooks on elementary number theory ⓘ |
| appliesTo |
positive integers n
ⓘ
prime numbers p ⓘ |
| assumes |
n is a nonnegative integer
ⓘ
p is prime ⓘ |
| classification | closed-form expression for valuations of factorials ⓘ |
| codomain | nonnegative integers ⓘ |
| concerns |
exponent of a prime in n!
ⓘ
factorials ⓘ p-adic valuation ⓘ prime factorization ⓘ |
| defines | v_p(n!) ⓘ |
| domain | natural numbers ⓘ |
| equivalentForm | v_p(n!) = (n - s_p(n))/(p - 1), where s_p(n) is the sum of the base-p digits of n ⓘ |
| example |
For n = 10 and p = 2, v_2(10!) = ⌊10/2⌋ + ⌊10/4⌋ + ⌊10/8⌋ = 5 + 2 + 1 = 8.
ⓘ
For n = 10 and p = 5, v_5(10!) = ⌊10/5⌋ + ⌊10/25⌋ = 2 + 0 = 2. ⓘ |
| field | number theory ⓘ |
| generalizationOf | counting multiples of a prime in an interval ⓘ |
| gives | exponent of p in the prime factorization of n! ⓘ |
| historicalPeriod | 19th century mathematics ⓘ |
| implies |
the sum defining v_p(n!) is finite
ⓘ
v_p(n!) counts how many times p divides n! ⓘ v_p(n!) equals the total number of multiples of p, p^2, p^3, … up to n ⓘ |
| namedAfter | Adrien-Marie Legendre NERFINISHED ⓘ |
| relatedConcept |
Kummer’s theorem
NERFINISHED
ⓘ
base-p expansion of integers ⓘ de Polignac’s formula NERFINISHED ⓘ p-adic valuation ⓘ prime factorization of factorials ⓘ |
| statement |
For a prime p and integer n ≥ 1, the exponent v_p(n!) of p in n! is given by v_p(n!) = ∑_{k=1}^{∞} ⌊n/p^k⌋.
ⓘ
For a prime p and integer n ≥ 1, v_p(n!) = ⌊n/p⌋ + ⌊n/p^2⌋ + ⌊n/p^3⌋ + …, where the sum is finite because p^k > n for large k. ⓘ |
| subfield | elementary number theory ⓘ |
| usedFor |
analyzing growth of prime exponents in n!
ⓘ
computing exponent of a prime in binomial coefficients ⓘ computing p-adic valuation of factorials ⓘ computing the highest power of a prime dividing n! ⓘ computing valuations in combinatorial identities ⓘ problems in p-adic number theory ⓘ studying divisibility properties of binomial coefficients ⓘ |
| usesOperation |
floor function
ⓘ
integer division ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.