Kezdőlap


Feladat:	B.4051	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Ágoston Tamás , Bodor Bertalan , Cséke Balázs , Éles András , Márkus Bence , Nagy Donát , Somogyi Ákos , Tossenberger Anna , Varga László , Véges Márton
Füzet:	2008/október, 409 - 410. oldal		PDF \| MathML
Témakör(ök):	Oszthatósági feladatok, Prímtényezős felbontás, Maradékos osztás, kongruenciák, Teljes indukció módszere, Feladat
Hivatkozás(ok):	Feladatok: 2007/december: B.4051

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.

Megoldás. A feladatban szereplő szám $S = \frac{10^{5^{n}} - 1}{9}$ , és nyilván nem osztható 3-mal (hiszen számjegyeinek összege $5^{n}$ , ami nem osztható 3-mal). Azt fogjuk megmutatni, hogy a $10^{5^{n}} - 1$ szám minden 3-nál nagyobb prímosztója 1-esre végződik. (Ez nyilván elegendő, mivel $S$ sem 2-vel, sem pedig 3-mal nem osztható, és minden 1-nél nagyobb osztója prímosztók szorzatára bontható; 1-re végződő számok szorzata pedig szintén 1-re végződik.)
Legyen $m$ és $k$ pozitív egész, $c$ pedig olyan egész szám, amelyre $m ∣ c^{k} - 1$ . Jelölje $r$ azt a legkisebb pozitív egészet, amelyre $m ∣ c^{r} - 1$ ; megmutatjuk, hogy ekkor $r ∣ k$ . A $k$ szerinti indukcióval bizonyítunk: $k = r$ -re az állítás nyilvánvalóan igaz; tegyük föl, hogy minden olyan, $k$ -nál kisebb $v$ természetes számra, amelyre $m ∣ c^{v} - 1$ fennáll, egyúttal $r ∣ v$ is teljesül. Az $m$ nyilván osztója a

\begin{matrix} (c^{k} - 1) - (c^{r} - 1) = c^{r} (c^{k - r} - 1) \end{matrix}

különbségnek is. Mivel

m ∣ c^{k} - 1

, azért

c^{k}

, és így

c

minden hatványa is relatív prím az

m

-hez; így

c^{k - r} - 1

is osztható

m

-mel. Indukciós feltevésünk értelmében

k - r

osztható

r

-rel, de akkor

k

is.
Legyen ezután

p

(10^{5^{n}} - 1)

-nek egy, a 3-nál nagyobb prímosztója, és jelölje

r

a legkisebb pozitív egészet, amelyre

p ∣ 10^{r} - 1

. Mint beláttuk, ekkor

r ∣ 5^{n}

, tehát

r = 5^{s}

. Mivel

p > 3

, az

r

nagyobb 1-nél, így

5 ∣ r

. Alkalmazzuk

p

-re és 10-re (amely a

p

-hez nyilvánvalóan relatív prím) a kis Fermat-tételt, miszerint

p ∣ 10^{p - 1} - 1

. Az előbbihez hasonlóan kapjuk, hogy

p - 1

osztható az

r

-rel, speciálisan 5-tel is. Mivel

p

nem a 2, azért

p - 1

a 2-vel is osztható, ebből pedig következik, hogy

p - 1

osztható

5 \cdot 2 = 10

-zel. Ez éppen azt jelenti, hogy

p

a 10-es alapú számrendszerben 1-esre végződik.