3
$\begingroup$

$\mathbb{P}$ is the prime numbers set.

$p \in \mathbb{P}$

$a,b,c \in \mathbb{N}$

$n=a p^b+c$ where

$c= n\bmod p$

$b$ is the highest power of $p$ who divides $n-c$

How to find $\beta$ where $\beta$ is the highest power of $p$ who divides $n!$?

And how to find $\alpha$ where $\alpha$ is $\dfrac{n!}{p^\beta}\bmod p$?

$n!=\alpha p^\beta$

Probably the answer will appear $a$, $b$, $c$, $p$ and factorials.

Obs.:

$x = y\bmod z \iff x \equiv y \pmod{z}$ and $0 \leq x \leq z-1$

$x,y,z \in \mathbb{N}$

  • 0
    What does "$c=\bmod (n,p)$" mean?2011-11-08
  • 0
    $c \equiv n \bmod p$2011-11-08
  • 2
    I'm not familiar with that notation; I do not think it is standard. If you mean that $c$ is the remainder of dividing $n$ by $p$, *sometimes* this is written $n\bmod p$ (`n\bmod p`), but I think you'll have to spell it out in the body to make it clear. In any case, use `\bmod` instead of `\mod`, to get the right phrasing.2011-11-08
  • 2
    I expect you are familiar with the fact that $\beta=\lfloor \frac{n}{p}\rfloor + \lfloor \frac{n}{p^2}\rfloor +\lfloor \frac{n}{p^3}\rfloor+\cdots$. We get a nice simple formula if $1\le a and $0 \le c, and something a bit messier otherwise.2011-11-08
  • 0
    I'm using the Mathematica notation `Mod[n,p]` is the remainder of dividing $n$ by $p$... But if you think will be more clear change it, please do it for me =)2011-11-08
  • 0
    In general, the highest power of the prime $p$ that divides $n!$ is given by $$\left\lfloor \frac{n}{p}\right\rfloor + \left\lfloor \frac{n}{p^2}\right\rfloor + \cdots + \left\lfloor\frac{n}{p^k}\right\rfloor + \cdots$$2011-11-08
  • 0
    It's true that $1 \leq a < p$ and $0 \leq c < p$, but how express your formula using $a,b,c,p$?2011-11-08
  • 0
    Hum... I'm trying to get the multiples of $p$ like: $$p,2p,3p,\ldots,(p-1)p,p^2,p^2+p,p^2+2p,\ldots,p^3+p,\ldots,$$ $$(p-1)p^3+(p-1)p^2+(p-1)p,\ldots,a p^b + (p-1)p^{b-1}+(p-1)p^{b-2}+\ldots+(p-1)p+c$$ but it's very hard find a summation for this... and find $\beta$ using $a$, $b$, $c$ and $p$.2011-11-08
  • 0
    If $0\le c, then until you run out of $p$'s, $\lfloor\frac{n}{p^k}\rfloor=ap^{b-k}$. If $a$ is also $, the required sum is just the finite geometric progression which I will write backwards as $a+ap+\cdots+ap^{b-1}$.2011-11-08
  • 0
    @AndréNicolas The truth is I wrote a thing wrong in above. $a$ could be greater than $p$. for $n=13$ and $p=2$ we have $13=n=3 \times p^2 +1$ and that sum need some improvement. I'll edit and return...But I know we can find the closed form using the $p$ multiples, but maybe it's the hard way.2011-11-09
  • 0
    @GarouDan: OK. For the $a$ term, if it is $\ge p$, we will have to add $\lfloor a/p\rfloor +\lfloor a/p^2\rfloor +\cdots$ to my earlier closed form. This sum is less attractive. We can characterize it in terms of coefficients in the base $p$ expansion of $a$, but that really no longer quite qualifies as a closed form.2011-11-09

0 Answers 0