Solving simultaneous modular congruences

Let \{n_i\}_{i=1}^k be a set of pairwise relatively prime integers- that is, \mathsf{gcd}(n_i,n_j) = 1 whenever i \neq j.

  1. Show that the Chinese Remainder Theorem implies that for any \{a_i\}_{i=1}^k \subseteq \mathbb{Z}, there is a solution x \in \mathbb{Z} to the simultaneous congruences x \equiv a_i mod n_i and this solution is unique mod n = \prod n_i.
  2. Let n_i^\prime = n/n_i for each i; note that n_i^\prime and n_i are relatively prime by assumption. Let t_i be the inverse of a_i^\prime mod a_i. Prove that the solution x in part (a) is x = \sum a_it_in_i^\prime mod n. (Note that these t_i 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 a_i.)
  3. Solve the simultaneous system of congruences x \equiv 1 \mod 8, x \equiv 2 \mod 25, and x \equiv 3 \mod 81 and the system y \equiv 5 \mod 8, y \equiv 12 \mod 25, and y \equiv 47 \mod 81.

  1. Since the n_i are pairwise relatively prime, the ideals (n_i) are pairwise comaximal. By the Chinese Remainder Theorem, the map \varphi : \mathbb{Z} \rightarrow \prod \mathbb{Z}/(n_i) is surjective and has kernel (\prod n_i). Consider the element (\overline{a_i}) \in \prod \mathbb{Z}/(n_i); then there exists an element x \in \mathbb{Z} such that \varphi(x) = (\overline{x}) = (\overline{a_i}). By the First Isomorphism Theorem for rings, x is unique mod n.
  2. It suffices to show that this x is indeed a solution. To that end, consider \varphi(x) = (\sum a_it_in_i^\prime). Note that the jth coordinate of \varphi(x) is \sum a_it_in_i^\prime, taken mod n_j. By definition, n_j divides n_i^\prime for all i \neq j. Thus the jth coordinate of \varphi(x) is a_jt_jn_j^\prime \equiv a_j, since t_j is the inverse of a_j^\prime mod n_j. Thus \varphi(x) = (a_i) as desired.
  3. For both of these examples, we have n_1 = 8, n_2 = 25, and n_3 = 81 (certainly these are pairwise relatively prime). Thus n_1^\prime = 25 \cdot 81, n_2^\prime = 8 \cdot 81, and n_3^\prime = 8 \cdot 25. We wish to invert n_i^\prime mod n_i. Since n_1^\prime \equiv 1 mod 8, t_1 = 1. Since n_2^\prime \equiv -2 mod 25 and 25 - 2 \cdot 12 = 1, t_2 = 12. Since n_3^\prime \equiv 38 mod 81 and 38\cdot 32 - 15 \cdot 81 = 1, t_3 = 32.

    Thus x = \sum_{i=1}^3 a_i \cdot t_i \cdot n_i^\prime = 1 \cdot 1 \cdot 25 \cdot 81 + 2 \cdot 12 \cdot 8 \cdot 81 + 3 \cdot 32 \cdot 8 \cdot 25 \equiv 4377 mod 8 \cdot 25 \cdot 81.

    Similarly, y \equiv 15437 \mod 8 \cdot 25 \cdot 81.

Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: