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. A feladatban szereplő szám , és nyilván nem osztható 3-mal (hiszen számjegyeinek összege , ami nem osztható 3-mal). Azt fogjuk megmutatni, hogy a szám minden 3-nál nagyobb prímosztója 1-esre végződik. (Ez nyilván elegendő, mivel sem 2-vel, sem pedig 3-mal nem osztható, és minden 1-nél nagyobb osztója prímosztók szorzatára bontható; 1-re végződő számok szorzata pedig szintén 1-re végződik.) Legyen és pozitív egész, pedig olyan egész szám, amelyre . Jelölje azt a legkisebb pozitív egészet, amelyre ; megmutatjuk, hogy ekkor . A szerinti indukcióval bizonyítunk: -re az állítás nyilvánvalóan igaz; tegyük föl, hogy minden olyan, -nál kisebb természetes számra, amelyre fennáll, egyúttal is teljesül. Az nyilván osztója a különbségnek is. Mivel , azért , és így minden hatványa is relatív prím az -hez; így is osztható -mel. Indukciós feltevésünk értelmében osztható -rel, de akkor is. Legyen ezután a -nek egy, a 3-nál nagyobb prímosztója, és jelölje a legkisebb pozitív egészet, amelyre . Mint beláttuk, ekkor , tehát . Mivel , az nagyobb 1-nél, így . Alkalmazzuk -re és 10-re (amely a -hez nyilvánvalóan relatív prím) a kis Fermat-tételt, miszerint . Az előbbihez hasonlóan kapjuk, hogy osztható az -rel, speciálisan 5-tel is. Mivel nem a 2, azért a 2-vel is osztható, ebből pedig következik, hogy osztható -zel. Ez éppen azt jelenti, hogy a 10-es alapú számrendszerben 1-esre végződik. |