Kezdőlap


Feladat:	Gy.2415	Korcsoport: 16-17	Nehézségi fok: átlagos
Füzet:	1988/január, 22 - 23. oldal		PDF \| MathML
Témakör(ök):	Nevezetes azonosságok, Rekurzív eljárások, Maradékos osztás, Oszthatósági feladatok, "a" alapú számrendszer (a >1, egész szám), Gyakorlat
Hivatkozás(ok):	Feladatok: 1987/május: Gy.2415

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.

Ha $n$ lépésben fejeződik be az eljárás, tehát $r_{n}$ jelöli az utolsó nem nulla maradékot, akkor a maradékok éppen az $A$ szám $50$ -alapú számrendszerbeli alakjának "számjegyei'', azaz

\begin{matrix} A = r_{n} \cdot 50^{n - 1} + ... + r_{2} \cdot 50 + r_{1} . \end{matrix}

Ekkor nyilván

\begin{matrix} A = r_{n} (50^{n - 1} - 1) + r_{n - 1} (50^{n - 2} - 1) + ... + r_{2} (50 - 1) + R, \end{matrix}

(1)

ahol

R = r_{n} + r_{n - 1} + ... + r_{1}

, a maradékok ‐ illetve a "számjegyek'' ‐ összege. Az (1) jobb oldalán álló összeg tagjaiban az

50^{i} - 1

tényező osztható

50 - 1 = 49

-cel, és így

7

-tel is, tehát az

A

valóban akkor és csak akkor osztható

7

-tel, ha

R = r_{n} + r_{n - 1} + ... + r_{2} + r_{1}

osztható vele.
Az eredmény és a bizonyítás a

3

-mal, illetve a

9

-cel való oszthatóság jól ismert szabályára emlékeztet. Általában, ha egy

m

számmal való oszthatóság eldöntésére keresünk hasonló eljárást, akkor az

m

bármely többszöröséhez

1

-et adva ‐

50 = 7 \cdot 7 + 1

‐ megfelelő osztót kapunk. A fentiekhez teljesen hasonlóan ugyanis ha

k > 0

tetszőleges egész, és

g = k m + 1

, akkor az

A

szám

g

alapú számrendszerbeli alakjának számjegyei éppen a feladatban leírt osztási eljárás során kapott maradékok. Most az

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

felírást kapjuk, és az állítás azon múlik, hogy

\begin{matrix} g^{i} - 1 = {(k m + 1)}^{i} - 1^{i} \end{matrix}

osztható

k \cdot m

-mel, az alapok különbségével, és így

m

-mel is.
Mivel valójában azt láttuk be, hogy

m | A - R,

ezért eredményünk kissé általánosabban úgy is fogalmazható, hogy tetszőleges

A

számból kiindulva az eljárás során kapott maradékok

R

összege és az

A

ugyanazt a maradékot adják

m

-mel osztva.
A

13

esetében tehát bármely

13 k + 1

alakú osztó megfelel, pl. a

40