# Solve the conditional congruence 371x ≡ 287 (mod 460)....

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.

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

## 1 Answer

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.