Prime valuation is a useful concept in number theory that describes how many times a prime number divides a nonzero integer. For a prime p and a nonzero integer n, the p-adic valuation vₚ(n) is the largest nonnegative integer e such that pᵉ divides n. For example, since 72 = 2³ × 3², we have v₂(72) = 3 and v₃(72) = 2.
Legendre's Formula applies this concept to factorials. It calculates the exponent of a prime p in the prime factorization of n!. The formula is vₚ(n!) = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + ..., where the sum continues until the powers of p exceed n. The floor symbol ⌊x⌋ represents the greatest integer less than or equal to x.
The formula works because multiples of p contribute at least one factor of p, multiples of p² contribute an additional factor, multiples of p³ contribute another factor, and so on. For example, to calculate the exponent of 2 in 10!, count the multiples of 2, then the additional factors contributed by multiples of 4 and 8. This gives 5 + 2 + 1 = 8. Therefore, 2⁸ is the highest power of 2 dividing 10!.
Prime valuation and Legendre's Formula are useful for determining divisibility properties of factorials, calculating binomial coefficients, and studying prime exponents in large integer expressions.
Legendre's Formula and Prime Valuation
Legendre's Formula determines the exponent of a prime number in the prime factorization of a factorial. Prime valuation is a broader concept that measures the exponent of a prime dividing a given integer.
| Name | Expression | Description |
|---|---|---|
Prime Valuation | vₚ(n) = max{e ≥ 0 : pᵉ | n} | The largest exponent e for which the prime power pᵉ divides n. |
Product Property | vₚ(ab) = vₚ(a) + vₚ(b) | The valuation of a product is the sum of the valuations of its factors. |
Legendre's Formula | vₚ(n!) = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + ... | Calculates the exponent of p in n!. |
Factorial Ratio | vₚ(n!/(a!b!)) = vₚ(n!) − vₚ(a!) − vₚ(b!), where a + b = n | Calculates the prime exponent in a binomial coefficient. |
Explanation
Variables
P
A prime number.
N
A positive integer.
E
The exponent of p in the prime factorization of n.
Vₚ(n)
The p-adic valuation of n.
K
A positive integer representing the power of p in Legendre's sum.
⌊x⌋
The floor of x, meaning the greatest integer less than or equal to x.
Example or application
A worked example has not yet been added.
Definition
For a prime p and nonzero integer n, the p-adic valuation vₚ(n) is the largest nonnegative integer e such that pᵉ divides n. Legendre's Formula states that vₚ(n!) = Σ_{k≥1} ⌊n/pᵏ⌋.
Purpose
The purpose of prime valuation is to measure the exponent of a prime in an integer. Legendre's Formula extends this idea to factorials, allowing prime exponents to be calculated without expanding large factorials.
Importance
It determines the prime factorization structure of factorials.
It provides an efficient way to calculate divisibility by prime powers.
It is essential for analyzing binomial coefficients.
It helps determine whether a factorial expression is divisible by a given integer.
It provides a foundation for p-adic number theory.
It simplifies problems involving large factorials and prime exponents.
Key Concepts
| Name | Description |
|---|---|
Prime Valuation | The exponent of a prime p in the prime factorization of a nonzero integer. |
p-adic Valuation | The function vₚ(n) that measures the exponent of p dividing n. |
Factorial | The product of all positive integers from 1 to n, denoted by n!. |
Legendre's Formula | A formula for calculating the exponent of a prime in the prime factorization of a factorial. |
Floor Function | The function ⌊x⌋ that gives the greatest integer less than or equal to x. |
Prime Power | A number of the form pᵏ, where p is prime and k is a positive integer. |
Characteristics
The p-adic valuation of a nonzero integer is a nonnegative integer.
The valuation of a prime p itself is vₚ(p) = 1.
If p does not divide n, then vₚ(n) = 0.
The valuation of a product equals the sum of the valuations of its factors.
Legendre's Formula involves a finite sum because the floor terms become zero when pᵏ exceeds n.
The formula counts repeated contributions from higher powers of the same prime.
It can be applied to factorial ratios when the resulting expression is an integer.
Types
| Name | Description |
|---|---|
Prime Valuation of an Integer | Measures the exponent of a prime in an ordinary nonzero integer. |
Prime Valuation of a Factorial | Uses Legendre's Formula to calculate the exponent of a prime in n!. |
Valuation of a Rational Number | For a nonzero rational number a/b, the p-adic valuation is vₚ(a) − vₚ(b). |
p-adic Valuation of Products | Describes how prime exponents combine when integers are multiplied. |
Components
| Name | Description |
|---|---|
Prime Number | The prime p whose exponent is being investigated. |
Integer or Factorial | The number n or factorial n! whose prime valuation is required. |
Prime Powers | The powers p, p², p³, and higher powers that contribute to the valuation. |
Floor Terms | The quantities ⌊n/pᵏ⌋ that count multiples of each prime power. |
Total Exponent | The sum of all floor terms, giving the exponent of p in n!. |
Properties
vₚ(1) = 0.
vₚ(p) = 1 for every prime p.
vₚ(ab) = vₚ(a) + vₚ(b) for nonzero integers a and b.
vₚ(a/b) = vₚ(a) − vₚ(b) for nonzero rational numbers.
If p does not divide n, then vₚ(n) = 0.
The valuation of a factorial is determined by Legendre's Formula.
The number of terms in Legendre's sum is finite.
For a binomial coefficient, the prime valuation is always nonnegative because the binomial coefficient is an integer.
Examples
| Title | Problem | Solution | Answer |
|---|---|---|---|
Prime Valuation of an Integer | Find v₂(80) and v₅(80). | The prime factorization of 80 is 2⁴ × 5. Therefore, the exponent of 2 is 4 and the exponent of 5 is 1. | v₂(80) = 4 and v₅(80) = 1. |
Applying Legendre's Formula | Find the exponent of 2 in 10!. | Using Legendre's Formula, v₂(10!) = ⌊10/2⌋ + ⌊10/4⌋ + ⌊10/8⌋ + ⌊10/16⌋ = 5 + 2 + 1 + 0 = 8. | The exponent of 2 in 10! is 8. |
Prime Exponent in a Binomial Coefficient | Find the exponent of 3 in the prime factorization of C(6, 3). | Use v₃(6!) − 2v₃(3!). We have v₃(6!) = ⌊6/3⌋ = 2 and v₃(3!) = ⌊3/3⌋ = 1. Therefore, the exponent is 2 − 1 − 1 = 0. | The exponent of 3 in C(6, 3) = 20 is 0. |
Applications
Determining the prime factorization of factorials.
Checking divisibility of large factorial expressions.
Calculating prime exponents in binomial coefficients.
Studying p-adic valuations.
Solving number-theoretic divisibility problems.
Analyzing prime powers in integer sequences and combinatorial expressions.
Prerequisites
Prime factorization
Prime powers
Factorials
Floor function
Divisibility
Learning Objectives
Define prime valuation and p-adic valuation.
Calculate the exponent of a prime in an integer.
State and apply Legendre's Formula.
Explain why higher prime powers contribute additional terms.
Calculate prime exponents in factorials.
Apply prime valuations to binomial coefficients.
Use valuation properties to investigate divisibility.
Common Mistakes
Counting only multiples of p and ignoring higher powers such as p² and p³.
Using the ceiling function instead of the floor function.
Including terms after pᵏ becomes greater than n without recognizing that they are zero.
Confusing the number of prime factors with the exponent of a specific prime.
Subtracting factorial valuations in the wrong order.
Assuming that a factorial's prime valuation equals the number of multiples of the prime alone.
Practice Questions
Find v₂(96) and v₃(96).
Use Legendre's Formula to find the exponent of 5 in 25!.
Calculate the exponent of 2 in 20!.
Find the exponent of 3 in C(10, 4).
Explain why multiples of p² contribute an additional factor of p.
State the product property of prime valuations.
How can prime valuation be used to determine divisibility?
Key Takeaway
Prime valuation measures the exponent of a prime in an integer, while Legendre's Formula efficiently calculates that exponent in a factorial. These tools are essential for studying divisibility, binomial coefficients, and prime-power structure.
Related Topics
Prime Factorization
Factorials
Binomial Coefficients
Divisibility
Möbius Function
Number-Theoretic Functions
p-adic Number Theory
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Source verification pending; check an authoritative textbook, university, standards body, or peer-reviewed source.
Suggest a correction or source · More in Arithmetic & Number Theory