Den kinesiske restsætning

Du har lavet en bøf i afskriften af opgaven, så jeg vil kun udstikke de generelle linier.

Lad os sige der er tre oplysninger givet ved dividenderne 3, 5 og 7, sådan som sidste del af dit citat refererer. Ideen er nu, parvist at danne alle produkter mellem disse tre tal, da så netop eet af de tre tal ikke er divisor. Vi kan derfor benytte hvert af disse par, under passende justering ved multiplikation af en hel faktor, til at opnå resten 1 ved division med det tal, der ikke er divisor (division med ethvert af de to øvrige giver naturligvis ingen rest). Lad os kalde disse tal, som hvert giver resten 1 ved division med det tal, der ikke er divisor, for grundtal.

I det konkrete tilfælde dannes produkterne 3*5 = 15, 3*7 = 21, 5*7 = 35. Grundtallene findes som

15 == 1 (mod 7)
21 == 1 (mod 5)
70 == 1 (mod 3)

hvor vi anvender 70=2*35 fremfor 5*7 da 35 == 2 (mod 3).

Man bemærker nu, at da et grundtal giver resten 1 ved division med tallet, der ikke er divisor, vil grundtallet multipliceret med den rest, der skal fremkomme ved division af den søgte løsning med dette tal, netop give den korrekte rest. Tallet der fremkommer som produktsummen af grundtallene og resterne er derfor en løsning.

I det konkrete tilfælde skal resterne alle være een, så tallet

1*70 + 1*21 + 1*15 = 106

er en løsning. For 1*70 giver rest 1*1 ved division med 3 medens 3 er divisor i både 21 og 15. Tilsvarende for 21 ved division med 5 og 15 ved division med 7.

Tallet 106 er imidlertid ikke den eneste løsning. For løsningen kan kun være bestemt modulo 3*5*7=105 eftersom alle tre dividender jo er divisorer i dette tal.

Tak skal du have! Det har hjulpet på forståelsen, men såvidt jeg kan se har du anvendt den moderne formulering af den kinesiske restsætning. Det jeg imidlertid var interesseret i var, at udføre samme regnestykke vha. metoden givet af Sun Zi vist i #0.

Nej, jeg benytter blot terminolgien fra modulusregningen, men teknikken er Sung Chings.

Så må jeg have misforstået det.

Hvordan gør man det så efter den moderne formulering?

[Lad m1, m2,...mn være parvis indbyrdes primiske positive heltal. Systemet
x == a1 (mod m1), x == a2 (mod m2),..., x == an (mod mn)
har en entydig løsning x modulo m = m1m2...mn.
Entydig løsning modulo m betyder igen, at der er en løsning x med 0 = x < m og at alle andre løsninger er kongruente modulo m til denne løsning.]

Den kinesiske restklassesætning garanterer eksistensen af en entydig løsning modulo m_1*...m_n, men anviser ikke en metode til at finde den. Et konstruktivt bevis for sætningen gør imidlertid og det er Sun Chings metode op ad dage, sålænge man indskrænker det til ringen af heltal. Almindeliggørelsen til vilkårlige ringe og moduler er selvsagt anderledes.