Page 199 - vol1

Ezért általánosabb megoldási módszerekre van szükségünk. Erre szolgál az
ún. kínai maradéktétel. Mielőtt azonban bemutatnánk a kínai maradéktételnek
egy elemi változatát, szükségünk van néhány számelméleti alapfogalomra és
eredményre.

Értelmezés. Az a és b természetes számok legkisebb közös többszörösének
=
b
a
nevezzük azt az M : [ , ] természetes számot, amelynek a következő
tulajdonságai vannak:
1) a M és |b M ;
|
'
2) bármely más olyan M természetes szám esetén, amelyre a M és
'
|
'
|
'
b | M is teljesül, következik, hogy M M .
1. segédtétel. Bármely x természetes szám esetén, ha az m m  * számokra
,
1
2
igaz, hogy m x és m x, akkor M = [ ,m ]| x .
|
|
m
1 2 1 2
Bizonyítás
Feltételezzük az ellenkezőjét: M  . Ekkor x = q M + , ahol , r  és

| x
r
q


0 r M , tehát r  0.
Mivel m x , ezért m q M | + r , de m M , így m r . (1)
|
|
|
1 1 1 1
Mivel m x, ezért m q M r 2 | + , de m M , így m r . (2)
|
|
|
2
2
2
|
|
Az előző értelmezés 2) feltétele, valamint az m r és m r alapján kell
1 2
hogy teljesüljön M r , ami lehetetlen, hiszen 0 r M  . Tehát a feltétel hamis,
|
ezért r = 0 kell hogy legyen, így M x .
|
=
2. segédtétel. Az m1, m2, ..., mk szám [ ,m m 2 ,..,m k ] M legkisebb közös
1
többszörösét a következőképpen határozzuk meg:
=
=
=
=
m
[ ,m ]: M ; [M m ]: M ; [M m ]: M ,...,[M ,m ]: M , ahol Mk
,
,
1 2 2 2 3 3 3 4 4 k− 1 k k
éppen M-mel egyenlő.
Bizonyítás
Az m és m számok közös többszörösei megegyeznek M többszöröseivel.
1 2 2
Így az m és m többszörösei, valamint az m többszörösei közül kiválasztjuk a
3
2
1
legkisebb közös többszöröst, ami annyit jelent, mint az M többszörösei és az
2
m többszörösei közül kiválasztani a legkisebb közös többszöröst, az M -at, és
3 3
így tovább, eljárásunk véges számú lépés után éppen az M-et adja meg.

199