- #1
cwatki14
- 57
- 0
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[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...
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...