Kezdőlap


Feladat:	B.3512	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Rácz Béla András
Füzet:	2002/október, 411 - 414. oldal		PDF \| MathML
Témakör(ök):	Legkisebb közös többszörös, Lineáris kongruenciák, Binomiális tétel, Feladat
Hivatkozás(ok):	Feladatok: 2002/január: B.3512

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)$ Csak az olyan számok között érdemes keresni, amelyekben 9-cel osztható számú egyes van, hiszen csak ezek oszthatók 9-cel. Legyen a számjegyek száma $9 n$ . Ekkor a szám szorzattá alakítható:

\begin{matrix} \begin{matrix} {\underset{︸}{111 ... 11}}_{9 n}^{} & = & 10^{9 n - 1} + 10^{9 n - 2} + ... + 10 + 1 = \\ = & 111 111 111 \cdot (10^{9 (n - 1)} + 10^{9 (n - 2)} + ... + 10^{9} + 1) . \end{matrix} \end{matrix}

Az első tényező szorzattá bomlik; a kilenc darab egyesből álló

111 111 111 = 111 \cdot 1 001 001

. Itt mindkét tényező osztható 3-mal, de 9-cel egyikük sem, a

9 n

-jegyű szám tehát pontosan akkor osztható 81-gyel, ha a 10-hatványok összegéből álló második tényező osztható 9-cel. Ez pedig akkor és csak akkor teljesül, ha 9-cel osztható számú 10-hatvány szerepel az összegben. A legkisebb

n

, amelyre ez igaz, a 9, tehát a 81 csupa egyesből álló legkisebb többszöröse a 81 darab egyesből álló szám.

b)

Ismét olyan számok között keresünk megfelelőt, amelyekben az 1-esek száma osztható 9-cel. A legkisebb szóbajövő számoknak tíz jegye van, egyikük 0. Minden ilyen szám megkapható úgy, hogy a tíz egyesből álló számból kivonunk egy nála kisebb 10-hatványt. Vizsgáljuk meg a 10-hatványok maradékát 81-gyel osztva a 0-tól a 9-es kitevőig.

\begin{matrix} \begin{matrix} kitevő & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ maradék & 1 & 10 & 19 & 28 & 37 & 46 & 55 & 64 & 73 & 1 \end{matrix} \end{matrix}

A tíz egyesből álló szám 81-es maradéka ezek összege:

334 = 4 \cdot 81 + 10

. A felsorolt 10-hatványok között van olyan, mégpedig pontosan egy, amelynek ugyanennyi a 81-es maradéka: ez a 10. Ezt elhagyva

1 111 111 101

adódik: ez a szám osztható 81-gyel, a többi legfeljebb tízjegyű egyesekből és nullákból álló szám pedig nem.
A vizsgált számok közül tehát a tízjegyű

1 111 111 101

a legkisebb.

Rácz Béla András (Budapest, Fazekas Mihály Főv. Gyak. Gimn., 10 o.t.)

II. megoldás. Először határozzuk meg a 10 hatványainak a maradékát 81-gyel osztva. Ha

U_{n}

jelöli az

n

darab egyessel felírt számot, akkor egyrészt

9 U_{n} = 10^{n} - 1

, másrészt

U_{n}

jegyeinek az öszege

n

. Ismeretes, hogy egy tizes számrendszerben felírt szám ugyanazt a maradékot adja 9-cel osztva, mint a számjegyeinek az összege:

U_{n} \equiv n (mod 9)

. Ezt a kongruenciát ‐ a modulussal együtt ‐ 9-cel szorozva kapjuk, hogy

9 U_{n} \equiv 9 n (mod 81)

, ahonnan

\begin{matrix} 10^{n} \equiv 9 n + 1 (mod 81) . \end{matrix}

(1)

Térjünk most rá a megoldásra. A fentiek szerint

a)

\begin{matrix} \begin{matrix} U_{n} & = 10^{0} + 10^{1} + ... + 10^{n - 1} \equiv 9 \cdot (0 + 1 + 2 + ... + (n - 1)) + n = \\ = \frac{n (9 (n - 1) + 2)}{2} (mod 81) . \end{matrix} \end{matrix}

Mivel

(2,81) = 1

, azért

81 ∣ U_{n}

pontosan akkor teljesül, ha

81 ∣ n (9 (n - 1) + 2)

. A szorzat második tényezője nem osztható 3-mal, így maga a szorzat pontosan akkor osztható 81-gyel, ha az első tényező,

n

a 81 többszöröse. A legkisebb ilyen

n

a 81, így a keresett szám a 81 darab egyessel felírt szám.

b)

A keresett szám osztható 9-cel, így a számjegyek összege is, tehát legalább 9 egyesből áll.
A fentiek szerint

U_{10} \equiv \frac{10 \cdot (9 \cdot 9 + 2)}{2} = 415 \equiv 10 (mod 81)

, ezért olyan 10-hatványt keresünk, amelyik 10 maradékot ad 81-gyel osztva. (1) szerint ez akkor teljesül, ha

\begin{matrix} 10^{k} \equiv 9 k + 1 \equiv 10 (mod 81), \end{matrix}

azaz

\begin{matrix} 9 k \equiv 9 (mod 81) . \end{matrix}

A talált kongruenciát a modulussal együtt 9-cel végigosztva

\begin{matrix} k \equiv 1 (mod 9), \end{matrix}

azaz

k = 1

. Ez pedig azt jelenti, hogy

U_{10} - 10 = {\underset{︸}{111 ... 11}}_{10}^{} - 10 = 1 111 111 101

osztható 81-gyel, ennél kisebb adott alakú szám pedig nem.

III. megoldás. A feladat

a)

részére.
A binomiális tétel szerint

10^{9} = {(9 + 1)}^{9} = \sum_{k = 0}^{9} (\binom{9}{k}) \cdot 9^{k}

. Vegyük észre, hogy ebben a kifejtésben csak az első két tag nem osztható

9^{3}

-nal:

9^{3} | (\binom{9}{2}) \cdot 9^{2}

, ha pedig

k \geq 3

, akkor

9^{k}

osztható

9^{3}

-nal. Eszerint

10^{9} \equiv 1 + 9^{2} (mod 9^{3})

. Ismét a binomiális tétel szerint

\begin{matrix} 10^{9 n} \equiv {(1 + 9^{2})}^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) \cdot 9^{2 k} (mod 9^{3}) . \end{matrix}

k \geq 2

, akkor a fenti kifejtés tagjai oszthatók

9^{3}

-nal, így

\begin{matrix} 10^{9 n} \equiv 1 + 81 n (mod 9^{3}) . \end{matrix}

Innen

U_{9 n} = \frac{10^{9 n} - 1}{9} \equiv 9 n (mod 9^{2})

, azaz

U_{9 n} \equiv 9 n (mod 81)

. Innen nyomban adódik, hogy

U_{9 n}

pontosan akkor osztható 81-gyel, ha 9

n

, tehát ha

n

osztható 9-cel.

Megjegyzések 1.) A második megoldásban felhasznált

10^{n} \equiv 1 + 9 n (mod 81)

kongruencia is megkapható a binomiális tétel felhasználásával.
2.) Az

n

-re vonatkozó teljes indukcióval igazolható, hogy

9^{n}

legkisebb olyan többszöröse, amelynek tízes számrendszerbeli alakja csak az 1 számjegyet tartalmazza a

9^{n}

jegyű

U_{9^{n}}

, pontosabban hogy

9^{n} ∣ U_{k}

akkor és csak akkor teljesül, ha

9^{n} ∣ k

. Ez azt jelenti, hogy a ,,csupaegy'' számok körében korlátlanul kiterjeszthető a 9-cel való oszthatóság szabálya: egy ilyen szám pontosan akkor osztható egy 9-hatvánnyal, ha a jegyeinek az összege ilyen. Ha pedig a jegyek száma egy 9-hatvány többszöröse, akkor még az a szabály is érvényben marad, hogy egy ilyen szám ugyanazt a maradékot adja egy megfelelő 9-hatvánnyal osztva, mint a jegyeinek az összege: a

k

-ra vonatkozó teljes indukcióval adódik, hogy

\begin{matrix} U_{m \cdot 9^{k}} \equiv 9^{k} \cdot U_{m} \equiv m \cdot 9^{k} (mod 9^{k + 1}) . \end{matrix}