What is Legendre's theorem?

Legendre's theorem states that the p-adic valuationThe p-adic valuation of an integer x is the exponent of the highest power of the prime number p that divides x. of $x$ denoted by $v_p(x)$ is defined as a positive integer, $n$, such that $p^n$ divides $x$, where $p$ is a prime number and $x$ is a positive integer. Legendre’s formula can be shown as follows:

Where $\lfloor {x}\rfloor$ is a floor functionFloor function takes a real number x as input, and return the nearest lowest integer. For example input = 2.61 output = 2 and $i$ is the range,$1 \le i \le \infty$. However, despite $i$ being infinite, only the first few terms; $x/p^i \ge 1$, are counted because the other terms are equal to $0$ due to the floor function and do not affect the summation process.

An alternate form of Legendre’s formula that involves the base-p expansion of $x$ is as follows:

Where $s_p(x)$ represents the sum of the digits in the base expansion of $x$.

Working of Legendre's theorem

The working of Legendre's theorem can be understood in more detail using the examples of the original and alternate forms given below.

Original form

The number $n$ denoted by $v_p(x)$, represents the exponent of the largest power of the prime number $p$, which can divide the factorial $x!$. The number $n$ can be calculated by plugging in the values of $x$ and $p$ into the equation directly, but before we do that, we have to explore a simple solution. The number $n$ is the exponent of $p$ in the prime factorizationIt is the process of breaking down the original number into the prime numbers, that can multiplied together to gain the original number. of $x$.

We take an example where $x = 7$; First, we do prime factorization as shown below:

We can see that $6$ and $4$ are not prime numbers, so we divide them even further as shown below:

Simplify and re-write:

Using this, we can deduce the value of $v_2(7!) = 4$, $v_3(7!) = 2$, and $v_5(7!) = 1$ by checking the exponent of the prime number $p$. We can verify the results by plugging the values into the original equation as shown below:

The equations above show a solved example using the prime factorization, and Legendre's original formula produces the same result.

Alternate form

In this example we let $x = 11$ and $p = 2$. To use the alternate form, we need to convert $x$ from base $10$ to base $p$, where $p$ is the prime number. Conversion of the base of $x$ is shown below:

Now, calculate as $s_2(11)$ shown below:

Now that we have all the required values, plug them into the alternate form resulting in the equation as follows:

We can verify this result by comparing it with the exponent of $2$ that we get when we do prime factorization of $11!$ as shown below:

The exponent of $2$ is $8$, which confirms that answer calculated by the alternate form is correct.

Applications of Legendre's theorem

Legendre's theorem is used to prove Kummer's theorem. In a special case, it is used to prove that 4 divides $\binom{2n}{n}$ where $n$ is a positive integer and not a power of $2$.