ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 09 Dec 2018 20:28:31 +0100Solving linear congruencehttps://ask.sagemath.org/question/44618/solving-linear-congruence/ Is there a simple way to solve a linear congruence modulo an integer with large prime factors in Sage? `solve_mod` function cannot handle such large moduli apparently.kdr01Sun, 09 Dec 2018 20:28:31 +0100https://ask.sagemath.org/question/44618/Solving systems of congruences with Gaussian integershttps://ask.sagemath.org/question/44287/solving-systems-of-congruences-with-gaussian-integers/ I am writing my own function to solve systems of congruences in arbitrary euclidean domains, but I can't quite make it work for gaussians.
# Extended Euclides Algorithm
def extended_euclides(a,b,quo=lambda a,b:a//b):
r0 = a; r1 = b
s0 = 1; s1 = 0
t0 = 0; t1 = 1
while r1 != 0:
q = quo(r0, r1)
r0, r1 = r1, r0 - q * r1
s0, s1 = s1, s0 - q * s1
t0, t1 = t1, t0 - q * t1
return r0, s0, t0
# Chinese Remainder Theorem
def chinese_remainder(remainders, modules, quo=lambda a,b:a//b):
"""
INPUT:
A list of remainders v_i and pairwise coprime modules m_i
representing a system of congruences {x == v_i mod m_i},
where v_i, m_i belong to an euclidean domain ED
OUTPUT:
A solution of the system of congruences in the domain ED
"""
m = reduce(lambda x,y:x*y, modules)
c = 0
for v_i, m_i in zip(remainders, modules):
m_div_m_i = quo(m, m_i)
_, s_i, _ = extended_euclides(m_div_m_i, m_i, quo)
# c_i = (v_i * s_i) % m_i
# we need to do it convolutedly bcs gaussian integer quotient is not implemented in SageMath
a = v_i * s_i; b = m_i
c_i = a - quo(a,b)*b
c += c_i * m_div_m_i
return c
# EXAMPLE ON Z
remainders = [ZZ(2),ZZ(7)]
modules = [ZZ(11), ZZ(13)]
print("System to be solved:")
for r,m in zip(remainders, modules):
print("x == {} (mod {})".format(r,m))
solution = chinese_remainder(remainders, modules)
print("A solution of the system is {}".format(solution))
#check that the solution is correct
for r, m in zip(remainders, modules):
assert(solution % m == r)
# EXAMPLE ON Z[i]
ZI = QuadraticField(-1, 'I').ring_of_integers()
gaussian_quo = lambda a,b : ZI(real(a/b).round() + I*imag(a/b).round())
gaussian_rem=lambda a,b: a - gaussian_quo(a,b)*b
remainders = [ZI(2+3*I),ZI(7+5*I)]
modules = [ZI(11), ZI(13-I)]
print("System to be solved:")
for r,m in zip(remainders, modules):
print("x == {} (mod {})".format(r,m))
solution = chinese_remainder(remainders, modules, gaussian_quo)
print("A solution of the system is {}".format(solution))
#check that the solution is correct
for r, m in zip(remainders, modules):
print(gaussian_rem(solution, m) / r)
assert(gaussian_rem(solution, m) == r)
This produces the following ouptut:
System to be solved:
x == 2 (mod 11)
x == 7 (mod 13)
A solution of the system is 46
System to be solved:
x == 3*I + 2 (mod 11)
x == 5*I + 7 (mod -I + 13)
A solution of the system is -41*I - 75
1
36/37*I - 6/37
Error in lines 31-33
Traceback (most recent call last):
File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1188, in execute
flags=compile_flags) in namespace, locals
File "", line 3, in <module>
AssertionError
So in the integer example we find a correct solution, but in the Gaussian example we find a solution that satisfies the first incongruence relation, but not the second.
I have checked with wolfram alpha, and if I did not mess up it seems like the problem is in the Chinese Remainder Theorem algorithm rather than on the assertion tests.
What is going on?JsevillamolThu, 15 Nov 2018 10:57:43 +0100https://ask.sagemath.org/question/44287/Least-modulus description of congruenceshttps://ask.sagemath.org/question/26173/least-modulus-description-of-congruences/Suppose I'm given a bunch of residues mod $n$. Is there an efficient/elegant way to get sage to calculate the least modulus $m$ and set of residues mod $m$ which describes the same set? For example if I give it "0,2,4,6 mod 8" it should simply return "0 mod 2".ey8izndyoqFri, 13 Mar 2015 00:38:52 +0100https://ask.sagemath.org/question/26173/Check whether a modular subgroup is congruence from its generatorshttps://ask.sagemath.org/question/9691/check-whether-a-modular-subgroup-is-congruence-from-its-generators/I want to input the generators of a specific subgroup of the modular group $\Gamma = PSL(2,\mathbb{Z})$ as explicit $2\times 2$ matrices, and have Sage tell me whether that subgroup is congruence. Clearly I need to use the command `is_congruence()` for the second part, but I'm having trouble inputting the subgroup generators. Potentially it is something very simple - can anyone help? Thanks.JimereeSat, 05 Jan 2013 11:24:24 +0100https://ask.sagemath.org/question/9691/Permutation Representations and the Modular Grouphttps://ask.sagemath.org/question/9202/permutation-representations-and-the-modular-group/Hi!
Given a congruence subgroup of the modular group G = SL2Z, how can one use Sage to find the permutation representations of G on the cosets of each of those normal subgroups? Specifically I am looking at the subgroups on page 22 here: http://arxiv.org/pdf/1201.3633v2.pdf
Many thanks!
JimereeFri, 03 Aug 2012 11:19:42 +0200https://ask.sagemath.org/question/9202/