Kezdőlap


Feladat:	Pontversenyen kívüli P.9	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Beck József , Göndőcs Ferenc , Martoni Viktor , Somorjai Gábor
Füzet:	1969/április, 168 - 170. oldal		PDF \| MathML
Témakör(ök):	"a" alapú számrendszer (a >1, egész szám), Pontversenyen kívüli probléma
Hivatkozás(ok):	Feladatok: 1968/november: Pontversenyen kívüli P.9

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.

Az $a$ alapú számrendszer számjegyei:

\begin{matrix} 0,1,2, ..., a - 1. \end{matrix}

(1)

Ezek közül csak azok jöhetnek tekintetbe, amelyek négyzete velük megegyező számjegyre végződik. Megmutatjuk, hogy az ilyen jegyek mind meg is felelnek: az ilyenre végződő számok minden hatványa ugyanarra a jegyre végződik.
Legyen egy ilyen jegy

b

, vagyis a

\begin{matrix} b^{2} - b = b (b - 1) \end{matrix}

(2)

különbség

0

-ra végződik, osztható

a

-val. Másrészt a

B

szám

a

-alapú számrendszerbeli alakja végződjék

b

-re, vagyis

B - b

is osztható

a

-val. Azt akarjuk megmutatni, hogy ekkor minden

k

természetes számra

B^{k}

, is

b

-re végződik, azaz

B^{k} - b

is osztható

a

-val. Hogy a második feltételt kihasználhassuk, vonjunk le a különbségből és adjunk is hozzá

b^{k}

-t:

\begin{matrix} B^{k} - b = B^{k} - b^{k} + b^{k} - b = (B - b) (B^{k - 1} + B^{k - 2} b + ... + B b^{k - 2} + b^{k - 1}) + \\ + b (b^{k - 1} - 1) = (B - b) (B^{k - 1} + B^{k - 2} b + ... + B b^{k - 2} + b^{k - 1}) + \\ + b (b - 1) (b^{k - 2} + ... + b + 1), \end{matrix}

és ez a feltételek szerint valóban osztható

a

-val.
Elegendő tehát azokat a

b

számjegyeket megkeresni, amelyekre a (2) alatti szám osztható

a

-val. A bal oldal két tényezőjének legnagyobb közös osztója a különbségüknek is osztója, ez viszont

1

, tehát

b

és

b - 1

relatív prímek
Legyen

a

és

b

legnagyobb közös osztója

a_{1}

, az

a

b - 1

számpáré

a_{2}

. Ezek szintén relatív prímek ‐ hiszen (az egységnél nagyobb) közös osztójuk a

b

b - 1

számpárnak is közös osztója lenne ‐, ezért az

a_{1} a_{2}

szorzat osztója

a

-nak.
Fordítva,

a

is osztója

a_{1} a_{2}

-nek, tehát

\begin{matrix} a_{1} a_{2} = a . \end{matrix}

(3)

Valóban, legyen az

a

alapszám törzstényezős felbontása

\begin{matrix} a = p_{1}^{α_{1}} p_{2}^{α_{2}} ... p_{k}^{α_{k}} . \end{matrix}

(4)

Ennek minden

p_{i}^{α_{i}}

alakú osztója

(i = 1,2, ..., k)

a fentiek szerint vagy

b

-nek, vagy

b - 1

-nek osztója (de csak az egyiküknek); ezért az első esetben

a_{1}

-nek osztója a

p_{i}^{α_{i}}

hatvány, a másodikban

a_{2}

-nek, így pedig mindenesetre osztója az

a_{1} a_{2}

szorzatnak.

i \neq j

esetlen

p_{i}^{α_{i}}

és

p_{j}^{α_{j}}

relatív prímek, ezért az

a_{1} a_{2}

szorzat osztható a (4) jobb oldalán álló szorzattal, vagyis

a

-val, amint állítottuk.
Ezen az úton minden megfelelő

b

számjegyhez hozzárendeltük az

a

szám egy (3) alakú felbontását két tényezős szorzatra. Megmutatjuk, hogy minden, ilyen felbontáshoz egyértelműen tartozik egy

b

számjegy.
Ehhez meg kell keresnünk az

a_{1}

számnak azt a

\begin{matrix} b = a_{1} m \end{matrix}

a

-nál kisebb többszörösét, amelyre

b - 1

osztható

a_{2}

-vel, azaz amelyet

a_{2}

-vel osztva a maradék

1

Osszuk a

\begin{matrix} 0, 1 \cdot a_{1}, 2 \cdot a_{1}, ..., (a_{2} - 1) \cdot a_{1} \end{matrix}

(5)

számokat

a_{2}

-vel. Nem lehet, hogy ennek során kétszer ugyanazt a maradékot kapjuk, hiszen ilyen esetben ennek a két többszörösnek,

i a_{1}

-nek és különbsége,

j a_{1}

-nek,

(i < j)

különbsége,

(j - i) a_{1}

osztható volna

a_{2}

-vel. Azonban

a_{1}

és

a_{2}

relatív prímek, ezért a szorzat csak úgy lehetne

a_{2}

-vel osztható, ha

(j - i)

osztható volna

a_{2}

-vel. Ámde

0 ≦ i < j < a_{2}

, így

0 < j - i < a_{2}

, ezért

j - i

sem osztható

a_{2}

-vel, tehát az (5) alatti számok mondott osztási maradékai mind különbözők.
Az (5) alatt felsorolt többszörösök száma

a_{2}

. Másrészt az

a_{2}

-vel végzett osztás maradékai

\begin{matrix} 0, 1, 2, ..., a_{2} - 1 \end{matrix}

(6)

számok lehetnek, tehát a lehetséges maradékok száma is

a_{2}

, így az (5) számok maradékai között minden maradék pontosan egyszer fordul elő. Nevezetesen az

1

maradék is egyszer fordul elő, tehát a választott (3) alakú felbontáshoz valóban egyértelműen hozzátartozik egy (2) alakú szorzat.
Ezek szerint feladatunk megoldásainak a száma egyenlő a (3) alakú felbontások számával. Egy (3) alakú felbontásban az

a

szám minden törzstényezője vagy

a_{1}

, vagy pedig

a_{2}

osztója. A felbontásokat tehát úgy kapjuk meg, hogy a (4) alatti törzstényezőket két csoportba osztjuk. Ismeretes, hogy

k

különböző elemet

2^{k}

-féleképpen oszthatunk két csoportba, feladatunk megoldásainak száma tehát

2^{k}

, ahol

k

a

szám törzstényezőinek a száma. (Ebben természetesen benne van a

b = 0

, és a

b = 1

triviális megoldás is;

b = 0

a_{1} = 1

a_{2} = a

felbontásból,

b = 1

pedig az

a_{1} = a

a_{2} = 1

felbontásból.)
Pl.

a = 105 = 3 \cdot 5 \cdot 7

esetén

k = 3

, a felbontások száma

2^{k} = 8

, és a megfelelő számjegyek:

b = 0, 1, 15, 21, 36, 70, 85, 91.

‐ Példát láttunk az 1222. gyakorlatban is¹.

Martoni Viktor

¹K. M. L. 38 (1969) 113. o.