Kezdőlap


Feladat:	C.940	Korcsoport: 14-15	Nehézségi fok: átlagos
Megoldó(k):	Nagy Dóra
Füzet:	2009/január, 23 - 24. oldal		PDF \| MathML
Témakör(ök):	Oszthatósági feladatok, Teljes indukció módszere, C gyakorlat
Hivatkozás(ok):	Feladatok: 2008/április: C.940

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. $n = 1$ -re $2^{4} + 1 = 17$ , $n = 2$ -re $2^{8} - 1 = (2^{4} + 1) (2^{4} - 1) = 17 \cdot 15$ .
Sejtésünk az, hogy ha $n$ páratlan, akkor 17 a $(2^{4 n} - 1)$ -nek, ha pedig páros, akkor a $(2^{4 n} + 1)$ -nek osztója. Sejtésünket teljes indukcióval bizonyítjuk.
Legyen $n = 2 k + 1$ ( $k = 0,1,2, ...)$ . Láttuk, hogy $n = 1$ -re igaz az állítás. Tegyük fel, hogy $n = (2 k + 1)$ -re is igaz, azaz

\begin{matrix} 2^{4 (2 k + 1)} + 1 = 2^{8 k + 4} + 1 = 17 \cdot x, \end{matrix}

ahol

x

egész. Belátjuk, hogy akkor

n = [2 (k + 1) + 1]

-re is igaz, vagyis a tulajdonság öröklődik.

\begin{matrix} 2^{4 [2 (k + 1) + 1]} + 1 & = 2^{8 k + 4} \cdot 2^{8} + 1 = (17 x - 1) \cdot 2^{8} + 1 = 17 \cdot 2^{8} x - 2^{8} + 1 = \\ = 17 \cdot 256 \cdot x - 255 = 17 \cdot 256 \cdot x - 17 \cdot 15, \end{matrix}

s ez osztható 17-tel.
Legyen most

n = 2 k

(

k = 1,2,3, ...)

n = 2

-re igaz az állítás. Tegyük fel, hogy

n = 2 k

-ra is igaz:

2^{4 n} - 1 = 2^{8 k} - 1 = 17 \cdot y

, és legyen

n = 2 (k + 1)

, ekkor

\begin{matrix} 2^{4 (2 (k + 1))} - 1 = 2^{8 k} \cdot 2^{8} - 1 = (17 y + 1) \cdot 2^{8} - 1 = 17 \cdot 256 \cdot y + 17 \cdot 15. \end{matrix}

Valóban, ez is osztható 17-tel. Ezzel a bizonyítást befejeztük.

II. megoldás.

2^{4 n} = {(2^{4})}^{n} = 16^{n}

.
Legyen

n

páros, ekkor

n = 2 k

, és

\begin{matrix} 2^{4 n} - 1 = 16^{2 k} - 1^{2 k} = (16 + 1) (16^{2 k - 1} - 16^{2 k - 2} + 16^{2 k - 3} - ... + 16 - 1) = 17 \cdot a, \end{matrix}

ahol

a \geq 1

és egész, amennyiben

k \geq 1

. Vagyis ha

n

pozitív páros szám, akkor

17 ∣ 2^{4 n} - 1

.
Legyen

n

páratlan, ekkor

n = 2 k + 1

, és

\begin{matrix} 2^{4 n} + 1 = 16^{2 k + 1} - 1^{2 k + 1} = (16 + 1) (16^{2 k} - 16^{2 k - 1} + 16^{2 k - 2} - ... - 16 + 1) = 17 \cdot b, \end{matrix}

ahol

b \geq 1

és egész, amennyiben

k \geq 1

. Vagyis ha

n

pozitív páratlan szám, akkor

17 ∣ 2^{4 n} + 1