Monday, November 16, 2009

Multiplicity of a Prime Factor

Definition 1: Multiplicity of a prime factor

The multiplicity of a prime factor of a given integer is the highest power of that factor that divides the integer.

Example 1: 60

The prime factorization of is 2*2*3*5

The multiplicity of 3 is 1. The multiplicity of 5 is 1. The multiplicity of 2 is 2.

Adrien-Marie Legendre came up with the following theorem regarding the multiplicity of a prime for n!. (For review of factorials (n!), see here)

Theorem 1: The multiplicity of a given prime p in n! is:

That is, let x = the multiplicity of a prime p.

Then px divides n! but px+1 does not.

Proof:

(1) If p is greater than n, then p doesn't divide n! and the answer is 0.

(2) So, we can assume p ≤ n.

(3) Let k be the largest power of p such that pk ≤ n.

(4) For each 1 ≤ i ≤ k, the number of integers from 1 to n that are divisible by pi but not divisible by pi+1 is:

If no numbers are divisible by pi, then floor(n/pi) = 0 [as does floor(n/pi+1)].

floor(n/pi+1) equals the number of integers that are greater than pi+1 and divisible by pi+1.

So the number of integers that are uniquely divisible by pi is the difference of these two floor functions.

(5) The value of px which divides n! is equal to the product of all the powers of p that divide any of the integers in the sequence from 1 .. n.

(6) So, the we can compute the value of x with:

(7) Putting this together, we see the following pattern:

(8) We can see for i=1, we have floor(n/p1), for i=2, we have 2*floor(n/p2) - 1*floor(n/p2), and for i=3, we have 3*floor(n/p3) - 2*floor(n/p3) and so on.

(9) The net result of this is that we rewrite the equation in step #7 to the following:

QED

References: