Feladat: 1962. évi Matematika OKTV II. forduló 2. feladata Korcsoport: 14-15 Nehézségi fok: átlagos
Füzet: 1962/december, 195 - 197. oldal  PDF  |  MathML 
Témakör(ök): Maradékos osztás, OKTV
Hivatkozás(ok):Feladatok: 1962/szeptember: 1962. évi Matematika OKTV II. forduló 2. feladata

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

I. Ha x0, y0 megoldása (1)-nek, akkor az első tagból levonva ab-t, a másodikhoz hozzáadva

n=ax0-ab+by0+ab=a(x0-b)+b(y0+a)
is teljesül, vagyis x0-b, y0+a is megoldás, és általában, ha t tetszés szerinti egész szám, akkor
a(x0-tb)+b(y0+ta)=n
is fennáll. Ha tehát van egy x0, y0 megoldásunk, akkor választhatjuk t-t úgy, hogy x0 helyébe a lehető legkisebb nem negatív érték kerüljön: mindig választható t úgy, hogy x1=x0-tb0 és b-1 közt legyen (ha nem lett volna már x0 ilyen; utóbbi esetben t=0 választható).
Ha x0, y0 nem negatív, akkor y1=y0+ta sem negatív, mert a>0 és ha
x1≥0ésb>0,akkort≥0.

Elegendő tehát azokat az értékeket vizsgálni, amelyeket ax+by az x=0, 1, ..., b-1 értékek és tetszés szerinti nem negatív egész y-ra vesz fel. Amely n számok ezek közt nem szerepelnek, azokra nem oldható meg az (1) egyenlet.
 
II. Szorítkozzunk egyelőre arra az esetre, ha a és b relatív prímek. Az általános esetet nem lesz nehéz erre visszavezetni. Ekkor a következő táblázatban szerepelnek azok az n értékek, amelyekre (1) megoldható:
0,b,2b,3b,...,jb,...a,a+b,a+2b,a+3b,...,a+jb,...(2)2a,2a+b,2a+2b,2a+3b,...,2a+jb,...3a,3a+b,3a+2b,3a+3b,...,3a+jb,....0.00.000........(b-1)a,(b-1)a+b,(b-1)a+2b,(b-1)a+3b,...(b-1)a+jb,...
Egy-egy sorban b különbségű számtani sorozat áll, tehát bármely két szám különbsége osztható b-vel, és így két ugyanabban a sorban álló szám b-vel osztva ugyanazt a maradékot adja.
Megmutatjuk, hogy különböző sorokban álló számok viszont különböző maradékot adnak b-vel osztva. Egy sor számai ugyanazt a maradékot adják, mint pl. az első szám. Ha a k1-edik és a k2-edik sor számai ugyanazt a maradékot adnák, akkor kezdő számaik különbsége: (k1-k2)a osztható volna b-vel. Ez azonban nem lehet, ugyanis a és b relatív prímek, és ha egy szám egy szorzatnak osztója, de az egyik tényezőhöz relatív prím, akkor osztója a másik tényezőnek; (k1-k2)a tehát csak úgy lehetne b-vel osztható, ha k1-k2 osztható volna b-vel. Azonban k1 is, k2 is kisebb b-nél és egyik sem negatív, így |k1-k2|<b, tehát nem lehet b-vel osztható. Így k1a és k2a különböző maradékot ad b-vel osztva.
Mivel b sorunk van és b lehetséges maradékunk (a 0, 1, 2, ..., b-1 számok), így minden maradék előfordul, és csak egyszer. Egy adott szám tehát legfeljebb egy sorban fordulhat elő és ott is csak egyszer, mert a sor egymás utáni számai állandóan nőnek.
Megállapításaink akkor is érvényben maradnak, ha a sorokat bal felé is folytatjuk b ismételt levonásával, hiszen az egyes sorokról csak annyit használtunk ki, hogy a szomszédos számok különbsége b.
Az így kiegészített táblázatban minden egész szám szerepel. Ha ugyanis n tetszés szerinti egész szám, és a k-adik sor az, amelynek a számai ‐ köztük (k-1)a is ‐ ugyanazt a maradékot adják, mint n, akkor n-(k-1)a osztható b-vel, tehát van olyan j egész szám, amelyre n-(k-1)a=bj, n=(k-1)a+bj. Így n a k-adik sornak a (k-1)a-tól számított j-edik száma jobbra vagy balra j előjele szerint.
Mivel a sorokat balra folytatva mindegyikben elegendő lépés után csupa negatív szám áll (a-szori levonás után biztosan), így csak véges számú olyan pozitív egész n szám van, amelyikre nincs (1)-nek nem negatív egészekből álló megoldása, és ezek a táblázat kiegészítésekor, tehát az
a-b,a-2b,a-3b,...2a-b,2a-2b,2a-3b,...(3).000.000.000.000...(b-1)a-b,(b-1)a-2b,(b-1)a-3b,...
táblázatban fellépő pozitív számok.
 
III. Ha a és b nem relatív prímek, jelöljük legnagyobb közös osztójukat d-vel, és legyen a=d⋅a', b=d⋅b'; itt a' és b' relatív prímek. Ekkor (2) minden száma többszöröse d-nek, mert ax+by=d(a'x+b'y), tehát minden a d-vel nem osztható természetes szám hiányzik (2)-ből, és így megfelel a feladat követelményének.
Ha viszont n=d⋅n', akkor az ax+by=n és a'x+b'y=n' egyenletnek ugyanazok a számpárok a megoldásai. Így ha a', b'-ből kiindulva írjuk fel a (3)-nak megfelelő táblázatot, az abban fellépő pozitív számok d-szeresei felelnek meg d többszörösei közül a feladat feltételeinek. Ezek azonban éppen a (3) táblázatban fellépő pozitív számok.
Az (1) egyenletnek tehát akkor nincs nem negatív egészekből álló megoldása, ha n a (3) táblázatban fellépő valamelyik természetes szám, továbbá ha a és b legnagyobb közös osztójával nem osztható (ha e két szám nem relatív prím egymáshoz).
 

Megjegyzések. 1. Ha a és b relatív prímek egymáshoz, a feladat követelményének megfelelő legnagyobb természetes szám a (3) táblázat bal alsó sarkában álló ab-a-b szám.
2. Könnyen látható az is, hogy ha 0≤n≤ab-a-b, akkor n és ab-a-b-n közül az egyik kielégíti a feladat követelményeit, a másik nem. Valóban, egyrészt ha volnának olyan x1, y1, x2, y2 nem negatív egész számok, amelyekre
ax1+by1=nésax2+by2=ab-a-b-n,
akkor
a(x1+x2)+b(y1+y2)=ab-a-b
volna és x1+x2, y1+y2 nem negatív, holott éppen láttuk, hogy ennek az egyenletnek nincs nem negatív egészekből álló megoldása. Így legfeljebb az egyik egyenletnek van nem negatív megoldása.
Másrészt láttuk, hogy az (1) egyenletnek mindig van egész megoldása, és van olyan x1, y1, megoldása is, amelyben 0≤x≤b-1. Ha most az egyenletnek nincs nem negatív egészekből álló megoldása, akkor y1<0. Ekkor
ab-a-b-n=a(b-1-x1)+b(-1-y1),
és itt x2=b-1-x1≥0, y2=-1-y1≥0 egy nem negatív egészekből álló megoldás.
3. A 0, 1, 2, ..., ab-a-b számoknak ezek szerint pontosan a fele elégíti ki a feladat követelményeit, tehát
ab-a-b+12=(a-1)(b-1)2
a megfelelő számok száma. (Ez mindig egész, mert ha a és b relatív prímek, akkor legalább az egyik páratlan.)