Kezdőlap


Feladat:	481. matematika gyakorlat	Korcsoport: 14-15	Nehézségi fok: könnyű
Megoldó(k):	Gazsi Lajos , Németh Attila
Füzet:	1958/november, 89 - 90. oldal		PDF \| MathML
Témakör(ök):	Maradékos osztás, Oszthatósági feladatok, Gyakorlat
Hivatkozás(ok):	Feladatok: 1958/március: 481. matematika gyakorlat

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: A 473. gyakorlatban (lásd 81. o.) tett megállapításunkat ‐ amely szerint, ha $b = c k + d$ , akkor $b^{n} = c K + d^{n}$ , ahol $b$ , $c$ , $k$ , $d$ , $K$ egész számok és $n$ pozitív egész szám ‐ úgy is kimondhatjuk, hogy a $b^{n} : c$ osztás maradéka ugyanaz, mint a $d^{n} : c$ osztásé, ahol $d = b - c k$ . Ezt $b = 5342$ és $c = 11$ -gyel alkalmazva $d$ -t vehetjük az $5342 : 11$ osztás maradékának, $7$ -nek, és így a keresett maradékot a $7^{82} : 11$ osztás maradékaként is megkaphatjuk.¹
Az alaphoz hasonlóan a kitevőben is áttérhetünk kisebb számon való vizsgálatra. Alkalmazhatjuk ugyanis feladatunkra Fermat tételét:² mivel $11$ törzsszám, továbbá $7$ és $11$ relatív prímek, azért $7^{11 - 1} - 1 = 7^{10} - 1$ osztható $11$ -gyel: $7^{10} - 1 = 11 k$ . Másrészt $7^{80} - 1 = {(7^{10})}^{8} - 1$ osztható $7^{10} - 1$ -gyel és így $11$ -gyel is, azért $7^{80} - 1 = 11 K$ , másképpen $7^{80} = 11 K_{1} + 1$ . Most már $7^{82} = 7^{2} \cdot 7^{80} = 49 (11 K_{1} + 1) = 11 K_{2} + 49$ és ez azt mutatja, hogy a keresett maradék annyi, mint a $49 : 11$ osztásé, vagyis $5$ .

Gazsi Lajos (Kaposvár, Táncsics M. g. II. o. t.)

II. megoldás: Miután

5342^{82}

vizsgálatáról áttértünk

7^{82}

-ére, a maradék megállapításában hatványról hatványra haladhatunk tovább. Eközben nem szükséges az egyes hatványokat tényleg kiszámítani, mert ha egy hatvány maradékát már kiszámítottuk, a következő hatvány maradéka ugyanannyi, mint a már megkapott maradék

7

-szeresének a maradéka. Valóban, ha

\begin{matrix} 7^{n} = 11 K_{n} + r_{n}, \end{matrix}

akkor

\begin{matrix} 7^{n + 1} = 7 \cdot 7^{n} = 7 (11 K_{n} + r_{n}) = 11 \cdot 7 \cdot K_{n} + 7 r_{n} . \end{matrix}

Mivel továbbá

11

-gyel való osztásnál legfeljebb

11

-féle különböző maradék léphet fel, így legkésőbb a

12

lépésig egy maradéknak kétszer kell fellépnie, és attól kezdve a maradékok periodikusan ismétlődnek, ami ismét megkönnyíti a számolást.
A számolás így alakul:

11

-gyel való osztásnál

\begin{matrix} 7^{1} & maradéka & 7, \\ 7^{2} = 49 & '' & 5, \\ 7^{3} & '' & =7 \cdot 5 = 35, & maradéka & = & 2, \\ 7^{4} & '' & =7 \cdot 2 = 14, & '' & = & 3, \\ 7^{5} & '' & =7 \cdot 3 = 21, & '' & = & 10, \\ 7^{6} & '' & =7 \cdot 10 = 70, & '' & = & 4, \\ 7^{7} & '' & =7 \cdot 4 = 28, & '' & = & 6, \\ 7^{8} & '' & =7 \cdot 6 = 42, & '' & = & 9, \\ 7^{9} & '' & =7 \cdot 9 = 63, & '' & = & 8, \\ 7^{10} & '' & =7 \cdot 8 = 56, & '' & = & 1, \\ 7^{11} & '' & =7 \cdot 1 = 7. \end{matrix}

Innen tehát periodikusan ismétlődnek a

7

5

2

3

10

4

6

9

8

1

maradékok. A

20

-ik,

30

-ik,

...,80

-ik hatvány maradéka újra

1

lesz, a

81

-iké

7

, a

7

-nek a

82

-ik hatványa pedig

5

-öt ad maradékul

11

-gyel való osztásnál, és ezzel együtt

5342^{22}

is.

Németh Attila (Győr, Bencés g. I. o. t.)

Megjegyzések: A kisebb alapra és kisebb kitevőre való áttérésben lényegében a fenti gondolatmenetek mellett számos más átalakítást is használtak megoldóink. Néhány ilyen (a nagy betűk egész számokat jelölnek):

\begin{matrix} 5342 = 11 \cdot 486 - 4; \end{matrix}