Feladat: 1980. évi Kürschák matematikaverseny 2. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Beleznay Ferenc ,  Bohus Géza ,  Gellér János ,  Horváth István ,  Király Zoltán ,  Szabó Endre ,  Szabó László ,  Tardos Gábor ,  Umann Gábor 
Füzet: 1981/február, 55 - 57. oldal  PDF file
Témakör(ök): Maradékos osztás, Természetes számok, Egyenletek, Oszthatóság, Prímszámok, Prímtényezős felbontás, Legnagyobb közös osztó, Egyenlőtlenségek, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 1981/február: 1980. évi Kürschák matematikaverseny 2. feladata

2. feladat. Legyen n>1 páratlan egész szám. Bizonyítsuk be, hogy akkor és csak akkor léteznek olyan x, y természetes számok, melyekre
4n=1x+1y,
ha n-nek van 4k-1 alakú prímosztója.

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.

2. feladat. Legyen n>1 páratlan egész szám. Bizonyítsuk be, hogy akkor és csak akkor léteznek olyan x, y természetes számok, melyekre

4n=1x+1y,(1)
ha n-nek van 4k-1 alakú prímosztója.
 

I. megoldás. Tegyük fel, hogy van az egyenletnek pozitív egész x, y megoldása. Legyen a két szám legnagyobb közös osztója d, azaz
x=dx1,y=dy1,
ahol x1 és y1 pozitív egész és nincs 1-nél nagyobb közös osztójuk, más szóval relatív prímek. Ezt beírva az egyenletbe és a törteket eltávolítva, azt kapjuk, hogy
4dx1y1=n(x1+y1).(2)

Itt n páratlan volta miatt a jobb oldal csak úgy lehet 4-gyel osztható, ha x1+y1 osztható 4-gyel. Ekkor x1 és y1 vagy mindkettő páros vagy mindkettő páratlan. Mivel ezen kívül relatív prímek is, csak a második eset következhet be. Minthogy pedig az összegük osztható 4-gyel, ez csak úgy lehet, ha az egyik 4k+1 alakú, a másik 4k-1 alakú.
A (2) összefüggés szerint x1 osztója az n(x1+y1) szorzatnak. x1+y1-hez azonban relatív prím, hiszen ha volna 1-nél nagyobb közös osztójuk, az osztója volna (x1+y1)-x1=y1-nek is, azonban x1 és y1 relatív prímek. Ismeretes, hogy ebben az esetben x1 csak úgy lehet osztója a szorzatnak, ha a másik tényezőjének, n-nek is osztója. Ugyanígy következik, hogy y1 is osztója n-nek.
Az x1-re és y1-re tett megállapításaink alapján következik, hogy ha megoldható az egyenlet, akkor van n-nek 4k-1 alakú osztója. Ekkor azonban van ilyen alakú prímosztója is. Ha ugyanis egy 4k-1 alakú számot akárhogy felbontunk tényezőkre, akkor azok közt van 4k-1 alakú. Valóban, számunk páratlan, így a felbontás tényezői is páratlanok, akkor pedig vagy 4k+1 vagy 4k-1 alakúak. Két előbbi alakú szám szorzata is ilyen alakú:
(4k1+1)(4k2+1)=4(4k1k2+k1+k2)+1,
és ez az alak újabb ilyen tényezőkkel szorozva sem változik meg. Elő kell tehát fordulnia 4k-1 alakúnak is. Ez igaz akkor is, ha prímtényezőkre bontottuk a számot. Így n 4k-1 alakú osztójának van 4k-1 alakú prímosztója, de ez osztója n-nek is.
Tegyük most fel, hogy p=4k-1 n-nek egy prímosztója: n=pm. Ekkor
4n=4kkpm=p+1kpm=1km+1kpm,
tehát x=km, y=kpm megoldása az egyenletnek. Ezzel a feladat állítását bebizonyítottuk.
 

Megjegyzések. 1. Felhasználtuk azt a tételt, hogy ha egy egész szám osztója egy szorzatnak, de annak egyik tényezőjéhez relatív prím, akkor osztója a másik tényezőnek. Ez következik a számelmélet alaptételéből, ami szerint minden 1-nél nagyobb természetes szám felbontható véges sok (pozitív) prímszám szorzatára és ez a felbontás a tényezők sorrendjétől eltekintve egyértelmű. Fordítva, az alaptétel is következik a fent kimondott tételből, az pedig bizonyítható az alaptétel felhasználása nélkül.
2. A bizonyítás befejező részében nem használtuk ki, hogy p prím, tehát képleteink n minden 4k-1 alakú osztójához megadnak egy megoldást.
3. A megoldás első részének gondolatmenetét folytatva n=n'x1 és x1, y1 relatív prím volta miatt a jobb oldali szorzat csak úgy lehet y1-gyel osztható, ha n' osztható vele: n'=my1. Ezeket beírva (2)-be m(x1+y1)=4d adódik.
Láttuk továbbá, hogy x1+y1 osztható 4-gyel, így x1+y1=4e jelöléssel
(31)n=mx1(4e-x1),(32)x=emx1,(33)y=em(4e-x1).
Ebből is világos, hogy x1 és 4e-x1=y1 közül az egyik 4k+1, a másik 4k-1 alakú.
Mivel x és y szerepe szimmetrikus, feltehetjük, hogy x1 a 4k+1 alakú. Tudjuk már, hogy x1 és 4e-x1 relatív prímek.
Azt kaptuk tehát, hogy az (1) egyenlet összes megoldását megkapjuk, ha vesszük n-nek (31) alakú felbontásait, amelyekben x1 és 4e-x1 relatív prímek, és képezzük hozzájuk a (32), (33) képletek szerinti értékeket, továbbá a két szám felcserélésével keletkező számpárt. x és y mindig különböző, mert x1 és 4e-x1 nem lehet egyenlő.
n-nek minden t=4j-1 alakú osztójához van legalább egy (31) alakú felbontása. Válasszuk ugyanis t-t 4e-x1-nek, x1-nek pedig az n/t bármelyik 4k+1 alakú és t-hez relatív prím osztóját (az 1 mindig ilyen). Ekkor e=(t+x1)/4 egész és m=n/(tx1). (Megoldást kapunk akkor is, ha t és x1 nem relatív prím, csak így egyes megoldásokat többször is megkaphatunk.)
 

II. megoldás. A feladatnak csak azt a részét bizonyítjuk, hogy ha az (1) egyenlet megoldható, akkor van n-nek 4k-1 alakú prímosztója. A törteket eltávolítva és 0-ra redukálva a
4xy-n(x+y)=0
összefüggést kapjuk. Szorozzunk 4-gyel és adjunk mindkét oldalhoz n2-et, ekkor a bal oldal szorzattá alakítható.
(4x-n)(4y-n)=n2.

Itt a bal oldali tényezők pozitívok, mert (1)-ből 1/x is, 1/y is kisebb 4/n-nél, s így
4x>n,4y>n.

Ha n-nek nincs 4k-1 alakú prímosztója, akkor nem állhat fenn az egyenlet, ekkor ugyanis 4x-n is, 4y-n is 4k-1 alakú, tehát mint az előző megoldásban láttuk, van 4k-1 alakú prímosztójuk. Ekkor azonban a bal oldalt prímtényezőkre bontva, azok közt lennének 4k-1 alakú prímek, a jobb oldalon viszont beírva n prímtényezős felbontását, csupa 4k+1 alakú prímszám szorzata állna, ez pedig ellentmond annak, hogy minden 1-nél nagyobb természetes szám a tényezők sorrendjétől eltekintve egyértelműen írható fel prímtényezők szorzataként.
 

Megjegyzés. Lényeges volt, hogy a természetes számok körére szorítkozunk, s ezért meg kellett állapítani, hogy a szorzat tényezői pozitívok. Ezt a legtöbb versenyző, aki ezt az utat választotta, elmulasztotta. Pedig írhatjuk az egyenlőséget
(n-4x)(n-4y)=n2
alakban is, és ekkor semmi probléma nem látszik adódni abból, ha n minden prímosztója 4k+1 alakú. Valóban van is megoldása az (1) egyenletnek, ha csak azt kívánjuk, hogy x és y egész legyen és n=4k+1:
4n=4kkn=n-1kn=1k-1kn=1k+1-kn.