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$?
 A: 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}.$$
