0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user88595 May 1 '14 at 16:57
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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