0
$\begingroup$

Solve the congruence:

a.) 371x ≡ 287 (mod 460)

b.)2837x ≡ 1601 (mod 1710)

-Currently covering a section on the Chinese remainder theorem and did several other conditional congruence problems but having a tough time figuring these ones out. Any help is appreciated.

$\endgroup$
2
  • $\begingroup$ You were not able to work backwards? $\endgroup$ Mar 10 '16 at 1:09
  • $\begingroup$ Is this one question or two separate questions? $\endgroup$ Mar 18 '16 at 15:10
1
$\begingroup$

Let's work backwards.

First, let's calculate the gcd of 371 and 460 using the Euclidean algorithm( I know it's 1, but we have to work through it anyway). $$ 460=1*371+89;371=4*89+15;89=5*15+14;15=1*14+1 $$ Now we do what is called working backwards:

$$ 1 = 15-14 = 15 - (89 - 5*15) = (371-4*89) - (460-371-5*(371-4*89)) \\ = (371-4*(460-371)) - (460-371 - 5*(371 - 4*(460-371))) \\ = (371 - 4*460 + 4*371) - 460 + 371 + 5*371-20*460+20*371 \\ = 31*371 + (-25)*460. $$ That's it: Now find $(31*287) $mod$\ 460$.This will be $157$, so $x=157$. Indeed, $371*157 - 287 = 126*460$.

The other one will also be solved similarly. $$ 2837=1*1601+1236;1601=1*1236+365;1236=3*365+141;365=2*141+83 \\;141=1*83+58;83=1*58+25;58=2*25+8;25=3*8+1 $$ So again, the gcd is obtained as $1$. We work backward: $$ 1 \\ =25-3*8 \\ = (83-58) - 3*(58-2*25) \\ = ((365-2*141) - (141-83)) - 3* ((141-83) - 2*(83-58)) \\ = (((1601-1236)-2*(1236-3*365)) - ((1236-3*365)-(365-2*141))) \\- 3*(((1236-3*365)-(365-2*141))-2*((365-2*141)-(141-83)))... = $$ So on, so forth. We obtain, at the end, that $x=1543$. I'll leave the tedious details to you, hope you have got the gist of my argument. It is possible to do the above via CRT, yet I suggest you try this method. Occasionally, it can be rewarding.

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