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. megoldás. Felhasználjuk a következő ismert tételt (lásd az 1. megjegyzést): ha pozitív egész, és egész számok, amelyekre teljesül, hogy és , akkor is teljesül ( a és legnagyobb közös osztóját jelöli). Legyen az legkisebb prímosztója (, tehát van neki). Megmutatjuk, hogy ; ebből az állítás azonnal következik. A feltétel szerint ; ebből csak annyit fogunk felhasználni, hogy . Mivel nem osztója a -nak (ha osztója lenne, akkor nem lehetne osztója), felírhatjuk a Fermat-tételt: . Mivel, mint láttuk, is teljesül, az idézett tétel szerint . Azonban és relatív prímek, hiszen legkisebb prímosztója , míg -nek csak -nél kisebb osztói lehetnek. Kaptuk tehát, hogy , vagyis osztója -nek, ez pedig csak úgy lehetséges, ha . Ezzel a bizonyítást befejeztük. II. megoldás. Felhasználjuk a Fermat-tétel ugyancsak közismert általánosítását, az Euler‐Fermat-tételt: ha és egymáshoz relatív prímek, akkor , ahol az -nél nem nagyobb, -hez relatív prím pozitív egészek száma (pl. . Ezt a függvényt Euler-féle függvénynek nevezik. Szükségünk lesz a függvénynek arra az egyszerű tulajdonságára is, hogy ha , akkor , hiszen az önmagához nem relatív prím, rajta kívül pedig csak olyan pozitív egész van, amelyik -nél nem nagyobb. Tegyük fel, hogy a feladat állítása hamis, azaz van olyan , -nél nagyobb egész, amelyik -tel nem osztható, de -nek osztója. Legyen a legkisebb ilyen szám. A feltétel szerint . Ebből következik, hogy a -hoz relatív prím; így az Euler‐Fermat tétel szerint Legyen és legnagyobb közös osztója . Mivel , nyilván . Másrészt az I. megoldásban idézett tétel szerint és ‐ mivel osztója az -nak ‐ . Az is igaz, hogy nem osztható -tel, mert sem osztható -tel. Végül , mert teljesül, de , azaz nem. A következőket tudjuk tehát -ről: -nél nagyobb és -nál kisebb egész szám, osztója -nek, de nem osztható -tel. Ez azt jelenti, hogy egy -nál kisebb ellenpélda a feladat állítására. Ez viszont ellentmondás, mert a legkisebb ellenpélda az . Az indirekt feltevésből ellentmondásra jutottunk, és ezzel igazoltuk az állítást. Megjegyzések. 1. Mindkét idézett tétel megtalálható Niven-Zuckermann: Bevezetés a számelméletbe című könyvében (29. oldal). A tételek bizonyítása nem nehéz, több természetes bizonyítás adható az első tételre, a második tétel pedig a Fermat-tételhez hasonlóan bizonyítható. 2. A második megoldásban látott módszert "végtelen leszállásnak'' nevezik. Ez a teljes indukció indirekt változata, amikor nem azt bizonyítjuk be, hogy ha egy természetes számokra vonatkozó állítás igaz valamennyi az -nél kisebb számra, akkor igaz az -re is, hanem azt, hogy ha az -re nem teljesül az állítás, akkor van egy -nél kisebb pozitív egész is, amire nem teljesül. Sok esetben kényelmesebb a végtelen leszállás módszere, mint a teljes indukció. |