Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.