Kezdőlap


Feladat:	256. matematika feladat	Korcsoport: 16-17	Nehézségi fok: nehéz
Füzet:	1951/november, 129. oldal		PDF \| MathML
Témakör(ök):	Euler-féle számelméleti függvény, Feladat
Hivatkozás(ok):	Feladatok: 1951/március: 256. matematika feladat

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.

Írjuk az 1-től $a b$ -ig terjedő számokat a következő táblázatba:

\begin{matrix} \begin{matrix} 1, & 2, & . . ., & a, \\ a + 1, & a + 2, & . . ., & 2 a, \\ 2 a + 1, & 2 a + 2, & . . ., & 3 a, \\ . . . & . . . . . . . & . \\ . . . & . . . . . . . & . \\ (b - 1) a + 1, & (b - 1) a + 2, & . . ., & b a . \end{matrix} \end{matrix}

Nézzük, hogyan helyezkednek el az

a

-hoz relatív prímszámok. Tekintsük a

k

-adik oszlopot:

k

a + k

2 a + k

...

(b - 1) a + k

Ezek nyilván mind relatív prímek, vagy mind nem relatív prímek

a

-hoz, attól függően, hogy

k

relatív prím-e

a

-hoz, vagy nem. Látjuk tehát, hogy az

a

-hoz relatív prímszámok

φ (a)

számú oszlopban helyezkednek el.
Most vizsgáljuk a

b

-hez relatív prímszámok elhelyezkedését. Mint a cikkben beláttuk, egy szám akkor és csak akkor relatív prím

b

-hez, ha

b

-vel osztva,

b

-hez relatív prím maradékot ad. Másrészt könnyen beláthatjuk, hogy ugyanabban az oszlopban álló két szám

b

-vel osztva nem adhatja ugyanazt a maradékot.

Ugyanis, ha

\begin{matrix} k + n_{1} a = q_{1} b + r \\ k + n_{2} a = q_{2} b + r volna, \end{matrix}

akkor

(n_{1} - n_{2}) a = (q_{1} - q_{2}) b

vagyis

(n_{1} - n_{2}) a

osztható volna

b

-vel, de mivel

a

és

b

relatív prímek, ebből következnék, hogy

(n_{1} - n_{2})

osztható

b

-vel. Ez azonban lehetetlen, mert

n_{1}

és

n_{2}

b

-nél kisebb pozitív számok s így különbségük is

b

-nél kisebb.
Tehát az egy oszlopban álló

b

számú szám

b

-vel osztva különböző maradékokat ad, s így a maradékok az összes számok 1-től

b

-ig. Mivel ezek között

φ (b)

darab

b

-hez relatív prímszám van, az előbbiek szerint minden oszlopban

φ (b)

számú

b

-hez relatív prímszám van; a

φ (a)

számú

a

-hoz relatív prímszámokat tartalmazó oszlopban tehát összesen

φ (a)

φ (b)

számú

a b

-hez relatív prímszám van. Ezzel a tételt bebizonyítottuk.