Find $r$ from three moduli Determine $r$ in $$x\equiv  15 \pmod{77}\\
x\equiv 16 \pmod{78}\\
x\equiv r \pmod{14}$$
With lists in Excel, I have discovered that $x = 5944$.
$$5944\equiv  15 \pmod{77}\\
5944\equiv 16 \pmod{78}\\
5944\equiv r \pmod{14}\implies r=8$$
This is not an elegant solution. How can I take on the task in a more mathematical way?
 A: By Chinese Remainder Theorem, since $77$ and $78$ are coprime, there is only one solution for $x$ mod $77 \times 78$. (Note that $5944$ is not a unique solution)
Observe that $$x \equiv 15\pmod {77} \equiv -62 \pmod {77}$$
$$x \equiv 16\pmod {78} \equiv -62 \pmod {78}$$
hence $x \equiv -62 \pmod {77 \times 78}$.
Since $14 \mid 77 \times 78$, $x \equiv -62 \pmod {14} \equiv 8 \pmod {14}$.
A: Follows immediately by CCRT for congruences in A.P. (Arithmetic Progression), i.e.
$\!\!\bmod \color{#c00}{77\!+\!k}\!:\ x \equiv 15\!+\!\color{#c00}k \equiv 15\color{#c00}{-77} \equiv -62\ \ $ [for $\,k=0,1$]
so $\,x\equiv -62\pmod{\!77\ \&\ 78}\!\iff\! x\equiv -62\pmod{77\cdot 78}\ $ by CCRT = Constant-case CRT
so $\,x\equiv -62\equiv 8\pmod{\!\color{#0a0}{14}}\,$ by $\,\color{#0a0}{2(7)}\mid 78(77)\,$ & congruences persist mod factors of modulus.
Generally, $ $ as above: $\,\ \begin{align}&x\equiv a\ \ \ \pmod{\!n}\\ &x\equiv a\!+\!1\!\!\!\!\pmod{n\!+\!1}\end{align}\! \iff x\equiv a\!-\!n\pmod{\!\!n(n\!+\!1)}$
therefore again by persistence we infer$\ d\mid n(n\!+\!1)\,\Rightarrow\, x\equiv a\!-\!n\pmod{\!d}$
Remark $ $ Replying to a comment, note the above persistence follows from,$\,\color{#0a0}2\mid 78\,$ and $\,\color{#0a0}7\mid 77\,$ so alternatively we could use such persistence before applying CRT to get $\,x\equiv 16\equiv 0\pmod{\!2}\,$ and $\,x\equiv 15\equiv \color{#c00}8\pmod{\!7}$ so $\,x\equiv 8\pmod{\!14}\,$ by CRT, as in J.W.T's answer (alternatively $\,x\bmod{14}= 2(\color{#c00}{x/2} \bmod 7) = 2(\color{#c00}4)\,$ by $\,2\mid x\,$ and the mod Distributive Law).
The A.P. method has the advantage that we also get the (unique) solution $\bmod 77\cdot 78\,$ just as easily (and the techniques used are instructional). It will always be easy when the A.P. has very small step-size (like $\,s = 1\,$ above) since the linked formula involves inverting only $\,s\ $ (not the possibly larger moduli as when rotely applying the common CRT formula).
But it helps to be familiar with both methods, i.e. reducing before and after CRT. Interesting reults may arise by performing operations in different order, so it may well be worthwhile to investigate the ramifications of such a reordering.
A: $x\equiv15\bmod77\implies x\equiv 1\bmod 7$.
$x\equiv16\bmod78\implies x\equiv 0\bmod 2$.
Therefore, by the Chinese remainder theorem,
$x\equiv15\bmod77$ and $x\equiv16\bmod78\implies x\equiv\color{blue}8\bmod14$.
