## 10.4 Solving Modular Linear Equations  Next we discuss solving the modular equation  for *x*, where *x* is an equivalence class modulo *n*, and *m, n* > 0. We will apply this result in [Section 10.7](LiB0088.html#1212) when we develop the RSA cryptosystem. Let <\[*m*\]*n*> be the subgroup generated by \[*m*\]*n* relative to the group (*Zn* +). Since <\[*m*\]*n*> = {\[0\]*n*, \[*m*\]*n*, \[2*m*\]*n*, …}, [Equation 10.12](#ch10eqn12) has a solution if and only if  Example 10.45****Consider the group (**Z**8, +). Since ****  the equation  has a solution if and only if \[*k*\]8 is \[0\]8, \[6\]8, \[4\]8, or \[2\]8. For example, solutions to  are *x* = \[2\]8 and *x* = \[6\]8. The following theorem tells us precisely the elements of the set 〈\[*m*\]*n*〉. Theorem 10.23****Consider the group (**Z***n*, +). For any \[*m*\]*n* ∊ **Z***n*, we have that ****  where *d* = gcd(*n, m*). This means  Proof: First show 〈\[*d*\]*n*〉 ⊆ 〈\[*m*\]*n*〉. Owing to [Theorem 10.2](LiB0081.html#1005), there exists integers *i* and *j* such that  Owing to the previous equality, for any integer *k*,  which means \[*kd*\]*n* = \[*kim*\]*n*, and therefore \[*kd*\]*n* ∊ 〈\[*m*\]*n*〉, We conclude that 〈\[d\]n〉 ⊆. Next show 〈\[m\]n〉 ⊆ 〈\[d\]n〉. Since *d*|*m*, there is an integer *i* such that *m* = *id.* Therefore, for any integer *k*,  which means 〈\[km\]n〉 ∊ 〈\[d\]n〉 . We conclude 〈\[m\]n〉 ⊆ 〈\[d\]n〉. The final result follows from the results just established and [Theorem 10.20](LiB0083.html#1094). Corollary 10.6****The equation ****  has a solution if and only if *d*/*k*, where *d* = gcd(*n, m*). Furthermore, if the equation has a solution, it has *d* solutions. Proof: As mentioned at the beginning of this section, the equation has a solution if and only if  Since [Theorem 10.23](#ch10ex77) implies  this means the equation has a solution if and only *d*’*k*’ for some *k*’ ∊ \[*k*\]*n.* Since \[*k*\]*n* is an equivalence class modulo *n* and *d*|*n*, clearly *d*|*k*’ for one *k*’ ∊ \[*k*\]*n* if and only if it does so for all members of \[*kn.* This proves the first part of the corollary. As to the second part, according to [Theorem 10.23](#ch10ex77), *ord*<\[*m*\]*n*) = *n*/*d.* Therefore, owing to [Corollary 10.4](LiB0083.html#1100), the sequence  has period *n*/*d* and the first *n*/*d* items are distinct. This means, if \[k\]*n* ∊ <\[*m*\]*n*>, that \[*k*\]*n* appears exactly *d* times in the set  Clearly, each of these appearances is owing to a different member of **Z***n.* This completes the proof. Corollary 10.7****The equation ****  has a solution for every equivalence class \[*k*\]*n* if and only if gcd(*n, m*) = 1. Furthermore, if this is the case, each \[*k*\]*n* has a unique solution. Proof: The proof follows immediately from [Corollary 10.6](#ch10ex78). Corollary 10.8****The equivalence class \[*m*\]*n* has a multiplicative inverse modulo *n* if and only if gcd(*n, m*) = 1. That is, the equation ****  has a solution if and only if gcd(*n, m*) = 1. Furthermore, if it has an inverse, that inverse is unique. Proof: The proof follows immediately from [Corollary 10.6](#ch10ex78). The uniqueness actually also follows from [Theorem 10.16](LiB0083.html#1078). Example 10.46****Consider the group (**Z**8, +). Since gcd(8, 6) = 2, according to [Theorem 10.23](#ch10ex77), ****  which agrees with our result in [Example 10.45](#ch10ex76). Owing to [Corollary 10.6](#ch10ex78), the equation  has exactly two solutions when \[*k*\]8 is any member of 〈\[6\]8〉. In [Example 10.45](#ch10ex76), we noted the two solutions when \[*k*\]8 = \[4\]8 are *x* = \[2\]8 and *x* = \[6\]8. Example 10.47****Consider again the group (**Z**8, +). Since gcd(8, 5) = 1, according to [Theorem 10.23](#ch10ex77), ****  According to [Corollary 10.7](#ch10ex79), the equation  has exactly one solution when \[*k*\]8 is any member of 〈\[5\]8〉. For example, when \[*k*\]8 = \[3\]8, the solution is *x* = \[7\]8. Example 10.48****Consider **Z**9. Since gcd(9, 6) = 3, [Corollary 10.8](#ch10ex80) implies \[6\]9 does not have a multiplicative inverse modulo 9. Since gcd(9, 5) = 1, [Corollary 10.8](#ch10ex80) implies \[5\]9 does have a multiplicative inverse modulo 9. That inverse is \[2\]9. **** Theorem 10.24****Let *d* = gcd(*n, m*) and let *i* and *j* be integers such that ****  (We know from [Theorem 10.2](LiB0081.html#1005) that such *i* and *j* exist.) Suppose further *d*|*k.* Then the equation  has solution  Proof: Owing to Equality 10.13, we have  Since  is an integer, we can multiply both sides of this equality by  yielding  which means  This proves the theorem. Example 10.49****Consider the equation ****  We have gcd(8, 6) = 2,  and 2|4. Therefore, the previous theorem implies the equation  has solution  Theorem 10.25****Suppose the equation ****  is solvable, *x* = \[*j*\]*n* is one solution, and *d* = gcd(*n, m*). Then the *d* distinct solutions of this equation are  Proof: Owing to [Corollary 10.6](#ch10ex78), there are exactly *d* solutions. Clearly,  So the *d* modulo classes in Expression 10.14 are all distinct. We complete the theorem by showing each of these classes is a solution to the equation. Since \[*j*\]*n* is a solution of \[*m*\]*n* *x* = \[*k*\]*n*,  Therefore, for *l* = 0, 1, …, *d* – 1,  which means  is also a solution to the equation. Example 10.50****In [Example 10.49](#ch10ex85), we showed that one solution of ****  is \[6\]8. Since gcd(8, 6) = 2, the previous theorem implies the other solution is  [Corollary 10.6](#ch10ex78), [Theorem 10.24](#ch10ex84), and [Theorem 10.25](#ch10ex86) enable us to write a simple algorithm for solving modular linear equations. That is, we first employ [Corollary 10.6](#ch10ex78) to see if a solution exists. If one does, we then use [Theorem 10.24](#ch10ex84) to find one solution and [Theorem 10.25](#ch10ex86) to find the other solutions. The algorithm follows: Algorithm 10.3 Solve Modular Linear Equation****Problem: Find all solutions to a modular linear equation **** Inputs: positive integers *m* and *n*, and integer *k.* Outputs: if the equation \[*m*\]*n* *x* = \[*k*\]*n* is solvable, all solutions to it. ``` void solve_linear (int n, int m, int k) { index l; int i, j, d; Euclid (n, m, d, i, j); // Call Algorithm 10.2. if (d|k) for (l = 0; l <= d - 1; l++) cout } ``` The input size in [Algorithm 10.3](#ch10ex88) is the number of bits it takes to encode the input, which is given by  The time complexity includes the time complexity of [Algorithm 10.2](LiB0082.html#1043) (Euclid's [Algorithm 2](LiB0015.html#146)), which we already know is *O*(*st*), plus the time complexity of the **for**-*l* loop. Since *d* can be as large as *m* or *n*, this time complexity is worst-case exponential in terms of the input size. However, we can do nothing about this since the problem requires that we compute and display an exponential number of values in the worst case.