- #1
jostpuur
- 2,112
- 19
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
<br /> \left(\begin{array}{c}<br /> \lbrack y_1\rbrack \\ \lbrack y_2\rbrack \\<br /> \end{array}\right)<br /> = \left(\begin{array}{cc}<br /> \lbrack a_{11}\rbrack & \lbrack a_{12}\rbrack \\<br /> \lbrack a_{21}\rbrack & \lbrack a_{22}\rbrack \\<br /> \end{array}\right)<br /> \left(\begin{array}{c}<br /> \lbrack x_1\rbrack \\ \lbrack x_2\rbrack \\<br /> \end{array}\right)<br />
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.
<br /> \left(\begin{array}{c}<br /> \lbrack y_1\rbrack \\ \lbrack y_2\rbrack \\<br /> \end{array}\right)<br /> = \left(\begin{array}{cc}<br /> \lbrack a_{11}\rbrack & \lbrack a_{12}\rbrack \\<br /> \lbrack a_{21}\rbrack & \lbrack a_{22}\rbrack \\<br /> \end{array}\right)<br /> \left(\begin{array}{c}<br /> \lbrack x_1\rbrack \\ \lbrack x_2\rbrack \\<br /> \end{array}\right)<br />
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.
Last edited:
