The highest power of a prime that divides $f(x)$

I have read a result on computing the highest power of a prime that divides $n!$. I was wondering if there are any results on how to compute the highest power of a prime dividing $f(x)$, where $f$ is a function on the real numbers that outputs integer values.

-
For general $f$, apart from brute-force, I don't see how. – J. M. Nov 26 '10 at 7:18
Sorry I don't mean a general $f$. I meant whether do we have results for other specific functions like the one we have for factorials. – Derek Scavo Nov 26 '10 at 7:22

2 Answers

Finding divisors of combinatorial numbers can range from trivial to extremely difficult. I'm going to explain a technique that I used numerous times to find divisors of combinatorial numbers, particularly the number of Latin squares and Latin rectangles. (check out my website for numerous papers including this tactic).

Suppose you have a set $C$ and want to find $|C| \pmod \mu$ for some $\mu$.

Step 1: Identify a group $G$ such that (a) $G$ acts on $C$ and (b) $|G|$ divisible by $\mu$.

Let $B=\{x \in C:$ there exist a non-trivial $g \in G$ such that $gx=x\}$, that is, $B$ is the set of objects in $C$ that admit non-trivial automorphisms in $G$.

Note that $G$ acts on $C \setminus B$, and moreover, the orbit of any $x \in C \setminus B$ is of cardinality $|G|$ (by the Orbit-Stabiliser Theorem, when all the stabilisers are trivial). We can therefore deduce $|G|$ divides $|C \setminus B|$, and hence $|C| \equiv |B| \pmod {|G|}$ (and hence $|C| \equiv |B| \pmod \mu$).

Most of the time, $x \in C$ will not admit a non-trivial automorphism in $G$. This means, that if we want to compute $|C| \pmod \mu$, we can instead find $|B|$, which already results in a significant computational saving.

Sometimes, however, this approach is still inappropriate (e.g. $|B|$ could be massive). But not all is lost.

Step 2: Identify a set $A$ such that:

• $B \subseteq A \subseteq C$,
• $G$ acts on $A$,
• members of $A$ have some property (such as a certain substructure) that can be used to find a divisor $\nu$ of $|A|$ (in the case of Latin squares, the substructure is a subsquare, which we can replace by any other subsquare, inducing an equivalence relation on $A$, thus giving a divisor of $|A|$).

Then the same argument as above implies $|C| \equiv |A| \pmod {|G|}$ and so $\gcd(|A|,|G|)$ divides $|C|$. Since we know $\nu$ divides $|A|$ and $\mu$ divides $|G|$, we can deduce that $\gcd(\mu,\nu)$ divides $|C|$.

I depict this concept below. The area shaded gray represents $C$, and is partitioned into orbits by $G$. The blue orbits have cardinality $|G|$ and the red orbits have cardinality strictly less than $|G|$. We "break a bit off" and call it $A$. If we can find a divisor of $|A|$, then we can use it to find a divisor of $|C|$.

-

This brought to mind a conjecture I made a couple of years ago which involved a generalisation of the factorial function. The integer n! is the product of x taken over all integers from 1 to n and as you know Legendre (and also I think de Polignac) proved the highest power of a prime p diving n! is given by

(floor(n/p)) + (floor(n/p^2)) + (floor(n/p^3)) + . . ..

Define the arithmetical function

F(n) := Product {1<=x<=n,1<=y<=n} GCD(x,y).

Here GCD(x,y) is the greatest common divisor of x and y. Clearly, we can consider this function as a generalisation of n! = Product {1<=x<=n} GCD(x).

The sequence F(n) begins [1,1,2,6,96,480,414720,..], which I submitted as A092287 in the OEIS.

There I conjectured that the highest power of a prime p dividing F(n) is given by

(floor(n/p))^2 + (floor(n/p^2))^2 + (floor(n/p^3))^2 + . . ..

So F(n) is, in some sense, the next step up from n!. Continuing further in this manner, consider products of the GCD of triples of integers:

G(n) := Product {1<=x<=n,1<=y<=n,1<=z<=n} GCD(x,y,z).

See A129454 in the OEIS.

Calculation suggests that the highest power of a prime p diving G(n) is given by

(floor(n/p))^3 + (floor(n/p^2))^3 + (floor(n/p^3))^3 + . . ..

So we may have an infinite sequence n!, F(n), G(n), ... of arithmetical functions answering your question.

One can also use the least common multiple function LCM instead of the GCD function in the above to get similar though more complicated conjectural factorisation results. See A090494 in Sloane for an example. Finally, take a look at A092143 and A129365 for yet more conjectural factorisations which have a similar feel to Legendre's result.

-