Chinese Remainder Theorem, Solving For Multiplicative Inverses

  • Thread starter cwatki14
  • Start date
  • #1
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...
 

Answers and Replies

  • #2
Petek
Gold Member
364
9
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
 
  • #3
841
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 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.
 
Last edited:

Related Threads on Chinese Remainder Theorem, Solving For Multiplicative Inverses

  • Last Post
Replies
9
Views
8K
  • Last Post
Replies
3
Views
4K
  • Last Post
Replies
5
Views
6K
  • Last Post
Replies
10
Views
5K
Replies
1
Views
3K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
7
Views
8K
Replies
9
Views
6K
Top