Chinese Remainder Theorem, Solving For Multiplicative Inverses

[cwatki14]

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?
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\phi1)
N=-1(mod\phi2)
...
N=-(n-1)(mod\phin)
A unique solution exists since (\phin,\phim)=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...

 

[Petek]

A hint for your first question:

If a = b (mod m), then ax = bx (mod m).

Find a way to apply this to, say, the equation 77x = 1 (mod 3).

HTH

Petek

 

[ramsey2879]

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?
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\phi1)
N=-1(mod\phi2)
...
N=-(n-1)(mod\phin)
A unique solution exists since (\phin,\phim)=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 referringw to phi of n or phi of m more like phi sub n or phi sub m, but I am not entirely sure...

the answer to the first part is that you can always subtract 0 mod m from both sides. Therefore since 75x = 0 mod 3, 77x-75x =1-0 mod 3. the answer to the second part is to look for a recursive method to find N then see if that can be reduced to a direct formula as a function of n . The simple answer to the second part is different depending upon whether N is an negative or positive number. Assuming N is positive and n = 5 the second smallest number N would be 61.