Finding the remainder of an exhausted $m!$

Question

For any prime $p$, let $n_p(m)$ denote the exponent of $p$ in the factorisation of $m!$, i.e. $m!=p^{n_p(m)}\cdot k$ with $p\not\mid k$.

I wonder if there is a general formula for $\frac{m!}{p^{n_p(m)}}$ modulo $p$?

I could not prove but I believe that the frequencies of $1,2,...,p-1$ are equal.

Answer 1

Does not seem to be that simple as we let things run high; I did primes 5, 7, 11. Seems reasonable to suggest 1, p-1 are the same and highest, after that not clear, although 5, 7 seem symmetric. I ran 11 pretty high, I guess if a+b = 11 then their counts are similar.

1 count 1330   2 count 1169   3 count 1169   4 count 1332 

1 count 2570   2 count 2220   3 count 2230   4 count 2210   5 count 2220   6 count 2550

1 count 121894   2 count 115087   3 count 99710   4 count 100842   5 count 113429   
6 count 112909   7 count 99693   8 count 99050   9 count 114123   10 count 123263 







int main()
{
   int p = 11;
   int count[p] ;
   int fac = 1;
   for(int i = 1; i < p; ++i) count[i] = 0;
   for(int i = 1; i <= 100000 * p; ++i)
   {
     int n = i;
     while ( n % p == 0 ) n /= p;
     n %= p;
     fac *= n;
     fac %= p;

     count[fac] = 1 + count[fac];
         cout << i << "  "  << fac <<  "  count " << count[fac] << endl;

   }
   for(int i = 1; i < p; ++i) cout << i << " count " << count[i] << "   " ;
   cout << endl << endl; 




    return 0 ;
}

Answer 2

With $k$ as in the question, define $F(m)$ to be the residue of $k$ modulo $p$.

A formula

Let $m=a+bp$, where $0\le a\le p-1$. Then, modulo $p$, $F(m)$ is congruent to $a!(p-1)!^bF(b)$. By Wilson's Theorem this simplifies to $a!(-1)^bF(b)$.

So, in general, let $$m=a_0+a_1p+a_2p^2+...+a_{2n-1}p^{2n-1},0\le a_i\le p-1.$$ Then, for $A=a_1+a_3+...+a_{2n-1}$, $F(m)$ is congruent, modulo $p$, to $$a_0!a_1!...a_{2n-1}!(-1)^A.$$

Frequencies

The formula shows that $F(m)$ is the product modulo $p$ $$F(a_0+a_1p) F(a_2+a_3p)...F(a_{2n-2}+a_{2n-1}p).$$ Therefore the frequencies for the $p^2$numbers $0!,1!,...,(p^2-1)!$ determine the frequencies for the $p^4$numbers up to $(p^4-1)!$ etc. etc.

For example, modulo 3 there are 4 1s and 5 2s from 0! to 8!

So up to 80! there are $4^2+5^2=41$ 1s and $2.4.5=40$ 2s.

Answer 3

Same about

$F(m,p) = F(m \mod p , p) \dot F(m \div p , p) \dot (-1)^{m \div p} $

with the integer division.