Feladat: N.70 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Gyarmati Katalin ,  Izsák Ferenc ,  Pap Gyula ,  Póczos Barnabás ,  Tóth Gábor Zsolt ,  Valkó Benedek 
Füzet: 1996/február, 103. oldal  PDF file
Témakör(ök): Euler-Fermat-tételek, Nehéz feladat
Hivatkozás(ok):Feladatok: 1995/május: N.70

Legyenek a, b, c, d különböző pozitív egészek. Bizonyítsuk be, hogy az acn+bdn alakú pozitív egészeknek összesen végtelen sok prímosztója van.

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 feladatot először abban a speciális esetben oldjuk meg, amikor c és d relatív prímek. Az a, b, c, d számok különbözősége helyett csupán annyit kötünk ki, hogy nem lehet c és d értéke is 1.
Tegyük fel, hogy az acn+bdn alakú pozitív egészeknek összesen csak véges sok prímosztója van. Legyenek ezek p1, p2, ..., pm. Válasszunk mindegyik pi-hez egy olyan αi pozitív egészet, hogy a, b és a+b egyike se legyen osztható pαi-vel.
Azt állítjuk, hogy ha n elég nagy és osztható φ(piαi)-vel, akkor acn+bdn nem osztható piαi-vel. (φ az Euler-féle függvény: φ(n) az n-nél nem nagyobb, n-hez relatív prím pozitív egészek száma.) A lehetséges eseteket két részre osztjuk.
I. eset: ha sem c, sem d nem osztható pi-vel. Legyen n=kφ(piαi). Az Euler‐Fermat tétel szerint

cn=(ck)φ(piαi)1modpiαiésdn=(dk)φ(piαi)1modpiαi,
ezért
acn+bdna+bmodpiαi.
Az αi definíciója szerint a+b nem osztható piαi-nel.
II. eset: ha c vagy d osztható pi-vel. Az állítás szimmetriája miatt feltehetjük, hogy c osztható pi-vel. Mivel c és d relatív prímek, ebben az esetben d nem osztható pi-vel. Ha nαi, akkor cn osztható piαi-nel, és ‐ ismét felhasználva az Euler‐Fermat tételt ‐
acn+bdna0+b1=bmodpiαi.
Mivel b nem osztható piαi-nel, kész vagyunk.
Legyen most P=φ(p1α1)φ(p2α2)...φ(pmαm). Ha n elég nagy és osztható P-vel, akkor acn+bdn nem osztható piαi-nel semmilyen i-re sem, tehát prímtényezős felbontásban a pi kitevője kisebb, mint αi. Mivel az indirekt feltevés szerint más prímosztója nincs, ebből következik, hogy
acn+bdnp1α1-1p2α2-1...pmαm-1.
Ez azonban ellentmondás, mert c és d közül valamelyik legalább 2, így az acn+bdn sorozat szigorúan monoton nő, és végtelenhez tart.
Hátravan még az általános eset vizsgálata, amikor c és d különböző, nem feltétlenül relatív prím számok. Legyen c és d legnagyobb közös osztója q; c=c1q, d=d1q, ahol c1 és d1 relatív prímek. Ezekkel a jelölésekkel
acn+bdn=qn(ac1n+bd1n).
Mivel c1 és d1 relatív prímek, a második tényező lehetséges értékeinek, mint láttuk, összesen végtelen sok prímosztója van.
 Gyarmati Katalin (Fazekas M. Főv. Gyak. Gimn., III. o.t.)