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 - The Fusion of Science and Community**

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

Loading...

Similar Threads - Chinese Remainder Theorem | Date |
---|---|

Generalization of Chinese Remainder Theorem | Apr 1, 2013 |

Find and Test Primes using the Chinese Remainder Theorem and Binary Search | Sep 20, 2010 |

Chinese remainder theorem (Gaussian ints) | Nov 23, 2009 |

The Chinese Remainder Theorem for moduli that aren't relatively prime | Nov 22, 2009 |

Chinese remainder theorem | Dec 6, 2008 |

**Physics Forums - The Fusion of Science and Community**