Sage is not returning all solutions to equations modulo n

asked 2015-06-24 18:05:16 +0200

Acanti
25 ●4

updated 2015-06-24 18:25:08 +0200

calc314
4191 ●22 ●48 ●113

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

add a comment

1 Answer

Sort by » oldest newest most voted

answered 2015-06-24 18:35:32 +0200

fidbc

2423 ●4 ●26 ●61

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

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 ( 2015-06-24 18:44:09 +0200 )edit

add a comment

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 18:05:16 +0200

Seen: 271 times

Last updated: Jun 24 '15

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.

Sage is not returning all solutions to equations modulo n edit