# How to solve the following congruence with fewer steps

I have the following congruences

\begin{align*} 2n&\equiv3\pmod5\\ 3n&\equiv4\pmod7\\ 4n&\equiv5\pmod9\\ 5n&\equiv6\pmod{11} \end{align*}

I already know a way to solve it (multiply each congruence by the modular inverse of the coefficient of $n$, and then solve using Chinese Remainder Theorem), but the answer I get is

$$n = 3464 \equiv -1 \pmod {5 \cdot 7 \cdot 9 \cdot 11}$$

I'm thinking that this probably isn't a coincidence, so I am wondering if there was a quicker way to solve this problem. Thanks!

## 2 Answers

Rewrite as $$2n\equiv-2\!\!\!\pmod5,\\ 3n\equiv-3\!\!\!\pmod7,\\ 4n\equiv-4\!\!\!\pmod9,\\ 5n\equiv-5\!\!\!\pmod{11}.$$ Then there is an obvious answer, and the CRT proves that this answer is unique modulo $5\times7\times9\times11$.

For each $k$, $(-1) \cdot k \equiv k+1 \mod (2k+1)$, and so $n k \equiv k+1 \mod (2k+1)$ for $k$ in some set $S$ if $n \equiv -1 \mod \text{LCM}(2k+1 \; : \; k \in S)$.