Feladat: F.3136 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Bérczi Gergely ,  Devecsery András ,  Felföldi Zsolt ,  Gyenes Zoltán ,  Hangya Balázs ,  Juhász András ,  Katona Zsolt ,  Méder Áron ,  Nyul Gábor ,  Patakfalvi Zsolt ,  Pogány Ádám ,  Rudolf Gábor ,  Terék Zsolt ,  Terpai Tamás ,  Tóth Ádám ,  Várkonyi Péter ,  Végh László ,  Zábrádi Gergely 
Füzet: 1997/március, 165. oldal  PDF file
Témakör(ök): Legnagyobb közös osztó, Teljes indukció módszere, Maradékos osztás, Oszthatósági feladatok, Prímszámok, Feladat
Hivatkozás(ok):Feladatok: 1996/október: F.3136

Az a1, a2, ..., an pozitív egészek legnagyobb közös osztója 1. Igazoljuk, hogy véges sok kivétellel minden pozitív egész előáll a1x1+...+anxn alakban, ahol x1, ..., xn nemnegatív egészek.

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.

A feladat állítását n-re vonatkozó teljes indukcióval igazoljuk.
n=2 esetben p=a1, és q=a2 relatív prímek. Ekkor q többszörösei teljes maradékrendszert alkotnak p szerint, vagyis tetszőleges 0k<p számhoz létezik olyan 0j<p, amelyre:

jqk(modp).
Így minden pq-nál nagyobb z számot elő lehet állítani a kívánt alakban: legyen k a z maradéka p-vel osztva. A k-hoz találunk p-nél kisebb j-t úgy, hogy
jqk(modp).
Ekkor z-jq osztható p-vel, legyen a hányados l, így z=jq+lp, ahol j0 és l0. Ezzel n=2-re igazoltuk az állítást.
Tegyük fel, hogy valamilyen m-re, nm esetén az állítás igaz. Megmutatjuk, hogy ekkor n=m+1 esetén is igaz.
Legyen az a1, a2, ..., am számok legnagyobb közös osztója d. Az indukciós feltétel szerint az a1d, a2d, ..., amd számokkal véges sok kivétellel minden pozitív egesz szám felírható a kérdéses alakban. Így létezik olyan u, hogy: (u,am+1)=1 és a1dv1+a2dv2+...+amdvm=u, ahol v1, v2, ..., vm nemnegatív egész.
Mivel d és am+1 relatív prímek (különben az a1, a2, a3, ..., am+1 számoknak lenne közös osztója), ud és am+1 is relatív prímek. Az előbb beláttuk, hogy a feladat állítása n=2 esetén igaz, azaz véges sok kivétellel minden pozitív egész szám felírható
x1du+x2am+1
alakban, azaz x1v1a1+x1v2a2+x1v3a3+...+x1vmam+x2am+1 alakban, ahol x1v1, x1v2, x1v3, ..., x1vm, x2 nemnegatív egészek.
Ezzel a feladat állítását igazoltuk.
 Terék Zsolt (Fazekas M. Főv. Gyak. Gimn., III. o.t.)