Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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] $

share|improve this question
    
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
add comment

2 Answers 2

up vote 5 down vote accepted

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}. $$

share|improve this answer
    
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
1  
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
add comment

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}.$$

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.