✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · SCI-MAT-002-097

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.

NameExpressionDescription

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

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.

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

NameDescription

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

NameDescription

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

NameDescription

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

TitleProblemSolutionAnswer

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