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
    I'm confused. The multiplicative inverse of ${a^x} \mod a$ does not exist since $a$ and $a^x$ are not coprime.2011-10-29
  • 0
    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$.2011-10-29
  • 0
    @J.D. We're obviously supposed to divide $a^x$ out of $n!$ before understanding it inside of $\mathbb{Z}/a\mathbb{Z}$.2011-10-29
  • 0
    Is there any purpose for this question or are you simply wondering?2011-10-29
  • 0
    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.2011-10-29
  • 0
    @PatrickDaSilva is right. $\frac{n!}{a^x}$ is always integer, because, $a^x$ should always divide $n!$.2011-10-29
  • 0
    The propose behind this question is I'm need a bit different way to calculate modulus. if $n>a$, $n! \equiv 0 \bmod a$, but, if we take all $a$ powers of $n!$, what's the final result? Interesting question, doesn't it?2011-10-29
  • 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
    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?2011-10-29
  • 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