Kezdőlap


Feladat:	1339. matematika feladat	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Szalay Mihály
Füzet:	1965/szeptember, 23 - 24. oldal		PDF \| MathML
Témakör(ök):	Szorzat, hatványozás azonosságai, Maradékosztályok, Euler-Fermat-tételek, Maradékos osztás, Feladat
Hivatkozás(ok):	Feladatok: 1964/október: 1339. matematika feladat

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.

a) $n$ helyére az első tíz természetes számot véve $2^{n} - 1$ értéke

\begin{matrix} 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, \end{matrix}

és ezek

7

-tel osztva rendre a következő maradékot adják:

\begin{matrix} 1, 3, 0, 1, 3, 0, 1, 3, 0, 1. \end{matrix}

Nézzük meg, hogy a maradékoknak ez a periodikus ismétlődése folytatódik-e. Ha

n = 3 k

, ahol

k

természetes szám, akkor

\begin{matrix} 2^{n} - 1 = 2^{3 k} - 1 = 8^{k} - 1^{k} = (8 - 1) A = 7 A, \end{matrix}

és itt

A

egész szám, mert bármely pozitív egész

k

kitevő esetén

a^{k} - b^{k}

osztható

a - b

-vel.

n = 3 k + 1

és

n = 3 k + 2

esetén pedig

\begin{matrix} 2^{3 k + 1} - 1 = 2 \cdot 2^{3 k} - 1 = 2 (2^{3 k} - 1) + 1 = 2 \cdot 7 B + 1 = 7 C + 1, \\ 2^{3 k + 2} - 1 = 2^{2} \cdot 2^{3 k} - 1 = 4 (2^{3 k} - 1) + 3 = 4 \cdot 7 D + 3 = 7 E + 3, \end{matrix}

ahol

B

és

D

az első eset szerint egész számok, így pedig

C

és

E

is egész számok. Ezzel bebizonyítottuk, hogy pozitív egész

n

esetén

2^{n} - 1

akkor és csak akkor osztható

7

-tel, ha

n

osztható

3

-mal.
b)

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

, így

7

-tel való osztásánál a maradék az előzők szerint sohasem

0

, ugyanis

n = 3 k

esetén a maradék

2

n = 3 k + 1

esetén

3

n = 3 k + 2

esetén pedig

5

Szalay Mihály (Budapest, Vörösmarty M. g. IV. o. t.)