Feladat: B.3908 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Treszkai László 
Füzet: 2007/április, 220 - 221. oldal  PDF file
Témakör(ök): Oszthatóság, Teljes indukció módszere, Nevezetes azonosságok, Feladat
Hivatkozás(ok):Feladatok: 2006/április: B.3908

Bizonyítsuk be, hogy 23n+1 minden n természetes számra osztható 3n+1-nel.

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 n-re vonatkozó teljes indukcióval bizonyítjuk.
n=0-ra az állítás teljesül: 32+1.
Tegyük fel, hogy az állítás igaz n=k-ra. Ennek felhasználásával szeretnénk belátni, hogy ekkor n=(k+1)-re is igaz, vagyis 3k+223k+1+1. Az

a3+b3=(a+b)(a2-ab+b2)
azonosságot felhasználva:
23k+1+1=(23k)3+13=(23k+1)((23k)2-23k+1).

Az indukciós feltevés szerint (23k+1) osztható 3k+1-gyel, így már csak a szorzat másik tényezőjéről kell belátnunk, hogy osztható 3-mal.
(23k)2-23k+1=(23k+1)2-323k.
Itt (23k+1)2 osztható (3k+1)2-tel szintén az indukciós feltevés miatt, 323k pedig osztható 3-mal, így a kettő különbsége is osztható 3-mal.
Az állítás igaz n=(k+1)-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 (23k)2-23k+1 osztható 3-mal: 3-mal nem osztható négyzetszám 3-mal osztva 1 maradékot ad, vagyis (23k)2  3-mal osztva 1 maradékot ad; 2-nek páratlan kitevőjű hatványa 3-mal osztva 2 maradékot ad; és így (23k)2-23k+1 valóban osztható 3-mal.
2. Sokan a (23n)3+1=(23n+1)3-3(23n)2-3(23n) azonosságot felhasználva bizonyították az állítást.
3. Legyen m pozitív egész, és a 0,1,2,...,m-1 számok közül az m-hez relatív prímek számát jelölje φ(m). Az Euler‐Fermat-tétel szerint ekkor aφ(m)-1 osztható m-mel minden olyan a egészre, ami relatív prím az m-hez. Legyen m=3n+1; ekkor éppen azok a számok relatív prímek az m-hez, amelyek nem oszthatók 3-mal. Így φ(3n+1)=3n+1-3n=23n. Válasszuk az a-t például 2-nek, ekkor az Euler‐Fermat-tétel szerint 223n-1=(23n+1)(23n-1) osztható 3n+1-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.