10
$\begingroup$

The answer to the following question would give an alternative solution to an old olympiad question if it is true.

Prove that there is no (constant) integer $c$ such that

$$1!+2!+\dots + q! \equiv c \bmod q \text{ for all $q \in \mathbb N^\ast$.}$$

($\mathbb N^\ast = \mathbb N \setminus \{0\}$)

$\endgroup$
  • $\begingroup$ $(1!+2!+\dots + q!) \bmod q$ is definitely not constant. See oeis/A067462. But that does not really answer the question. $\endgroup$ – lhf Nov 29 '16 at 12:35
  • $\begingroup$ Well, yes, there is no good reason for $c$ to exist, but to me it seems quite hard to prove that it does not exist. $\endgroup$ – Tara Nov 29 '16 at 14:05
  • $\begingroup$ It seems that the Chinese Remainder Theorem (together with a little bit of work to show that the system of congruences is consistent) implies that it is not possible to show that $c$ does not exist by working out what the value of $c$ is modulo $q$ for some finite set of values of $q$. (i.e. For any finite set of values for $q$, there is a $c$ that works.) This of course does not mean that there is a $c$ that works for all $q$, but we would need some other way of showing that. $\endgroup$ – Dylan Dec 4 '16 at 7:52
  • 3
    $\begingroup$ what does the $\ast$ mean in $\mathbb N^\ast$ ? $\endgroup$ – G Cab Mar 2 '17 at 15:20
  • $\begingroup$ This usually means that $0$ is excluded. $\endgroup$ – Phira Mar 3 '17 at 23:36
3
+150
$\begingroup$

Let $K(q)=\sum_{k=1}^{q-1} k!$.Since $q!\equiv0\pmod{q}$, thus $c$ is an integer such that for every postive integer $q$, we have $K(q)\equiv c\pmod q$. for instance, we have $K(q!)\equiv c\pmod{q!}$. But by definition of $K$, we know that $K(q!)\equiv K(q)\pmod{q!}$ which leads to $K(q)\equiv c\pmod{q!}$. Hence there is a sequence of integers like $(k_q)_{q\in\mathbb Z^+}$ such that $c=k_q\cdot q!+K(q)$. Now for every positive integer $q$:

$$0=c-c=k_{q+1}\cdot (q+1)!+K(q+1)-k_q\cdot q!-K(q)=\left((q+1)k_{q+1}-k_q+1\right)q!$$ $$\therefore\quad k_{q+1}=\dfrac{k_q-1}{q+1}$$

Now using induction we show that for every natural number $n$, we must have $|k_q|\ge q^n$. For the base case, we note that if $k_q=0$, then $k_{q+1}$ can't be an integer, so $|k_q|\ge1=q^0$. For the induction step, we have:

$$\dfrac{|k_q|+1}{q+1}\ge\dfrac{|k_q-1|}{q+1}=|k_{q+1}|\ge (q+1)^n$$ $$\therefore\quad|k_q|\ge(q+1)^{n+1}-1\ge q^{n+1}$$

But this leads to an obvious contradiction. So $c$ doesn't exist.

$\endgroup$
1
$\begingroup$

I found this question very interesting, since it's easy to prove that $c$ is not constant by example meanings, however, the relevant part is to give the proof mathematically, which I think I have found.

We assume that for $q=k$ ; $q=k+1$ and that $c$ is constant, so the following relations should hold:

$0 \equiv \sum_{i=1}^{k}i! - c \pmod k$

$0 \equiv \sum_{i=1}^{k+1}i! - c \pmod{k+1}$

Let's put all together:

$c=\sum_{i=1}^{k}i! -kp$

$0 \equiv \sum_{i=1}^{k+1}i! - \sum_{i=1}^{k}i! -kp \pmod{k+1}$

$0 \equiv (k+1)! + \sum_{i=1}^{k}i! - \sum_{i=1}^{k}i! -kp \pmod{k+1}$

$0 \equiv (k+1)! -kp \pmod{k+1}$

$p=\sum_{i=1}^{k}i! - c$

$0 \equiv (k+1)! -k(\frac{\sum_{i=1}^{k}i! - c}{k}) \pmod{k+1}$

$0 \equiv (k+1)! - \sum_{i=1}^{k}i! - c \pmod{k+1}$ ($*$)

Since $\sum_{i=1}^{k}i! - c$ is multiple of $k$ then for the latter ($*$) to be true we need that:

$GCD(k+1, \sum_{i=1}^{k}i! - c) \neq 1$

Maybe sounds a bit confusing at the first time, but makes sense. This attempt just tell us for $c$ to be constant the sum of the previous factorials minus $c$ has to be multiple of the current modulus.

For example, take k=5

$GCD(k+1, \sum_{i=1}^{k}i! - c) = GCD(6, 153 - 3) = GCD(6,150) = 6$ so both $k$ and $k+1$ will yield same $c$

but for k=6

$GCD(k+1, \sum_{i=1}^{k}i! - c) = GCD(7, 873 - 3) = GCD(7,870) = 1$ thus $c$ in $k$ and $c$ in $k+1$ yield $3$ and $5$ respectively.

Take into account that I have put some effort elaborating this answer, maybe there exists other simple proof, but I least I try to throw some light to the question.

$\endgroup$
  • $\begingroup$ You don't need that $c=3$ for $q=6$, and $c=5$ for $q=7$. You just need that $c \equiv 3 \pmod 6$ and $c \equiv 5 \pmod 7$. Which means that $c=33$ works for both $6$ and for $7$, for example. $\endgroup$ – Dylan Dec 4 '16 at 7:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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