## Solving simultaneous modular congruences

Let be a set of pairwise relatively prime integers- that is, whenever .

- Show that the Chinese Remainder Theorem implies that for any , there is a solution to the simultaneous congruences mod and this solution is unique mod .
- Let for each ; note that and are relatively prime by assumption. Let be the inverse of mod . Prove that the solution in part (a) is mod . (Note that these can be found quickly using the Euclidean Algorithm, and thus we can quickly find solutions to the system of congruences for any choice of the .)
- Solve the simultaneous system of congruences , , and and the system , , and .

- Since the are pairwise relatively prime, the ideals are pairwise comaximal. By the Chinese Remainder Theorem, the map is surjective and has kernel . Consider the element ; then there exists an element such that . By the First Isomorphism Theorem for rings, is unique mod .
- It suffices to show that this is indeed a solution. To that end, consider . Note that the th coordinate of is , taken mod . By definition, divides for all . Thus the th coordinate of is , since is the inverse of mod . Thus as desired.
- For both of these examples, we have , , and (certainly these are pairwise relatively prime). Thus , , and . We wish to invert mod . Since mod 8, . Since mod 25 and , . Since mod 81 and , .
Thus mod .

Similarly, .

### Like this:

Like Loading...

*Related*

or leave a trackback:

Trackback URL.