For each odd prime number $p$, prove that the integer $$1!+2!+3!+\cdots +p!-\left\lfloor \frac{(p-1)!}{e}\right\rfloor$$is divisible by $p$ (Here, $e$ denotes the base of the natural logarithm and $\lfloor x\rfloor$ denotes the largest integer that is less than or equal to $x$.)
Problem
Source: Simon Marais MC 2019 B2
Tags: factorial, number theory
14.10.2019 21:23
We have \begin{align*} \left\lfloor \frac{(p-1)!}{e}\right\rfloor & = \lfloor (p-1)!\cdot e^{-1}\rfloor \\ & = \left\lfloor (p-1)!\left( \sum_{k=0}^{\infty}{\frac{(-1)^k}{k!}}\right) \right\rfloor \\ & = (p-1)!\left( \sum_{k=0}^{p-2}{\frac{(-1)^k}{k!}}\right)\\ & \equiv \sum_{k=0}^{p-2}{(p-k-1)!} \pmod{p}\\ & = \sum_{t=1}^{p-1}{t!}. \end{align*}
16.10.2019 08:55
I solved it the same way. With a bit more elaboration... We begin by making the computation \[ \begin{aligned} \sum_{k = 1}^{p - 1} k! &\equiv \dfrac{(p - 1)!}{1} + \dfrac{(p - 1)!}{p - 1} + \dfrac{(p - 1)!}{(p - 1)(p - 2)} + \cdots + \dfrac{(p - 1)!}{(p - 1) \cdots (2)} &\pmod{p} \\ &\equiv \dfrac{-1}{1} + \dfrac{-1}{-1} + \dfrac{-1}{(-1)(-2)} + \cdots + \dfrac{-1}{(-1) \cdots (2 - p)} &\pmod{p} \\ &\equiv -\sum_{k = 0}^{p - 2} \dfrac{(-1)^k}{k!}. &\pmod{p} \\ \end{aligned} \] We then take a slight detour into Maclaurin series. The closest fraction of the form $\dfrac{q_k}{k!}$ to $\dfrac{1}{e} = e^{-1}$ is exactly of the form $\displaystyle{\sum_{j = 0}^k \dfrac{(-1)^j}{j!}}$. This is motivated by expanding $\displaystyle{e^x = \sum_{i = 0}^{\infty} \frac{x^i}{i!}}$. By analyzing the error, we determine that it is indeed at most $\dfrac{1}{(k + 1)!}$, meaning that a different choice of $q_k$ yields a larger error. Now let $k$ be an odd number. We can easily see that \[ \displaystyle{\frac{k!}{e} = q_k + \sum_{j = k + 1}^{\infty} \frac{k! (-1)^j}{j!}}, \] where $\displaystyle{\left|\sum_{j = k + 1}^{\infty} \frac{k! (-1)^j}{j!}\right| < 1}$. Therefore $\displaystyle{q_k = \left\lfloor \frac{k!}{e} \right\rfloor}$, because then the error term is $> 0$. We can also see that \[ \displaystyle{\frac{(k + 1)!}{e} = (k + 1)q_k + \sum_{j = k + 1}^{\infty} \frac{(k + 1)! (-1)^j}{j!} = (k + 1)q_k + (-1)^{k + 1} + \sum_{j = k + 2}^{\infty} \frac{(k + 1)! (-1)^j}{j!}}, \] where $\displaystyle{\left|\sum_{j = k + 2}^{\infty} \frac{(k + 1)! (-1)^j}{j!}\right| < 1}$. We then see that $\displaystyle{(k + 1)q_k = \left\lfloor \frac{(k + 1)!}{e} \right\rfloor}$. Let us substitute $k = p - 2$. We obtain, \[ \left \lfloor \frac{(p - 1)!}{e} \right \rfloor \equiv (p - 1) q_{p - 2} \equiv -q_{p - 2} \equiv -\left \lfloor \frac{(p - 2)!}{e} \right \rfloor \pmod{p}. \] We can then compute \[ -(p - 2)! \sum_{k = 0}^{p - 2} \dfrac{(-1)^k}{k!} \equiv -q \equiv -\left\lfloor \frac{(p - 2)!}{e} \right\rfloor \equiv \left\lfloor \frac{(p - 1)!}{e} \right\rfloor \pmod{p}, \] and with a bit more magic we get \[ \begin{aligned} -(p - 1)! \sum_{k = 0}^{p - 2} \dfrac{(-1)^k}{k!} &\equiv (p - 1)\left\lfloor \frac{(p - 1)!}{e} \right\rfloor &\pmod{p} \\ -(-1) \sum_{k = 0}^{p - 2} \dfrac{(-1)^k}{k!} &\equiv -\left\lfloor \frac{(p - 1)!}{e} \right\rfloor &\pmod{p} \\ -\sum_{k = 0}^{p - 2} \dfrac{(-1)^k}{k!} &\equiv \left\lfloor \frac{(p - 1)!}{e} \right\rfloor &\pmod{p} \\ \sum_{k = 1}^{p - 1} k! &\equiv \left\lfloor \frac{(p - 1)!}{e} \right\rfloor, &\pmod{p} \\ \end{aligned} \] as desired.
13.08.2022 12:28
Same proof as above, notice however that we don't need p to be prime