The Chinese Remainder Theorem states that if p1, p2, …,
pn are relatively prime, then for any integers a1, a2,
…an there is a number c such that c = a1
(mod p1 ), c=a2 (mod p2 ), …, c = an (mod pn ).
The ichinrem command will find this value of c.
ichrem is a synonym for ichinrem.
Note that any multiple of L = lcm(p1,p2,…,pn) can be
added to c and the equalities will still be true. If the pk
are relatively prime, then by the Chinese remainder theorem a solution
c will exist; what’s more, any two solutions will be congruent
modulo the product of the pks.
If all of the arguments are given as modular integers, then the result
will also be given as a modular integer c % l.
The chrem command does the same thing as ichinrem, but the input is given in a different form.
Be careful with
the order of the parameters, indeed:
chrem([a,b],[p,q])=ichrem([a,p],[b,q])=ichinrem([a,p],[b,q])
Examples.
|
⎡ ⎣ | 48,65 | ⎤ ⎦ |
⎛ ⎝ | −17 | ⎞ ⎠ | %65 |
⎡ ⎣ | 48,65 | ⎤ ⎦ |
|
⎡ ⎣ | 298,315 | ⎤ ⎦ |
⎛ ⎝ | −17 | ⎞ ⎠ | %315 |
⎡ ⎣ | 298,315 | ⎤ ⎦ |
Remark.
These three commands, ichinrem,
ichrem and chrem, may also be used to find the
coefficients of a polynomial whose equivalence classes are known
modulo several integers by using polynomials with integer coefficients
instead of integers for the ak.
For example, to find ax+b modulo 315=5 × 7 × 9 under the
assumptions
|
and
|
Example.
Input:
Output:
⎛ ⎝ | ⎛ ⎝ | −17 | ⎞ ⎠ | %315 | ⎞ ⎠ | x+156%315 |
hence a=-17 (mod 315) and b=156 (mod 315).
As before, chrem takes the same input in a different format.
Input:
Output:
⎡ ⎣ | 298 x+156,315 | ⎤ ⎦ |
(note that 298 = −17 (mod 3 )15).