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. Megoldás. Az állítást -re vonatkozó teljes indukcióval bizonyítjuk. -ra az állítás teljesül: . Tegyük fel, hogy az állítás igaz -ra. Ennek felhasználásával szeretnénk belátni, hogy ekkor -re is igaz, vagyis . Az azonosságot felhasználva: | |
Az indukciós feltevés szerint osztható -gyel, így már csak a szorzat másik tényezőjéről kell belátnunk, hogy osztható -mal. | | Itt osztható -tel szintén az indukciós feltevés miatt, pedig osztható 3-mal, így a kettő különbsége is osztható 3-mal. Az állítás igaz -re is, ezzel minden természetes számra az állítást bebizonyítottuk.
Megjegyzések. 1. Többen a következő módon bizonyították, hogy osztható 3-mal: 3-mal nem osztható négyzetszám 3-mal osztva 1 maradékot ad, vagyis 3-mal osztva 1 maradékot ad; 2-nek páratlan kitevőjű hatványa 3-mal osztva 2 maradékot ad; és így valóban osztható 3-mal. 2. Sokan a azonosságot felhasználva bizonyították az állítást. 3. Legyen pozitív egész, és a számok közül az -hez relatív prímek számát jelölje . Az Euler‐Fermat-tétel szerint ekkor osztható -mel minden olyan egészre, ami relatív prím az -hez. Legyen ; ekkor éppen azok a számok relatív prímek az -hez, amelyek nem oszthatók 3-mal. Így . Válasszuk az -t például 2-nek, ekkor az Euler‐Fermat-tétel szerint osztható -nel. A feladat állítása ebből azért következik, mert a második tényező még 3-mal sem osztható, hiszen 2-nek minden páratlan kitevőjű hatványa a 3-mal maradékosan osztva 2-t ad maradékul. |