Page 208 - vol1

8. feladat
Egy egész szám háromszorosát 4-gyel osztva a maradék 1, a kétszeresét 5-
tel osztva a maradék 3, az ötszörösét 7-tel osztva a maradék 2, a hétszeresét 9-
cel osztva a maradék 8. Melyik ez a szám?

Megoldás
Olyan x számot keresünk, amelyre egy időben teljesül:
4 | 3x − 1; 5 | 2x − 3; 7 | 5x − 2 és 9 | 7x − .
8
A kínai maradéktétel lépéseit követjük az előbbi tétel módosításai szerint:
7
1) a = 3; a = 2; a = 5; a = ;
1 2 3 4
c = 1; c = 3; c = 2; c = ;
8
4
3
2
1
m = 4; m = 5; m = 7; m = ;
9
4
2
3
1
=
=
=
=
=
=
,
( ,m 1 ) ( ,m 2 ) ( ,m 3 ) ( ,m 2 ) (m m 3 ) (m m 1 ) 1 teljesül.
a
a
m
,
a
1
2
3
1
3
2
2)
m m m m m m m m m m m m m m m m
M = 1 2 3 4 = 315;M = 1 2 3 4 = 252;M = 1 2 3 4 = 180;M = 1 2 3 4 = 140.
1
4 2 5 3 7 4 9
3) A 2. tétel alapján képezzük az a M y m z c− = egyenleteket:
i i i i
945y − 4z = 1; 504y − 5z = 3; 900y − 7z = 2 és 980y − 9z = .
8
Ezeknek egy-egy partikuláris megoldása rendre:
y = 1 és z = 236; y = és z = 201; y = és z = 514 ; y = 1 és
2
4
1 1 2 2 3 3 4
z = 108.
4
4) A feladat egy partikuláris megoldása:
+
+
=
x = M y + M y + M y + M y = 315 504 720 140 1697.
+
4 4
1 1
2 2
0
3 3
5) Ugyancsak a 2. tétel alapján a feladat általános megoldása:
+
+
x = x + mm m m t = 1697 1260t = 1260(t + 1) 419 , vagyis x = 1260n+ 419, ahol
1
0
2
4
3
n .
Befejezésül megjegyezzük, hogy a jelen paragrafusban tárgyalt
problémák az úgynevezett lineáris kongruenciák témakörébe tartoznak,
ellenben ebben a paragrafusban csak az elemi megközelítéséről írtunk, csupán
elemi eszközök segítségével.

208