Kezdőlap


Feladat:	B.3525	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Bóka Gergely
Füzet:	2002/december, 534 - 535. oldal		PDF \| MathML
Témakör(ök):	Számsorozatok, Euler-Fermat-tételek, Lineáris kongruenciák, Feladat
Hivatkozás(ok):	Feladatok: 2002/február: B.3525

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 31 prímszám, azért a ,,kis'' Fermat-tétel szerint osztója a $10^{30} - 1$ számnak. Mivel ${(10^{30})}^{k} - 1^{k}$ osztható $(10^{30} - 1)$ -gyel, azért a 31 osztója az összes $10^{30 k} - 1$ alakú számnak is ( $k$ tetszőleges pozitív egész). Osztója tehát ezen számok harmadrészének is, vagyis minden olyan számnak, ami $30 k$ darab 3-as számjegyből áll. Egy ilyen számot 100-zal megszorozva, majd az eredményhez 31-et hozzáadva újfent 31-gyel osztható számhoz jutunk, és minden ilyen szám a megadott sorozathoz tartozik. Ezek szerint 31-től kezdve a sorozat minden 30-adik eleme osztható 31-gyel, ezek tehát a 31 kivételével valamennyien összetettek. Ezzel beláttuk, hogy a sorozatban végtelen sok összetett szám van.

Megjegyzés. A ,,kis'' Fermat-tételt számos számelmélettel foglalkozó könyvben megtalálhatjuk, például Dr. Szalay Mihály: Számelmélet című tankönyvében is.

II. megoldás. Az

1,31,331,3331, ...

sorozatban végtelen sok olyan elem van, amelyben

16 k + 8

darab 3-as van. Tekintsük ezeket az elemeket:

\begin{matrix} {\underset{︸}{333 ... 333}}_{16 k + 8 db}^{} 1 = \frac{{\overset{}{\overset{︷}{999 ... 999}}}_{}^{16 k + 8 db} 3}{3} = \frac{{\overset{}{\overset{︷}{999 ... 9999}}}_{}^{16 k + 9 db} - 6}{3} = \frac{10^{16 k + 9} - 1 - 6}{3} = \frac{10^{16 k + 9} - 7}{3} . \end{matrix}

Ha belátjuk, hogy

17 ∣ 10^{16 k + 9} - 7

, akkor

(3; 17) = 1

miatt

\frac{10^{16 k + 9} - 7}{3}

is osztható 17-tel, azaz

17 ∣ {\underset{︸}{333 ... 333}}_{16 k + 8}^{} 1

is fennáll. Ehhez igazolni kell, hogy

10^{16 k + 9} \equiv 7 mod 17

.
A kongruencia szabályait felhasználva:

\begin{matrix} 10^{16 k + 9} & = & 10^{9} \cdot {(10^{16})}^{k} = 1000^{3} \cdot {(10 000^{4})}^{k} = \\ = & {(58 \cdot 17 + 14)}^{3} \cdot {({(588 \cdot 17 + 4)}^{4})}^{k} \equiv 14^{3} \cdot {(4^{4})}^{k} = \\ = & (161 \cdot 17 + 7) {(15 \cdot 17 + 1)}^{k} \equiv 7 \cdot 1^{k} = 7 (mod 17) . \end{matrix}

Tehát

10^{16 k + 9} - 7 \equiv 0 (mod 17)

, így

17 ∣ {\underset{︸}{333 ... 333}}_{16 k + 8}^{} 1

minden

k

-ra. A sorozatnak végtelen sok eleme osztható 17-tel, ezért végtelen sok eleme összetett.

Bóka Gergely (Szolnok, Verseghy Ferenc Gimn., 11. évf.)