Kezdőlap


Feladat:	1564. matematika feladat	Korcsoport: 14-15	Nehézségi fok: átlagos
Füzet:	1968/november, 114 - 116. oldal		PDF \| MathML
Témakör(ök):	Maradékos osztás, Prímtényezős felbontás, Feladat
Hivatkozás(ok):	Feladatok: 1967/november: 1564. 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.

I. Megoldás. Képezzük külön-külön a 2-es alap, majd a 6-os, 7-es, 8-as alapok $1$ , $2$ , $...$ , $10$ kitevőjű hatványának $11$ -gyel való osztásában fellépő ( $11$ -nél kisebb, nem negatív) maradékot (lásd a táblázatot). Ebben felhasználjuk, hogy ha egy szorzatban a tényezőket olyan számokkal helyettesítjük, melyek $11$ -gyel osztva ugyanannyi maradékot adnak, mint az eredetiek, akkor az új szorzat is annyi maradékot ad $11$ -gyel osztva, mint az eredeti. Valóban, ha az $a \cdot b$ szorzatban $a$ helyére $a_{1}$ -et, $b$ helyére $b_{1}$ -et írunk, ahol $a$ és $a_{1}$ , ill. $b$ és $b_{1}$ $11$ -gyel osztva ugyanazt a maradékot adják, azaz $a - a_{1}$ és $b - b_{1}$ osztható $11$ -gyel, akkor $a_{1} b_{1}$ és $a b$ maradéka is egyenlő, azaz $a b - a_{1} b_{1}$ is osztható $11$ -gyel:

\begin{matrix} a b - a_{1} b_{1} = a b - a_{1} b + a_{1} b - a_{1} b_{1} = (a - a_{1}) b + a_{1} (b - b_{1}), \end{matrix}

mert mindkét tag egyik-egyik tényezője osztható vele.

\begin{matrix} n= & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & esetén \\ 2^{n}maradéka & 2 & 4 & 8 & 5 & 10 & 9 & 7 & 3 & 6 & 1 \\ 6^{n}maradéka & 6 & 3 & 7 & 9 & 10 & 5 & 8 & 4 & 2 & 1 \\ 7^{n}maradéka & 7 & 5 & 2 & 3 & 10 & 4 & 6 & 9 & 8 & 1 \\ 8^{n}maradéka & 8 & 9 & 6 & 4 & 10 & 3 & 2 & 5 & 7 & 1 \end{matrix}

Eszerint mind a négy alap

10.

hatványának

1

a maradéka. Ez fölöslegessé teszi a további kitevők vizsgálatát, mert a maradékok sorozata mindegyik alap esetében

10

-esével szakaszosan ismétlődik. Valóban,

a

-val a négy alap bármelyikét jelölve

\begin{matrix} a^{10} = 11 B + 1, \end{matrix}

tehát ha

a^{n}

maradéka

r_{2}

, azaz

\begin{matrix} a^{n} = 11 C + r_{2}, \end{matrix}

akkor

\begin{matrix} a^{n + 10} = a^{n} \cdot a^{10} = (11 C + r_{2}) (11 B + 1) = 11 D + r_{2}, \end{matrix}

ahol

\begin{matrix} D = 11 B C + B r_{2} + C, \end{matrix}

és ez állításunkat igazolja.
Eszerint

α = 10 m

(ahol

0 < m < k

) és bármely szóba jövő

k

szám esetén az (1) kifejezésben mindegyik kitevő

10 n

alakú

(n > 0)

, tehát mindegyik hatvány maradéka

1

, és a kifejezés maradéka

1 + 1 - 1 - 1 = 0

. Ezzel azt kaptuk, hogy (1) helyett elég vizsgálni a

\begin{matrix} (8^{α} - 7^{10 - α}) + (6^{10 - α} - 2^{α}) \end{matrix}

(2)

kifejezést, ahol

0 < α < 10

.
Táblázatunk szerint a 6-os alap maradékainak sorozata fordított sorrendben megegyezik a

2

-es alap maradékainak sorozatával, emiatt a

6^{10 - α} - 2^{α}

különbség

11

-gyel való osztásában a maradék mindig

0

. Ugyanezek állnak a

7

-es és

8

-as alap maradékainak sorozatára, ill. a (2)-beli első zárójeles kifejezésre, így a (2) kifejezés ‐ és vele (1) is ‐ minden szóba jövő esetben

0

maradékot ad, osztható

11

-gyel.

II. megoldás. Figyeljük meg, hogy egy-egy kisebbítendő és kivonandó alapjának szorzata

1

maradékot ad

11

-gyel osztva:

\begin{matrix} 6 \cdot 2 = 11 + 1, 8 \cdot 7 = 55 + 1. \end{matrix}

Megmutatjuk, hogy ennek lényeges szerepe van a feladat állításának helyes voltában; általában, ha

a \cdot b - 1

osztható

11

-gyel, akkor

\begin{matrix} D = a^{10 k + α} - b^{10 k - α} \end{matrix}

osztható

11

-gyel, így

8^{10 k + α} - 7^{10 k - α}

és

6^{10 k + α} - 2^{10 k - α}

is, tehát a feladatban szereplő kifejezés is osztható

11

-gyel.
Valóban,

\begin{matrix} D = a^{10 k + α} - b^{10 k - α} = a^{10 k + α} - a^{α} b^{10 k} + a^{α} b^{10 k} - b^{10 k - α} = a^{α} [{(a^{10})}^{k} - {(b^{10})}^{k}] + \\ b^{10 k - α} [{(a b)}^{α} - 1], \end{matrix}

és itt az első tag osztható a

c = a^{10} - b^{10}

, a második az

a b - 1

különbséggel. Feltételünk szerint az utóbbi osztható

11

-gyel, azt kell tehát csak megmutatnunk, hogy

c

osztható

11

-gyel.
A feltételből következik, hogy sem

a

, sem

b

nem osztható

11

-gyel, különben

a b

volna vele osztható, nem pedig

a b - 1

c

így alakítható:

\begin{matrix} c = (a^{10} - 1) - (b^{10} - 1), \end{matrix}

elég tehát megmutatnunk, hogy ha egy

d

egész szám nem osztható

11

-gyel, akkor

d^{10} - 1

osztható vele. Láttuk az I. megoldásban, hogy ezt elég a

d = 1

2

...

10

számokra megmutatni. Ez

d = 1

-re nyilvánvaló, a

d = 2

6

7

8

számokra fent láttuk; a

d = 3

4

5

9

10

számokból előállítjuk rendre

d^{2}

d^{3}

d^{5}

d^{10}

maradékát, menet közben az egyes hatványokat mindjárt helyettesítve a

11

-gyel való osztásukból adódó maradékkal:

\begin{matrix} d= & 3 & 4 & 5 & 9 & 10 & esetén \\ d^{2}maradéka & 9 & 5 & 3 & 4 & 1 \\ d^{3}maradéka & 5 & 9 & 4 & 3 & 10 \\ d^{5}maradéka & 1 & 1 & 1 & 1 & 10 \\ d^{10}maradéka & 1 & 1 & 1 & 1 & 1 \end{matrix}

Ezzel bizonyításunkat befejeztük.

Megjegyzés. Elkerülhettük volna az utolsó lépés numerikus számolását Fermat tételének alkalmazásával, mely szerint ha

p

törzsszám és

a

nem osztható

p

-vel, akkor

a^{p - 1} - 1

osztható

p

-vel.