Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

I have the bulk of the work done for this;

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

share|cite|improve this question
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 '14 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 '14 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 '14 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 '14 at 0:55
I presume this result can be generalised to $n$ cases, or at least 3? – user142340 Apr 12 '14 at 0:57
up vote 1 down vote accepted

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.

share|cite|improve this answer
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 '14 at 1:02
@user142340 Not to worry, almost everyone slips up there when first learning the peculiarities of modular arithmetic. – Bill Dubuque Apr 12 '14 at 1:05

$x \equiv 11 \mod 84$ , so $x = 84k + 11$, and $x \equiv 23 \mod 36$, so $x = 36n + 23$. So:$84k + 11 = 36n + 23$, and $84k - 36n = 12$. So $7k - 3n = 1$. So$3n = 7k -1$, and $n = \dfrac{7k-1}{3} = 2k + \dfrac{k-1}{3}$. Thus $3 | k-1$, and $k = 3t + 1$, and $n = 2(3t+1) + t = 7t +2$. So$x = 36n + 23 = 36(7t + 2) + 23 = 252t + 95$ with $t \in \mathbb{Z}$

share|cite|improve this answer
Why...why are you screaming at us? – chubakueno Apr 12 '14 at 1:34
@chubakueno: dude: what is going on in that little back yard? – DeepSea Apr 19 '14 at 13:24
Lol it was just a joke, but you have to admit this automatically gets everyone's attention(including mine), so it is not my fault... – chubakueno Apr 19 '14 at 14:15
@chubakueno: cheers. – DeepSea Apr 19 '14 at 20:55
@chubakueno: you are a good person. – DeepSea Apr 20 '14 at 4:30

Find all solutions for x≡11 (mod 84) and x≡23 (mod 36).

x≡11 (mod 84) and x≡23 (mod 36) are equivalent to x=11+84y and x=23+35z where x,y,z ∈Z, respectively.

Here is a link to a PDF file for my solution:

The following images were generated from the PDF file above.

enter image description here enter image description here

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.