Ask Your Question
0

Sage is not returning all solutions to equations modulo n

asked 2015-06-24 11:05:16 -0500

Acanti gravatar image

updated 2015-06-24 11:25:08 -0500

calc314 gravatar image

I am trying to find all 2x2 matrices $S$ over $Z/9Z$ such that $S^3=I$, where I is the identity matrix. I am currently using the following procedure:

S = matrix(SR, 2, [[a,b],[c,d]]);
S3=S^3
l=solve_mod([S3[0,0]==1,S3[0,1]==0,S3[1,0]==0,S3[1,1]==1], 9);
l

The list of solutions (there are 207) I receive does not include S=[[1,3],[3,1]], for example, which does in fact satisfy $S^3=I$. I am new to Sage, is there something I am missing? How can I get a complete list of solutions?

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
0

answered 2015-06-24 11:35:32 -0500

fidbc gravatar image

Trying to find them using brute force isn't that bad. The following worked for me

import itertools
Z9=Zmod(9)
I=Matrix(Z9,[[1,0],[0,1]])
L=[]
for a,b,c,d in itertools.product(Z9,repeat=4):
    M=Matrix(Z9,[[a,b],[c,d]])
    if I==M^3:
        L.append(M)

The length of the list seems to be 297 though, but the 39th element seems to be the one that was missing from your list.

edit flag offensive delete link more

Comments

Thanks! This will fix my current problem, but I am still concerned for when I use larger matrices, and/or a different modulus. If anyone has ideas on a really efficient way to do this in general, I would love to hear them.

Acanti gravatar imageAcanti ( 2015-06-24 11:44:09 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2015-06-24 11:05:16 -0500

Seen: 86 times

Last updated: Jun 24 '15