# Modular equations, find x

Problem: Find an integer $x$ such that $x = 5\pmod 8, x = 3 \pmod 9, x = 4 \pmod 7$.

Attempt: By the Chinese Remainder Theorem " Suppose $a_1,a_2,...a_k$ are integers pairwise relatively prime natural numbers, and $x_1, x_2, .....x_k$ are integers. There exists an integer $x$ such that $x = x_i($mod $a_i)$ for $i$ between $1 -s$. Moreover, $x$ is unique up to congruence mod $n = a_1 a_2 \cdots a_s$."

Then using the above theorem the $gcd(8,9,7) = 1$. Thus, $x$ is unique up to congruence mod $504 =8\times9\times7$.

Then $n = 504$. So $$r_1 = \frac{n}{8} = \frac{504}{8} = 63$$ $$r_2 = \frac{n}{9} = \frac{504}{9} = 56$$ $$r_3 = \frac{n}{7} = \frac{504}{7} = 72$$

So 63 is congruent to zero mod 9 and 7, and invertible mod 8.

• This post is hard to read. It would be easier if you used the formatting. this mainly involves using the dollar signs "$" to create equations. – user88595 May 1 '14 at 16:57 As a next step: note that$63\equiv -1 \ \mod 8$so that$7\times 63 \equiv -7\equiv 1 \mod 8$. So you take$7\times 63=441$as the multiplier associated with$8$. Then you do the same kind of thing to identify multipliers using the pairs$56,9$and$72,7$. Simpler,$\ x \equiv -3\,$mod$\,7,8\iff 7,8\mid x\!+\!3\iff 7\cdot 8\mid x\!+\!3\iff \color{#c00}{x\! +\! 3 = 56 k}.\,{\rm Hence\ \ mod}\ 9\!:\ 3 \equiv \color{#c00}{x\equiv 56k-3}\equiv 2k-3 \iff 2k\equiv 6\iff k\equiv 3\qquad\qquad\qquad\iff {k = 3\!+\!9j\iff x = \color{#c00}{56}(3\!+\!9j)\color{#c00}{-3}\, =\, 165 + 504j}\$