Systems of Linear Congruences—Single Modulus - Introduction to Cryptography with Java Applets - page 140

FIGURE 6.2

public class ModIdentityMatrix extends ModSquareMatrix {

//Make a ModSquareMatrix whose diagonal elements are all 1, zeros elsewhere
public ModIdentityMatrix(int n,BigInteger mod) throws
MatricesNonConformableException {
//Call a super constructor first, making zero matrix
super(n,mod,true,false);
//Set the diagonal elements to 1
for (int i=1;i<=n;i++) array[i][i]=new BigInteger(“1”);

}

}

I have written a test applet called TestLinearSystemSolveApplet to test Gaussian elimi-
nation modulo m . Consider the congruence AX B (mod m ). The user enters the modulus
m , the square matrix of coefficients A , and a vector of constants B . If a unique solution X
exists modulo m , the applet will compute and display it. The applet and its source code can
be found on the topic's website. A screen shot is shown in Figure 6.2.

EXERCISES

1. Solve the following systems of linear congruences, if any solutions exist. For any sys-

tems that have multiple solutions, report all the solutions.
a. 2 x + 5 y 1 (mod 11)

3 x + 2 y 7 (mod 11)

b. 2 x + 5 y 1 (mod 11)

3 x + 2 y 6 (mod 11)

c. 4 x + 3 y + z 2 (mod 7)

y + 3 z 5 (mod 7)

2 x + 6 y + 3 z 0 (mod 7)