help()


## Welcome to Sage 6.4!

• Online documentation: View the Sage documentation online.

• Help: For help on any object or function, for example matrix_plot, enter matrix_plot? followed by tab or shift+enter. For help on any module (or object or function), for example, sage.matrix, enter help(sage.matrix).

• Tab completion: Type obj followed by tab to see all completions of obj. To see all methods you may call on obj, type obj. followed by tab.

• Source code: Enter matrix_plot?? followed by tab or shift+enter to look at the source code of matrix_plot.

• License information: For license information about Sage and its components, enter license().

i

I
i is I

True
SR --> ZZ[i]
reset()

K.<i> = QuadraticField(-1)
R = K.maximal_order()

a = matrix(R, 2, [1,2,3+i,7*i])

a.smith_form()

([ 1 0] [ 0 5*i - 6], [ 1 0] [-i - 3 1], [ 1 -2] [ 0 1])
CRT?

File: /usr/local/sage/sage-6.4/local/lib/python2.7/site-packages/sage/rings/arith.py
Signature : CRT(a, b, m=None, n=None)
Docstring :
Returns a solution to a Chinese Remainder Theorem problem.

INPUT:

* "a", "b" - two residues (elements of some ring for which
extended gcd is available), or two lists, one of residues and one
of moduli.

* "m", "n" - (default: "None") two moduli, or "None".

OUTPUT:

If "m", "n" are not "None", returns a solution x to the
simultaneous congruences xequiv a bmod m and xequiv b bmod n,
if one exists. By the Chinese Remainder Theorem, a solution to the
simultaneous congruences exists if and only if aequiv
bpmod{gcd(m,n)}. The solution x is only well-defined modulo
lcm(m,n).

If "a" and "b" are lists, returns a simultaneous solution to the
congruences xequiv a_ipmod{b_i}, if one exists.

EXAMPLES:

Using "crt" by giving it pairs of residues and moduli:

sage: crt(2, 1, 3, 5)
11
sage: crt(13, 20, 100, 301)
28013
sage: crt([2, 1], [3, 5])
11
sage: crt([13, 20], [100, 301])
28013

You can also use upper case:

sage: c = CRT(2,3, 3, 5); c
8
sage: c % 3 == 2
True
sage: c % 5 == 3
True

Note that this also works for polynomial rings:

sage: K.<a> = NumberField(x^3 - 7)
sage: R.<y> = K[]
sage: f = y^2 + 3
sage: g = y^3 - 5
sage: CRT(1,3,f,g)
-3/26*y^4 + 5/26*y^3 + 15/26*y + 53/26
sage: CRT(1,a,f,g)
(-3/52*a + 3/52)*y^4 + (5/52*a - 5/52)*y^3 + (15/52*a - 15/52)*y + 27/52*a + 25/52

You can also do this for any number of moduli:

sage: K.<a> = NumberField(x^3 - 7)
sage: R.<x> = K[]
sage: CRT([], [])
0
sage: CRT([a], [x])
a
sage: f = x^2 + 3
sage: g = x^3 - 5
sage: h = x^5 + x^2 - 9
sage: k = CRT([1, a, 3], [f, g, h]); k
(127/26988*a - 5807/386828)*x^9 + (45/8996*a - 33677/1160484)*x^8 + (2/173*a - 6/173)*x^7 + (133/6747*a - 5373/96707)*x^6 + (-6/2249*a + 18584/290121)*x^5 + (-277/8996*a + 38847/386828)*x^4 + (-135/4498*a + 42673/193414)*x^3 + (-1005/8996*a + 470245/1160484)*x^2 + (-1215/8996*a + 141165/386828)*x + 621/8996*a + 836445/386828
sage: k.mod(f)
1
sage: k.mod(g)
a
sage: k.mod(h)
3

If the moduli are not coprime, a solution may not exist:

sage: crt(4,8,8,12)
20
sage: crt(4,6,8,12)
Traceback (most recent call last):
...
ValueError: No solution to crt problem since gcd(8,12) does not divide 4-6

sage: x = polygen(QQ)
sage: crt(2,3,x-1,x+1)
-1/2*x + 5/2
sage: crt(2,x,x^2-1,x^2+1)
-1/2*x^3 + x^2 + 1/2*x + 1
sage: crt(2,x,x^2-1,x^3-1)
Traceback (most recent call last):
...
ValueError: No solution to crt problem since gcd(x^2 - 1,x^3 - 1) does not divide 2-x

sage: crt(int(2), int(3), int(7), int(11))
58


︠7e23474c-ea53-441d-bf24-69276f56dffa︠

︠10286dc4-b1b1-49fe-903c-bba095c65239︠