1
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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)$.

| cite | improve this answer | |
$\endgroup$

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.