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