- #1

- 57

- 0

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