# Find all solutions to this system of congruences

$$x \equiv 11 \pmod{84}$$ $$x \equiv 23 \pmod{36}$$

I have the bulk of the work done for this;
$x=11+84j$
$x=23+36k$

$\Rightarrow 11+84j \equiv 23 \pmod{36}$
$\Rightarrow 84j \equiv 12 \pmod{36}$
$\Rightarrow 12j \equiv 12 \pmod{36}$
$\Rightarrow j \equiv 1 \pmod{36}$
$\Rightarrow j = 1 + 36n$

Thus this system is true for any $x$ of the form $x=11+84(1+36n)=95+3024n$.

However, I know from messing around when trying to solve this that all $x$ of this form are not the entirety of the $x$ which satisfy the system; that would be $x=95+252n$.
I've also observed that $252$ is the lowest common multiple of $36$ and $84$, but I don't know how to tie this together to give a concrete method to finding all the solutions.

-
If there is a solution of the system $x\equiv a\bmod{m}$, $x\equiv b\pmod{n}$, there is a unique solution modulo $\text{lcm}(m,n)$. –  André Nicolas Apr 12 at 0:37
Ah, so using this fact I could take $95+3024n \pmod{lcm(36, 84)=252} = 95 \pmod{252}$, thus conclude that $x=95 + 252n$ was a set of solutions. Is there something obvious I'm missing then to conclude that this spans all possible values of $x$ which are solutions? –  user142340 Apr 12 at 0:44
The result mentioned in my previous comment is standard when one discusses the Chinese Remainder Theorem. It is often not noticed, because in most examples we choose pairwise relatively prime moduli. –  André Nicolas Apr 12 at 0:47
You could have also gotten there directly, since $84j\equiv 12\pmod{36}$ if and only if $7j\equiv 1\pmod{3}$ iff $j\equiv 1\pmod{3}$. –  André Nicolas Apr 12 at 0:55
I presume this result can be generalised to $n$ cases, or at least 3? –  user142340 Apr 12 at 0:57

Correct is: $\ 12j\equiv 12\pmod {36}\iff 36\mid 12(j-1)\overset{\rm cancel\ 12}\iff \color{#c00}3\mid j-1\iff \color{#0a0}{j = 1+3n}.$

Therefore $\ x = 11+84\,\color{#0a0}j = 11+84(\color{#0a0}{1+3n}) = 95 + 252n,\,$ as claimed.

-
Ah, I wondered why my approach hadn't yielded the correct answer, or at least all of them; I need to be mindful of cancelling in modular arithmetic. Many thanks, your help has been much appreciated over a number of queries. –  user142340 Apr 12 at 1:02
@user142340 Not to worry, almost everyone slips up there when first learning the peculiarities of modular arithmetic. –  Bill Dubuque Apr 12 at 1:05