10

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\}$)

Tara
  • 404
  • 1
  • 3
  • 13
  • $(1!+2!+\dots + q!) \bmod q$ is definitely not constant. See [oeis/A067462](https://oeis.org/A067462). But that does not really answer the question. – lhf Nov 29 '16 at 12:35
  • 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. – Tara Nov 29 '16 at 14:05
  • 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. – Dylan Dec 04 '16 at 07:52
  • 3
    what does the $\ast$ mean in $\mathbb N^\ast$ ? – G Cab Mar 02 '17 at 15:20
  • This usually means that $0$ is excluded. – Phira Mar 03 '17 at 23:36

2 Answers2

4

Let $ K ( q ) = \sum _ { k = 1 } ^ { q - 1 } k ! $. Since $ q ! \equiv 0 \pmod q $, thus $ c $ is an integer such that for every positive 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 ) = \big( ( q + 1 ) k _ { q + 1 } - k _ q + 1 \big) q ! $$ $$ \therefore \quad k _ { q + 1 } = \frac { 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 | \ge 1 = q ^ 0 $. For the induction step, we have: $$ \frac { | k _ q | + 1 } { q + 1 } \ge \frac { | 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.

Mohsen Shahriari
  • 6,563
  • 10
  • 29
  • 69
1

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.

kub0x
  • 2,107
  • 1
  • 14
  • 25
  • 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. – Dylan Dec 04 '16 at 07:49