### 1.6.22 Κινεζικά υπόλοιπα : ichinrem, ichrem

ichinrem([a,p],[b,q]) ή ichrem([a,p],[b,q]) επιστρέφει μια λίστα [c,lcm(p,q)] με 2 ακεραίους.
Ο πρώτος αριθμός c είναι τέτοιος ώστε

∀k∈ ℤ,d=c+k×  lcm(p,q)

έχει τις ιδιότητες

d=a(mod p),d=b(mod q)

Αν p και q είναι πρώτοι μεταξύ τους, μια λύση d υπάρχει πάντα και όλες οι λύσεις είναι ισοδύναμες modulo p*q.
Παραδείγματα :
Λύστε :

⎧
⎨
⎩

x | = | 3 (mod 5)
x | = | 9 (mod 13)

Είσοδος :

ichinrem([3,5],[9,13])

ή είσοδος :

ichrem([3,5],[9,13])

Έξοδος :

[-17,65]

άρα x=-17 (mod 65)
μπορούμε επίσης για είσοδο να έχουμε :

ichrem(3%5,9%13)

Έξοδος :

-17%65

Λύστε :

⎧
⎪
⎨
⎪
⎩

x | = | 3 (mod 5)
x | = | 4 (mod 7)
x | = | 1 (mod 9)

Αρχική είσοδος :

tmp:=ichinrem([3,5],[4,7])

ή είσοδος :

tmp:=ichrem([3,5],[4,7])

έξοδος :

[-17,35]

επόμενη είσοδος :

ichinrem([1,9],tmp)

ή είσοδος :

ichrem([1,9],tmp)

Έξοδος :

[-17,315]

άρα x=-17 (mod 315)
Εναλλακτική λύση :

ichinrem([3%5,4%7,1%9])

Έξοδος :

-17%315

Σχόλιο
ichrem (ή ichinrem) μπορούν να χρησιμοποιηθούν για να βρεθούν οι συντελεστές πολυωνύμου οι οποίοι είναι γνωστοί modulo αρκετών ακεραίων, για παράδειγμα να βρείτε ax+b modulo 315=5 × 7 × 9 σύμφωνα με τις παραδοχές:

⎧
⎪
⎨
⎪
⎩

a= | 3 (mod 5)
a= | 4 (mod 7)
a= | 1 (mod 9)

,

⎧
⎪
⎨
⎪
⎩

b= | 1 (mod 5)
b= | 2 (mod 7)
b= | 3 (mod 9)

Είσοδος :

ichrem((3x+1)%5,(4x+2)%7,(x+3)%9)

Έξοδος :

(-17%315× x+156%315

άρα a=-17 (mod 315) και b=156 (mod 315).