Page 202 - vol1

−
prímek és mind osztják az x x− különbséget, ezért m m ..m x x , vagyis
|
0 1 2 k 0


létezik t  , amelyre igaz, hogy x x− 0 = mm 2 ..m t  = x + mm 2 ..m t .
x
1
k
1
0
k
Ezzel a tételt bizonyítottuk.
=
Megjegyzés. Észrevehető, hogy a c = c = ... c = esetén a kínai maradéktétel
0
2
1
k
éppen a 3. segédtétel következményére redukálódik, de ezt éppen a
maradéktétel bizonyításakor használtuk. Ezért kellett ezt másképpen
bizonyítanunk, és így a kínai maradéktétel a c = c = ... c = esetben is igaz.
=
0
1 2 k
2. feladat
Oldjuk meg az 1. példát a kínai maradéktétel segítségével, és próbáljunk
arra is választ adni, hogy hányan lehettek a gyermekek!
Megoldás
Jelölje x a gyermekek számát. A feladat szövege alapján olyan pozitív x-et
keresünk, amelyre egy időben igaz, hogy
2| x − 1 és 3| x − .
2
A kínai maradéktétel bizonyítási algoritmusát követve rendre felírható:
1
2
3
2
1) m = és m = relatív prím, és c = , c = .
1 2 1 2
m m m m
2) M = 1 1 2 = 3 és M = 2 1 2 = 2.
m m
1 2
3) Képezzük az M y m z c− = diofantoszi egyenleteket:
i i i
3y − 2z = 1, illetve 2y − 3z = 2 .
Észrevehető, hogy egy-egy partikuláris megoldásuk:
y = 3 és z = , illetve y = és z = .
4
4
2
2
2
1
1
4) A feladat egy partikuláris megoldása tehát:

x = M y + M y = 3 3 2 4 17 .
=
+

2 2
0
1 1
5) A feladat általános megoldása (lásd a (**) képletet):
x = x + mm t = 17 6t = 6t + 12 5 6(t + 2) 5: 6n+ , ahol ezúttal n * .
+
=
=
+
+
5
0 1 2
Tehát a csapatban 11, 17, 23,… gyermek lehetett, akiket hatosával állítva
sorba, a sor végén 5 gyermek marad.

202