Feladat:	B.4493	Korcsoport: 18-	Nehézségi fok: átlagos
Megoldó(k):	Demeter Dániel
Füzet:	2013/november, 478 - 479. oldal		PDF  |  MathML
Témakör(ök):	Feladat, Legnagyobb közös osztó, Legkisebb közös többszörös, Prímtényezős felbontás, Konstruktív megoldási módszer
Hivatkozás(ok):	Feladatok: 2012/december: B.4493

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. Az $a$, $b$, $c$ számok (módosított) kanonikus alakja: $\begin{array}{c}{\displaystyle a=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\text{...}{p}_r^{{\alpha }_r}\mathrm{,}b=p_1^{{\beta }_1}{p}_2^{{\beta }_2}\text{...}{p}_r^{{\beta }_r}\mathrm{,}c=p_1^{{\gamma }_1}{p}_2^{{\gamma }_2}\text{...}{p}_r^{{\gamma }_r}\mathrm{.}}\end{array}$ A módosított kanonikus alakon azt értjük, hogy mindhárom szám ugyanazokat a prímeket tartalmazza úgy, hogy amelyik ténylegesen nem szerepelne a felbontásban, azt $0$ kitevővel vesszük be a szorzatba. Ezzel elérjük, hogy a számok egységesen kezelhetők. Jelöljük a $p_i$ prímhez tartozó kitevők közül a legkisebbet $\underset{}{\overset{}{\text{min}}}\left(i\right)$-vel, a középsőt $\text{med}\left(i\right)$-vel, a legnagyobbat pedig $\underset{}{\overset{}{\text{max}}}\left(i\right)$-vel. Világos, hogy $\underset{}{\overset{}{\text{min}}}\left(i\right)\le \text{med}\left(i\right)\le \underset{}{\overset{}{\text{max}}}\left(i\right)$. Ismert, hogy a legnagyobb közös osztóban mindegyik prím az előforduló legkisebb kitevőn, míg a legkisebb közös többszörösben az előforduló legnagyobb kitevőn szerepel. (Természetesen ebben az egységes jelölésben.) A páronkénti legnagyobb közös osztó meghatározásakor tetszőleges $p_i$ prím esetében megmarad a legkisebb kitevő kétszer és a középső egyszer. Ha ennek a háromnak vesszük a maximumát, akkor éppen $\text{med}\left(i\right)$-t kapjuk. Vegyük most páronként a legkisebb közös többszörös kitevőit a $p_i$ prím esetében. Itt a legnagyobb marad meg kétszer és a középső egyszer. Ha vesszük a három pár legnagyobb közös osztóját, akkor ott e három közül a legkisebbet kell vennünk, vagyis a középsőt $\text{med}\left(i\right)$-t. Az elmondottak tetszőleges $p_i$ hatványaira igazak, vagyis $\begin{array}{c}{\displaystyle \left[\left(a\mathrm{,}b\right)\mathrm{,}\left(b\mathrm{,}c\right)\mathrm{,}\left(c\mathrm{,}a\right)\right]=\left(\left[a\mathrm{,}b\right]\mathrm{,}\left[b\mathrm{,}c\right]\mathrm{,}\left[c\mathrm{,}a\right]\right)}\end{array}$ valóban teljesül.