# Given $a$ and $n$, find $y \equiv \frac{n!}{a^x} \bmod a$

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$?

-
I'm confused. The multiplicative inverse of ${a^x} \mod a$ does not exist since $a$ and $a^x$ are not coprime. –  user2468 Oct 29 '11 at 3:31
I think what OP means is what is $n!$ mod $a$ when you take out all powers of $a$ from $n!$. In that sense $n!/(a^x)$ is a well-defined integer and we can consider it mod $a$. –  Patrick Da Silva Oct 29 '11 at 4:03
@J.D. We're obviously supposed to divide $a^x$ out of $n!$ before understanding it inside of $\mathbb{Z}/a\mathbb{Z}$. –  anon Oct 29 '11 at 4:03
Is there any purpose for this question or are you simply wondering? –  Patrick Da Silva Oct 29 '11 at 4:06
When $a$ is prime, this is an extension of Wilson's Theorem: $(a-1)! = -1$ mod $a$ ($a$ prime). So if $n=ak+r$ where $0 \leq r < a$, then $n!/a^x = [(a-1)!]^k+r!=(-1)^k+r!$ (mod $a$) or something like that (consider $(2a)!/a^2=1\cdots (a-1) 1\cdots(a-1) = [(a-1)!]^2$ mod $a$). For a non-prime modulus this would seem to be quite complicated. –  Bill Cook Oct 29 '11 at 4:17

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}.$$

-
Thx about your explanation. Very relevant. Unfortunally after "Now to compute..." I didn't undestand very well. Can you explain a little more how to find A and B parts? –  GarouDan Oct 29 '11 at 13:15
@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.) –  anon Oct 30 '11 at 1:59