2x2 matrix with factor group elements

[jostpuur]

We fix some $N=1,2,3,\ldots,$ and define the factor group $\mathbb{Z}_N$ as $\mathbb{Z}/N\mathbb{Z}$, and denote the elements $x+N\mathbb{Z}$ as $[x]$, where $x\in\mathbb{Z}$. My question is that how do you solve $[x_1]$ and $[x_2]$ out of

$$\left(\begin{array}{c} \lbrack y_1\rbrack \\ \lbrack y_2\rbrack \\ \end{array}\right) = \left(\begin{array}{cc} \lbrack a_{11}\rbrack & \lbrack a_{12}\rbrack \\ \lbrack a_{21}\rbrack & \lbrack a_{22}\rbrack \\ \end{array}\right) \left(\begin{array}{c} \lbrack x_1\rbrack \\ \lbrack x_2\rbrack \\ \end{array}\right)$$

when $[y_1],[y_2],[a_{11}],[a_{12}],[a_{21}],[a_{22}]\in\mathbb{Z}_N$ are known constants.

First edit:

To clarify what I mean by "a solution", I'll show a one for the 1x1 case, where we seek to solve $[y]=[a][x]$.

If $[a]=0$ and $[y]\neq 0$, then there are no solutions.

If $[a]=0$ and $[y]=0$, then all $[x]\in\mathbb{Z}_N$ are solutions, and the number of different solutions is $N$.

If $[a]\neq 0$, we choose representatives $a,y\in\mathbb{Z}$ such that $0<a<N$ and $0\leq y<N$.

If $\textrm{gcd}(a,N)$ does not divide $y$, then there are no solutions.

If $\textrm{gcd}(a,N)$ divides $y$, then a solution exists, and the number of different solutions $[x]\in\mathbb{Z}_N$ is $\textrm{gcd}(a,N)$. So the solution is unique only if $\textrm{gcd}(a,N)=1$.

Above we interpret that if $y=0$, then $\textrm{gcd}(a,N)$ divides $y$.

The whole thing is surprisingly complicated, considering how simple the formula $[y]=[a][x]$ looks. So I would be expecting something similar, but more complicated for the 2x2 case. The greatest common divisor of $a_{11}a_{22} - a_{12}a_{21}$ with something is probably related to the solution?

Of course the problem is not really to write down an algorithm that would "solve" the problem, because that would be trivial. We could write a program that goes through all the $N^2$ possibilities for $([x_1],[x_2])$, and checks which one of them work. I'm seeking something reasonably analytic.

Second edit:

I think I already realized how the problem gets solved, and I probably spent more time describing the problem than solving it, which is peculiar of course... I haven't solved the whole thing yet fully though.

 

[Stephen Tashi]

Giving the problem a technical name, I'd called it "solving simultaneous linear equations in a finite field".

A useful digression would be to ask: What's the rellation between the solutions to to simultaneous linear Diophantine equations and the soluitons to linear equations in a finite field?

 

[Incnis Mrsi]

Giving the problem a technical name, I'd called it "solving simultaneous linear equations in a finite field".

What? Original poster didn’t say N must be prime. One can solve linear systems over rings with zero divisors (Ī mean ℤ_N for composite N), but it is a theory different from linear algebra over a field. Even solving one linear equation is a non-trivial problem since we, in general, can’t divide.