Page 201 - vol1

A tételre létezik induktív bizonyítás, de számunkra értékesebb egy konstruktív
bizonyítás, mert így az egyes feladatok megoldása során algoritmikusan alkal-
mazható. A következő, konstruktív bizonyítást lépésekre bontva mutatjuk be.

m m ..m
1) Legyen M = 1 2 k minden 1, 2, ...,i  k esetén.
i
m i
2) Nyilvánvaló, hogy (M m ) (mm ..m m ..m ,m ) 1, hiszen m ,m ,..,m
=
=
,
i i 1 2 i − 1 i + 1 k i 1 2 k
|
páronként relatív prím. Ugyanakkor belátható, hogy m M minden i  és
j
j
i

, i j  1, 2, ..., k esetén.
=
3) Mivel (M m ) 1, ezért az előző paragrafus 1. tétele alapján az
,
i i

M y m z = egyenletnek minden i  1,2,..,k esetén van egész megoldása.

−

c
i
i
i
Legyen rendre ( , )y z az előző egyenletek egy-egy partikuláris megoldása
i
i


minden i  1,2,..,k esetén. Tehát M y − i i m z = i i c minden i  1,2,...,k
i
értékre. (1)
=
4) Képezzük az x 0 : M y + M y + ... M y összeget. (2)
+
k
k
2 2
1 1

(a) Igazoljuk, hogy minden i  1,2,..,k esetén m x − .
|
c
0
i
i
(2) k
(1)
i i 
i 
=
Valóban, x − c = M y + (M y − c i ) m z + k M y i m , hiszen m M
|
j
i
j
i
i
i
i
0
j
j = 1 j = 1


i j j i

minden i  , j ,i j  1,2,..,k esetén.
Tehát x valóban megoldása a (*) oszthatóságoknak.
0
(b) Igazoljuk, hogy az x = x + mm ..m t alakú számok megoldásai a (*)

0 1 2 k
oszthatóságoknak. Ez igaz, hiszen

−
−
+
x c = x + mm ..m t c = (x − c ) mm ..m t m minden 1, 2,..,i  k

i 0 1 2 k i 0 i 1 2 k i
esetén, hiszen x − c m is igaz.
i
0
i
Most azt igazoljuk, ha az x a (*) oszthatóságnak megoldása, akkor

−
x = x + m m 2 ...m t alakú. Valóban, hiszen m x c és m x − c  x c =  i m
−
|
|
i
i
i
0
i
0
i
1
k
i
és x − c =  m minden 1,2,..,i  k esetén ( ,   * ) .
0 i i i i i

|
Tehát x x− 0 (  = i  − i ) m , vagyis m x x− minden 1, 2,..,i  k esetén. A
i
i
0
3. Segédtétel következménye értelmében, mivel m ,m ,..,m páronként relatív
1 2 k

201