Kezdőlap


Feladat:	F.1911	Korcsoport: 16-17	Nehézségi fok: -
Füzet:	1974/november, 126 - 127. oldal		PDF \| MathML
Témakör(ök):	Nevezetes azonosságok, Maradékos osztás, Feladat
Hivatkozás(ok):	Feladatok: 1974/január: F.1911

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 mértani sorozat összegére vonatkozó összefüggésből következik, hogy ha $n$ természetes szám, akkor

\begin{matrix} A^{n} - B^{n} = (A - B) (A^{n - 1} + A^{n - 2} B + ... + B^{n - 1}) . \end{matrix}

Emiatt, ha

A

és

B

egész számok és

n

természetes szám,

A^{n} - B^{n}

osztható

(A - B)

-vel, ha pedig

n

páratlan, akkor

A^{n} + B^{n} = A^{n} - {(- B)}^{n}

osztható

A - (- B) = (A + B)

-vel. Ezek alapján fogjuk a

2^{888} : 61

osztás maradékát a kettes alap alacsonyabb hatványainak

61

-gyel való osztásából kapott maradékaiból meghatározni.
A kettes alap első néhány hatványa közül a

6

-ik ad aránylag kis maradékot

61

-gyel osztva:

2^{6} = 61 + 3

. Az így kapott

3

maradékot tovább hatványozva, az

5

-ik hatvány jut ismét közel egy

61

-gyel osztható számhoz:

3^{5} = 4 \cdot 61 - 1

. Ezekből következik, hogy az

\begin{matrix} N = 2^{30} + 1^{30} = [{(2^{6})}^{5} - 3^{5}] + [3^{5} + 1] \end{matrix}

szám osztható

61

-gyel, hiszen az utóbbi alakjában az első tag osztható

2^{6} - 3 = 61

-gyel, és mint láttuk, a második tag is osztható

61

-gyel. Mivel az

\begin{matrix} M = {(2^{30})}^{29} + 1^{29} \end{matrix}

szám osztható

2^{30} + 1 = N

-nel, ez az

M

szám is osztható

61

-gyel. Ezt felhasználva kapjuk, hogy

\begin{matrix} 2^{888} - 888 = 2^{18} \cdot {(2^{30})}^{29} - 888 = 2^{18} \cdot M - 2^{18} - 888 = 2^{18} \cdot M - [{(2^{6})}^{3} - 3^{3}] - 915 \end{matrix}

is osztható

61

-gyel, hiszen az utolsó alakjában az első tagban

M

osztható

61

-gyel, a második tag osztható

2^{6} - 3 = 61

-gyel, és

915 = 61 \cdot 15

. Állításunkat ezzel bebizonyítottuk.

Megjegyzések. 1. Mivel

2^{60} - 1 = (2^{30} - 1) (2^{30} + 1)

, ez a szám is osztható

61

-gyel. Ez az állítás következik az ún.,,kis Fermat-tétel''-ből, mely szerint

a^{p - 1} - 1

osztható

p

-vel, ha

p

törzsszám, és a

p

-vel nem osztható egész szám. Sokan ezt felhasználva kapták, hogy a

2^{888} : 61

osztás maradéka egyenlő a

2^{48} : 61

osztás maradékával. De mivel az utóbbi meghatározásához már semmiféle,,nagy ágyút'' nem tudtak előrántani, többnyire ügyetlen, hosszadalmas számolásba keveredtek, és így végül is többet bajlódtak, mintha fel sem használták volna Fermat tételét.
2. Feladatunk kapcsolatos a pontversenyen kívül közölt 198-as problémával, a kapcsolatra annak megoldása során még visszatérünk.