# Solving a system of equation modul0 5

Consider the system of linear equations $$\begin{pmatrix} 6 & -3\\ 2 & 6 \end{pmatrix}\begin{pmatrix} x_1\\ x_2 \end{pmatrix}=\begin{pmatrix} 3\\ 1 \end{pmatrix}$$

a) Solve the system in $\mathbb{F}_5$

I just want to make sure my solution is correct:

We have: $$A=\begin{pmatrix} 6 & -3\\ 2 & 6 \end{pmatrix}\\ \Rightarrow A^{-1}= \frac{1}{42}\begin{pmatrix} 6 & 3\\ -2 & 6 \end{pmatrix}\\ \equiv \begin{pmatrix} 3 & \frac{3}{2}\\ -1 & 3 \end{pmatrix} \mbox{ } [5]$$

Therefore: $\begin{pmatrix} x_1\\ x_2 \end{pmatrix}=\begin{pmatrix} 3 & \frac{3}{2}\\ -1 & 3 \end{pmatrix}\begin{pmatrix} 3\\ 1 \end{pmatrix}= \begin{pmatrix} \frac{21}{2}\\ 0 \end{pmatrix} [5]$

-
set the matrix $A$ up so the entries are in mod 5. Solve for $\mathbf{x}$ and put in mod 5. – Eleven-Eleven Sep 16 '13 at 15:07
@ChristopherErnst So before I find the inverse matrix of A, I need to find entries of A modulo 5 ? What I did is I looked for the value of the determinant modulo 5 and then multiplied the inverse of that value with $\begin{pmatrix} 6 & 3\\ -2 & 6 \end{pmatrix}$ – Jean-Francois Rossignol Sep 16 '13 at 15:11
The LinearAlgebra[Modular][LinearSolve] command of Maple ( see maplesoft.com/support/help/Maple/… )solves linear systems mod q. – user64494 Sep 16 '13 at 16:32

Note that modulo $5$ one has $$A = \begin{bmatrix} 6 & -3\\ 2 & 6 \end{bmatrix} = \begin{bmatrix} 1 & 2\\ 2 & 1 \end{bmatrix}.$$ The latter matrix has determinant $-3 \equiv 2$, whose inverse is $3$, so $$A^{-1} = \begin{bmatrix} 3 & -1\\ -1 & 3 \end{bmatrix}.$$ Now $$\begin{bmatrix} x_{1}\\x_{2} \end{bmatrix} = A^{-1} \begin{bmatrix} 3\\ 1 \end{bmatrix} = \begin{bmatrix} 3 & -1\\ -1 & 3 \end{bmatrix}. \begin{bmatrix} 3\\ 1 \end{bmatrix} = \begin{bmatrix} 3\\ 0 \end{bmatrix},$$ which is your result, as $$\frac{21}{2} \equiv 21 \cdot 3 \equiv 3 \pmod{5}.$$

-
I like this method better. Thank you – Jean-Francois Rossignol Sep 16 '13 at 15:28
@Jean-FrancoisRossignol, you're welcome! – Andreas Caranti Sep 16 '13 at 15:28
How did you calculate the value of 2 modulo 5 ? – Jean-Francois Rossignol Sep 16 '13 at 15:39
In $\mathbb F_5$, $2^2=4$, $2^3=3$, and $2^4=1$, so that $1/2=3$. – Lubin Sep 16 '13 at 15:43

This method is legitimate since, if a solution exists, the determinant is non-zero mod $5$, and thus is invertible mod $5$.

To continue, $21 \equiv 1 \pmod 5$ and $\frac{1}{2}=2^{-1} \equiv 3 \pmod 5$.

So the solution becomes $$\begin{bmatrix} 3 \\ 0 \\ \end{bmatrix}.$$

-
Thank you for your answer. I just have an additional question: before look for $A^{-1}$ should I look for the values of the entries modulo 5 ? – Jean-Francois Rossignol Sep 16 '13 at 15:22
Either way is fine; it'll give the same inverse (although, sometimes it might reduce the arithmetic to reduce modulo $5$ first). Working in matrices over $\mathbb{Z}_5=\mathbb{Z}/5\mathbb{Z}$ means that reducing entries modulo $5$ result in equal matrices. This abstract algebra approach can make things easier. – Rebecca J. Stones Sep 16 '13 at 15:29