Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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

2 Answers 2

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|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 at 1:02
1  
@user142340 Not to worry, almost everyone slips up there when first learning the peculiarities of modular arithmetic. –  Bill Dubuque Apr 12 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|improve this answer
2  
Why...why are you screaming at us? –  chubakueno Apr 12 at 1:34
    
@chubakueno: dude: what is going on in that little back yard? –  OC-Sansoo Apr 19 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 at 14:15
    
@chubakueno: cheers. –  OC-Sansoo Apr 19 at 20:55
    
@chubakueno: you are a good person. –  OC-Sansoo Apr 20 at 4:30

Your Answer

 
discard

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.