So I am working on solving sets of linear congruence with the chinese remainder theorem. When I go to solve for the inverses I am meeting a bit of trouble. What do I do when the a term is larger that m?(adsbygoogle = window.adsbygoogle || []).push({});

Example

77x=1(mod3)

33y=1(mod7)

21z=1(mod11)

where x,y,z are the inverses I am trying to solve for so I can use the chinese remainder thm. I usually solve for congruences by applying the euclidean algorithm backwards, but I have never encountered the situation where the a term is larger than the modulo m.... What do I do to solve for these inverses?

Also, I am looking at a system of linear congruences like the following

N=0(mod[tex]\phi[/tex]1)

N=-1(mod[tex]\phi[/tex]2)

...

N=-(n-1)(mod[tex]\phi[/tex]n)

A unique solution exists since ([tex]\phi[/tex]n,[tex]\phi[/tex]m)=1 whenever m does not equal n.

So it asks when n=2 what is the least possible value of N? How do I do this/ solve for the inverses? I didn't think it was referring to phi of n or phi of m more like phi sub n or phi sub m, but I am not entirely sure...

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Chinese Remainder Theorem, Solving For Multiplicative Inverses

**Physics Forums | Science Articles, Homework Help, Discussion**