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.
See also: * "CRT_list()"
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