Hogyan oldjam meg az alábbi feladatot?

Magyarán az a kérdés, hogy minden egész szám felírható-e 29a+22b alakban.

Van az a számelméleti tétel (ha jól tudom, az a neve, hogy kínai maradéktétel), hogy az

A*x + B*y = C egyenletnek mindig van (x;y) egészeket tartalmazó számpárja, hogyha A és B relatív prímek. Ezek alapján a

29a + 22b = n egyenletnek (ahol n tetszőleges egész) mindig lesz (a;b) egészeket tartalmazó számpárja, mivel a 22 és a 29 relatív prímek. Ezzel bizonyítottuk, hogy az állítás igaz.

Biztosan van szép megoldása, és nem kell egy ekkora tételt előszedni hozzá, de hirtelen nincs ötletem.

Másik megoldás; nézzük meg, hogy az 1-et ki tudjuk-e rakni;

29a+22b = 1, rendezzük így az egyenletet:

a = (1-22b)/29

Kis próbálgatás után kijön, hogy ha a b értéke 4, akkor az a értéke (-3) (nyilván próbálgatás nélkül is meg lehet határozni, vannak rá eszközök). Tehát az 1 kirakható, vagyis

29*(-3) + 22*4 = -87+88 = 1, tehát

29*(-3) + 22*(4) = 1.

Ez azért jó nekünk, mert az 1-ből szorzással bármilyen szám megkapható. Például nézzük meg, hogy az 5-öt hogyan tudjuk megkapni; szorozzunk 5-tel:

5*(29*(-3) + 22*(4)) = 5, bontsuk ki a külső zárójelet:

5*29*(-3) + 5*22*(4) = 5

A szorzatban nyugodt szívvel megtehetjük, hogy a zárójelben lévő számot szorozzuk meg az 5-tel:

29*(-15) + 22*(20) = 5

Ez az eredeti feladat szempontjából azért érdekes, mert ebből látjuk, hogy ha a=-15 és b=20, akkor a kifejezés értéke 5.

Általánosan azt mondhatjuk, hogy ha n egész szám, akkor szorozhatunk n-nel;

n*(29*(-3) + 22*(4)) = n, majd a fentiek szerint elvégezve a beszorzásokat:

29*(-3n) + 22*(4n) = n

Tehát beláttuk, hogy bármelyik egész szám előállítható a kifejezésből. És nemcsak azt láttuk be, hogy az állítás igaz, hanem konkrét képzési szabályt is tudtunk adni ahhoz, hogy bármelyik szám megalkotható legyen; ha a=-3n és b=4n, akkor a kifejezés értéke n lesz, és mivel n helyére bármelyik egész szám beírható gond nélkül, ezért bármelyik egész szám megalkotható ezzel a képzési szabállyal.