Kezdőlap


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

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: $3 ∣ 2 + 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 $3^{k + 2} ∣ 2^{3^{k + 1}} + 1$ . Az

\begin{matrix} a^{3} + b^{3} = (a + b) (a^{2} - a b + b^{2}) \end{matrix}

azonosságot felhasználva:

\begin{matrix} 2^{3^{k + 1}} + 1 = {(2^{3^{k}})}^{3} + 1^{3} = (2^{3^{k}} + 1) ({(2^{3^{k}})}^{2} - 2^{3^{k}} + 1) . \end{matrix}

Az indukciós feltevés szerint

(2^{3^{k}} + 1)

osztható

3^{k + 1}

-gyel, így már csak a szorzat másik tényezőjéről kell belátnunk, hogy osztható

3

-mal.

\begin{matrix} {(2^{3^{k}})}^{2} - 2^{3^{k}} + 1 = {(2^{3^{k}} + 1)}^{2} - 3 \cdot 2^{3^{k}} . \end{matrix}

Itt

{(2^{3^{k}} + 1)}^{2}

osztható

{(3^{k + 1})}^{2}

-tel szintén az indukciós feltevés miatt,

3 \cdot 2^{3^{k}}

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

{(2^{3^{k}})}^{2} - 2^{3^{k}} + 1

osztható 3-mal: 3-mal nem osztható négyzetszám 3-mal osztva 1 maradékot ad, vagyis

{(2^{3^{k}})}^{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

{(2^{3^{k}})}^{2} - 2^{3^{k}} + 1

valóban osztható 3-mal.
2. Sokan a

{(2^{3^{n}})}^{3} + 1 = {(2^{3^{n}} + 1)}^{3} - 3 {(2^{3^{n}})}^{2} - 3 (2^{3^{n}})

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 = 3^{n + 1}

; ekkor éppen azok a számok relatív prímek az

m

-hez, amelyek nem oszthatók 3-mal. Így

φ (3^{n + 1}) = 3^{n + 1} - 3^{n} = 2 \cdot 3^{n}

. Válasszuk az

a

-t például 2-nek, ekkor az Euler‐Fermat-tétel szerint

2^{2 \cdot 3^{n}} - 1 = (2^{3^{n}} + 1) (2^{3^{n}} - 1)

osztható

3^{n + 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.