1
$\begingroup$

Take $n!$ and find $x$, where $a^x$ is the greatest power of $a$ who divides $n!$

Then find $y$, where $y \equiv \frac{n!}{a^x} \bmod a$

For example,

if $a=3$ and $n=6$ then

$6!=2\times3\times4\times5\times6=3^2\times80 \Rightarrow 3^2\times2 \Rightarrow (x=2, y=2)$.

How to find $x$ and $y$ without a computer or computing sucessives divisions? How can we do a explicit formula to find $x$ and $y$ to express $n!$ in this way in $a$?

  • 0
    @BillCook do this to primes it's still interesting. But looks like your formula it's$a$bit wrong. $\frac{(2a)!}{a^2}\equiv 1\times2\times...\times(a-1)\times1\times2\times...\times(a-1)\times2\equiv [2(a-1)!]^2\bmod a$. Yes$a$little dificult generalize this to non-primes and all $n$'s.2011-10-29

1 Answers 1

1

This is probably too unwieldy to be of use by hand, but it provides for a bit of reduction that might prove useful for a potential algorithm.

Factorize $a=p_1^{e_1}\cdots p_k^{e_k}$ and write $x=x_n(a)$ as a function of $a$. Decompose it as: $x_n(a)=\min\{x_n(p_1^{e_1}),x_n(p_2^{e_2}),\dots,x_n(p_k^{e_k})\}. \tag1$

The exponent in the highest power of a prime $q$ dividing $n!$ is given by de Polignac's formula:

$v_n(q)=\sum_{l=1}\left\lfloor \frac{n}{q^l}\right\rfloor;$

The sum is finite with final index $l=\lfloor\log_qn\rfloor$. This tells us that our function for prime power arguments is $x_n(q^b)=\lfloor v_n(q)/b\rfloor$, which suffices to compute $x_n$ generally via $(1)$ above.

Now to compute $y=n!/a^x$, write it as a product of two parts: part A a product of all numbers that are $\le n$ and coprime with $a$, part B all other numbers in $1,\dots,n$. Since $\prod_{u\in\mathbb{Z}/a\mathbb{Z}^\times}u=1$ (that is, the product of all numbers in $1,2,\dots,a$ that are coprime with $a$, modulo $a$, is simply the multiplicative identity - this is a basic fact of abstract algebra) we may reduce the product of $A$ by ignoring all numbers coprime to $a$ in the intervals $[1,a],[a+1,2a],[2a+1,3a]\dots,[ma+1,(m+1)a]$, where we have that $(m+1)a$ is the last multiple of $a$ before or equal to $n$. Take all numbers in the last partial interval $[(m+1)a,n]$ and reduce them all modulo $a$, and you are left with $[1,(n)_a]$, where This makes part $A$ equal to $(n)_a!$ modulo $a$.

And to compute part $B$, first note that Polignac's formula says that the highest prime power of $p_i$ (one of the primes dividing $a$) that divides $n!$ is given by $v_n(p_i)$ defined above. So the product of all factors noncoprime with $n$ will be the product of all highest powers of primes $p_i$ dividing $n$, or

$\large(\circ)=\prod_{i=1}^k p_i^{v_n(p_i)}.$

If we divide this by $a^x$ we get

$\large B=\prod_{l=1}^k p_l^{v_n(p_l)-xe_l}.$

  • 0
    @GarouDan: I've put a little more work in but it might still be terse. Tell me if you want more clarification. (Also, I fixed part B because there was a slight error.)2011-10-30