ichinrem([a,p],[b,q]) or ichrem([a,p],[b,q]) returns a
list [c,lcm(p,q)] of 2 integers.
The first number c is such that
∀ k ∈ ℤ, d=c+ k × lcm(p,q) |
has the properties
d=a (mod p ), d=b (mod q ) |
If p and q are coprime, a solution d always exists
and all the solutions are congruent modulo p*q.
Examples :
Solve :
|
Input :
or :
Output :
so x=-17 (mod 65)
We can also input :
Output :
Solve :
|
First input :
or :
Output :
Then input :
or :
Output :
hence x=-17 (mod 315)
Alternative input:
Output :
Remark
ichrem (orichinrem)may be used to find the coefficients of a polynomial
whose equivalence classes are known modulo several integers, for example find
ax+b modulo 315=5 × 7 × 9 under the assumptions:
| , |
|
Input :
Output :
hence a=-17 (mod 315) and b=156 (mod 315).