Ask Your Question

Revision history [back]

You can define a polynomial ring over $\mathbb{Z}/26\mathbb{Z}$ with an ideal in it generated by (the left-hand sides of) your equations, and calculate a Groebner basis of it with respect to a lexicographic monomial ordering. This will "triangularize" the system of equations, and if you are lucky you can solve it by successive substitutions. Here is the setup:

R = PolynomialRing(IntegerModRing(26), names='k_1,k_2,k_3,k_4,x1,x2', order='lex')
a,b,c,d,x1,x2 = R.gens()
K = Matrix(R,[[a,b],[c,d]]); K

pl = vector(R,[1,29])
ci = vector(R,[8,21])
eq1,eq2 = (K*pl-ci)

pl = vector(R,[25,22])
ci = vector(R,[x1,-5])
eq3,eq4 = (K*pl-ci)

pl = vector(R,[7,16])
ci = vector(R,[x2,19])
eq5,eq6 = (K*pl-ci)

I = R.ideal([eq1,eq2,eq3,eq4,eq5,eq6])

I replaced $i$ by $-5$ because it will lead to a solution; the other option, i.e. $5$, doesn't.

sage: I.groebner_basis()
[k_1 + 15*x2 + 10, k_2 + 21*x2 + 20, k_3 + 9, k_4 + 16, x1 + 5*x2 + 14]

This can be viewed as a list of equations (set equal to zero). Each of these equations can be solved by putting its first term to the other side (so only x2 remains as an indeterminate). Indeed:

sage: [eq.subs(x1=-5*x2-14,k_4=-16,k_3=-9,k_2=-21*x2-20,k_1=-15*x2-10) for eq in [eq1,eq2,eq3,eq4,eq5,eq6]]
[0, 0, 0, 0, 0, 0]

The system of equations with $i$ replaced by $5$ is unsolvable because the Groebner basis contains the constant $2$, or, if you prefer: because 12*eq2 + 5*eq4 - eq6 evaluates to $2$ in that case.