Page 198 - vol1

23. A kínai maradéktétel és alkalmazása

A kínai maradéktétel legalább 2000 éves, erről számos számelméleti
könyvben olvashatunk.

Az utóbbi időben a tételt a nagy számokkal végzett számításokra
kidolgozott algoritmusokban alkalmazzák eredményesen, de számos elemi
aritmetikai feladat épül a szóban forgó tételre. Íme erre egy egyszerű példa:

1. feladat
Ha néhány gyereket párosával állítunk sorba, akkor egy gyerek marad a sor
végén, ha hármasával, akkor pedig kettő. Hányan maradnak a sor végén, ha
hatosával állítjuk őket sorba?
1. megoldás
Legyen M a gyerekek száma. A feltételek alapján egy időben igaz, hogy

M = 2 x + 1 és M = 3 y + , ahol x y * . Ezek alapján 3M = 6x+ 3 és
,

2
2M = 6y + 4 , ahonnan kivonással kapjuk, hogy M = 6(x − y ) 1 = 6(x − y − 1) + ,
−
5
ami azt jelenti: ha hatosával állítjuk sorba a gyermekeket (amennyiben több
mint 6 gyerek van), akkor a sor végén 5 gyermek marad.
2. megoldás
Az előző megoldás eredményeit használva tulajdonképpen a
2x + = 3y + 2   2x − 3y = diofantoszi egyenletet kell megoldanunk a
1
1
természetes számok halmazán.
Könnyen belátható, hogy x = és y = 1 egy partikuláris megoldás. Ezért
2
0 0
a 2x − 3y = 1 egyenlet egész megoldásai
+


x b n x = − 3n+ és y = − a n y = − 2n+ , ahol n .
=
+
2
1
0
0
Bevezetve a − n = m jelölést, x = 3m+ 2 és y = 2m + 1 adódik, és jelen
esetben m kell hogy legyen.
+
=
=
=
+
=
5
Tehát M = 2x + 1 3y + 2 2(3m+ 2) 1 3(2m+ 1) 2 6m+ , vagyis
válaszunk ugyanaz, mint az előző megoldás esetén.
Könnyen belátható, hogy ha az 1. feladat esetén kettőnél több feltétel
(adat) lenne, akkor sem az 1. megoldás, sem a 2. megoldás nem lenne
értékesíthető.

198