7.1.20  Chinese remainders

The ichinrem or ichrem command finds this value of c.

• ichinrem takes one or more arguments: Each argument is a pair of integers a_k and p_k either as a list [a_k,p_k] or as a modular integer a_k% p_k.
• ichinrem([a₁,p₁],[a₂,p₂],…,[a_n,p_n]) if possible returns a list [c,L], where L= lcm(p₁,p₂,…,p_n) and c satisfies c≡ a_k (mod p_k ) for k=1,…,n.

Note that any multiple of L=lcm(p₁,p₂,…,p_n) can be added to c and the equalities will still be true. If the p_k are relatively prime, then a solution c exists by Theorem 1; what’s more, any two solutions will be congruent modulo the product of the p_ks.

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.

• chrem takes two arguments: [a₁,…,a_n] and [p₁,…,p_n], lists of integers of the same size.
• chrem([a₁,…,a_n],[p₁,…,p_n]) returns [c,L], as for ichinrem.

Be careful with the order of the parameters. Indeed, chrem([a,b],[p,q]), ichrem([a,p],[b,q]) and ichinrem([a,p],[b,q]) all produce the same output.

Examples

Solve:

or:

so x≡ 48 (mod 65 ).

You can also input:

Note that 48≡ −17 (mod 65 ).

Recalling that chrem takes its arguments in a different form, you can also enter:

Solve:

hence x≡ 298 (mod 315 ).

Alternative input:

Note that 298≡ −17 (mod 315 ).

Again, with the arguments in a different form, you can also enter:

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 a_k.

For example, to find ax+b modulo 315=5 · 7 · 9 under the assumptions

and

Example

hence a=-17 (mod 315) and b=156 (mod 315).

As before, chrem takes the same input in a different format.

Note that 298≡ −17 (mod 315 ).