Modular equations, find x

Question

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.

I don't know how to continue. Please can anyone please help me.

Answer 1

first i will multiply the mod, so 8*9*7 = 504 then i will need to find n1, n2, and n3 so basically n1 = 9*7=63 n2=8*7=56 n3=8*9=72 so now set up the equations since the mods are relatively prime then there gcd=1 so 63g1 congruent to 1 mod 8 56g2 congruent to 1 mod 9 72g3 congrent to 1 mod 7

we now can reduce the mod 7g1 congruent to 1 mod 8 2g2 congruent to 1 mod 9 2g3 congrent to 1 mod 7 using the multiplicative inverse of the mods g1=-1 g2=-4 g3=-3 now put everything together (-1*5*63)+(-4*3*56)+(-3*72*4)=-1851 which we can reduce usind congrent classes of 504 we will get 165 so x=165 all other possiple solution of x +{165 + 504k: k=0,1,2,3,4,...,n}

Answer 2

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

Answer 3

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