TMA4155 – exercise 2

Invert each of the matrices \[\begin{pmatrix}1&2&2\\3&2&1\\2&1&1\end{pmatrix}\] and \[\begin{pmatrix}1&2&3\\3&2&1\\2&1&1\end{pmatrix}\] modulo 10, if possible (or explain why it is not possible).

Solve each of the following congruence relations (or sets of such).

1. \(4x\equiv12\pmod{9}\)
2. \(3x+9\equiv21\pmod{8}\)
3. \(6x\equiv3\pmod{9}\)
4. \(6x\equiv4\pmod{9}\)
5. \(x\equiv7\pmod{8}\) and \(x\equiv3\pmod{5}\)

Exercise 24, page 108 in Trappe & Washington

Solve the system of congruence relations: \[ \begin{split} x&\equiv1\pmod 2\\ x&\equiv2\pmod 3\\ x&\equiv3\pmod 5\\ x&\equiv4\pmod 7\\ \end{split} \]

Let \(z=2^{8500}\bmod 10403\).

1. Notice that \(10403=101\cdot103\). Show that if you know \(x=2^{8500}\pmod{101}\) and \(y=2^{8500}\pmod{103}\), you can compute \(2^{8500}\pmod{10403}\) using the Chinese Remainder Theorem.
2. Use Fermat’s Little Theorem and exponent arithmetic to compute \(x\) and \(y\).
3. Compute \(z\).