Kvant Math Problem 1027
The number $1987$ is prime, since it is not divisible by any prime not exceeding $\sqrt{1987}<45$.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m24s
Source on kvant.digital
Problem
Prove that the number $1985!!+1986!!$ is divisible by $1987$. (Here $n!!$ denotes the product of all positive integers not exceeding $n$ and having the same parity, i.e., $n!!=n\cdot(n-2)\cdot(n-4)\cdot\ldots$.)
V. V. Proizvolov
Exploration
The number $1987$ is prime, since it is not divisible by any prime not exceeding $\sqrt{1987}<45$.
The double factorials separate the integers from $1$ to $1986$ according to parity:
$$1985!!=1\cdot3\cdot5\cdots1985,$$
$$1986!!=2\cdot4\cdot6\cdots1986.$$
Since the modulus is the prime $1987$, every nonzero residue class modulo $1987$ occurs exactly once among the integers $1,2,\dots,1986$. The odd product and the even product together partition all these residues.
A natural idea is to compare the even product with the odd product modulo $1987$. Because
$$1986\equiv -1 \pmod{1987},$$
the even numbers may be paired with negatives of odd numbers:
$$2\equiv -(1985),\quad 4\equiv -(1983),\quad \dots,\quad 1986\equiv -(1).$$
There are $993$ such pairs. Hence the product of all even numbers should be $(-1)^{993}$ times the product of all odd numbers, that is, the negative of it.
The crucial point is to justify this congruence carefully and then deduce that the sum of the two double factorials is congruent to zero modulo $1987$.
Problem Understanding
We must prove that
$$1987\mid\bigl(1985!!+1986!!\bigr).$$
This is a Type B problem. The statement is already given, so the task is to establish the divisibility.
The core difficulty is relating the product of all odd numbers up to $1985$ to the product of all even numbers up to $1986$ modulo the prime $1987$.
Proof Architecture
Let
$$O=1985!!,\qquad E=1986!!.$$
First, show that for each $k=1,2,\dots,993$,
$$2k\equiv -(1987-2k)\pmod{1987}.$$
This follows directly from $1987-2k+2k=1987$.
Next, multiply these congruences for all $k$ to obtain
$$E\equiv (-1)^{993}O \pmod{1987}.$$
The factors $1987-2k$ are precisely the odd numbers $1985,1983,\dots,1$.
Since $993$ is odd,
$$(-1)^{993}=-1,$$
and therefore
$$E\equiv -O \pmod{1987}.$$
Adding $O$ to both sides yields
$$O+E\equiv0\pmod{1987},$$
which is exactly the required statement.
The step most likely to fail under scrutiny is the identification of the numbers $1987-2k$ with all odd integers from $1$ to $1985$.
Solution
Set
$$O=1985!!=1\cdot3\cdot5\cdots1985,$$
and
$$E=1986!!=2\cdot4\cdot6\cdots1986.$$
For each integer $k$ with $1\le k\le 993$,
$$2k+(1987-2k)=1987,$$
hence
$$2k\equiv -(1987-2k)\pmod{1987}.$$
Multiplying these congruences for all $k=1,2,\dots,993$, we obtain
$$\prod_{k=1}^{993}(2k) \equiv (-1)^{993}\prod_{k=1}^{993}(1987-2k) \pmod{1987}.$$
The left-hand side is exactly $E$.
The numbers
$$1987-2,\ 1987-4,\ \dots,\ 1987-1986$$
are
$$1985,\ 1983,\ \dots,\ 1,$$
which are precisely all positive odd integers not exceeding $1985$. Therefore
$$\prod_{k=1}^{993}(1987-2k)=O.$$
Consequently,
$$E\equiv (-1)^{993}O \pmod{1987}.$$
Since $993$ is odd,
$$(-1)^{993}=-1,$$
so
$$E\equiv -O \pmod{1987}.$$
Adding $O$ to both sides gives
$$O+E\equiv0\pmod{1987}.$$
Thus
$$1985!!+1986!!$$
is divisible by $1987$.
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the passage from individual congruences to the product congruence. For every $k$,
$$2k\equiv -(1987-2k)\pmod{1987}.$$
Multiplication of congruences modulo a fixed modulus preserves congruence, so
$$(2)(4)\cdots(1986) \equiv (-1)^{993}(1985)(1983)\cdots(1) \pmod{1987}.$$
No division is involved, so there is no hidden assumption.
The second delicate step is identifying the factors $1987-2k$. When $k$ runs from $1$ to $993$, the values are
$$1985,1983,\dots,1.$$
There are exactly $993$ of them, and there are exactly $993$ positive odd integers not exceeding $1985$. Hence every such odd integer appears exactly once.
The third delicate step is the sign. Since
$$993=\frac{1986}{2},$$
and $993$ is odd,
$$(-1)^{993}=-1.$$
A mistaken parity computation here would reverse the conclusion.
Alternative Approaches
One may also use Wilson's theorem. Since $1987$ is prime,
$$1\cdot2\cdot3\cdots1986\equiv -1\pmod{1987}.$$
Writing this product as
$$(1985!!)(1986!!)=OE,$$
and using the congruence
$$E\equiv -O\pmod{1987},$$
obtained by pairing each even residue with the negative odd residue, gives
$$-O^2\equiv -1\pmod{1987},$$
hence $O^2\equiv1\pmod{1987}$. From $E\equiv -O$ the desired divisibility follows immediately.
The direct pairing argument used in the main proof is preferable because it reaches the conclusion without invoking Wilson's theorem and relies only on elementary properties of congruences.