Kezdőlap


Feladat:	A.217	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Ambrus Gergely , Gyenes Zoltán , Harangi Viktor , Kiss Zoltán , Kunszenti-Kovács Dávid , Pálvölgyi Dömötör , Varjú Péter , Zábrádi Gergely
Füzet:	2000/február, 100 - 101. oldal		PDF \| MathML
Témakör(ök):	Legnagyobb közös osztó, Legkisebb közös többszörös, Nehéz feladat
Hivatkozás(ok):	Feladatok: 1999/szeptember: A.217

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.

Legyen $M$ az a szám, amely előáll bármelyik két $a_{i}$ legkisebb közös többszöröseként, és legyen $b_{i} = \frac{M}{a_{i}}$ . A $b_{1}$ , $...$ , $b_{n}$ számok páronként relatív prímek, mert $i \neq j$ esetén

\begin{matrix} (b_{i}, b_{j}) = (\frac{M}{a_{i}}, \frac{M}{a_{j}}) = \frac{M}{[a_{i}, a_{j}]} = \frac{M}{M} = 1. \end{matrix}

M

mindegyik

b_{i}

-nek többszöröse, ezért többszöröse a szorzatuknak is. Tehát

M = c b_{1} b_{2} ... b_{n}

egy alkalmas

c

pozitív egésszel, és

a_{i} = \frac{M}{b_{i}} = c b_{1} ... b_{i - 1} b_{i + 1} ... b_{n}

. Az

a_{1}

...

a_{n}

számok legnagyobb közös osztója

\begin{matrix} (a_{1}, ..., a_{n}) = (\frac{M}{b_{1}}, ..., \frac{M}{b_{n}}) = \frac{M}{[b_{1}, ..., b_{n}]} = \frac{M}{b_{1} ... b_{n}} = c, \end{matrix}

ezért

c = 1

.
Tehát az

a_{1}

...

a_{n}

számokra vonatkozó feltételek azzal ekvivalensek, hogy megfelelő, páronként relatív prím

b_{1}

...

b_{n}

pozitív egészekkel

a_{i} = b_{1} ... b_{i - 1} b_{i + 1} ... b_{n}

.
Legyen

u

tetszőleges egész szám, és tegyük fel, hogy felírható a kívánt alakban:

\begin{matrix} a_{1} x_{1} + ... + a_{n} x_{n} = u . \end{matrix}

Vizsgáljuk ezt az egyenletet modulo

b_{i}

. A bal oldalon

a_{i}

kivételével az összes együttható osztható

b_{i}

-vel, ezért

\begin{matrix} a_{i} x_{i} = (b_{1} ... b_{i - 1} b_{i + 1} ... b_{n}) x_{i} \equiv u (mod b_{i}) . \end{matrix}

Legyen

ξ_{i} (u)

a legkisebb olyan nemnegatív egész, amelyre

\begin{matrix} (b_{1} ... b_{i - 1} b_{i + 1} ... b_{n}) ξ_{i} (u) \equiv u (mod b_{i}) . \end{matrix}

Az előbbiek alapján, figyelembe véve, hogy

b_{i}

relatív prím

(b_{1} ... b_{i - 1} b_{i + 1} ... b_{n})

-nel,

\begin{matrix} x_{i} \equiv ξ_{i} (u) (mod b_{i}), \end{matrix}

másrészt,

ξ_{i} (u)

minimalitása miatt

x_{i} \geq ξ_{i} (u)

. Bevezetve az

y_{i} = \frac{x_{i} - ξ_{i} (u)}{b_{i}}

jelölést,

\begin{matrix} \frac{u - a_{1} ξ_{1} (u) - ... - a_{n} ξ_{n} (u)}{b_{1} ... b_{n}} = y_{1} + ... + y_{n} \end{matrix}

egy nemnegatív egész szám.
Vezessük be a

\begin{matrix} h (u) = \frac{u - a_{1} ξ_{1} (u) - ... - a_{n} ξ_{n} (u)}{b_{1} b_{2} ... b_{n}} \end{matrix}

(2)

függvényt. Eddig azt láttuk, hogy ha

u

előállítható, akkor

h (u)

egy nemnegatív egész szám. Az is biztos, hogy

h (u)

mindig egész, mert (2) számlálójában tetszőleges

i

-re

u - a_{i} ξ_{i} (u)

osztható

b_{i}

-vel, a maradék tagokban pedig az

a_{j}

együttható osztható vele. Ha a

h (u)

egész szám nemnegatív, akkor

u

egy megfelelő előállítását kapjuk az

x_{1} = ξ_{1} (u) + h (u) b_{1}

x_{2} = ξ_{2} (u)

...

x_{n} = ξ_{n} (u)

számokkal.
Ezzel bebizonyítottuk, hogy

u

akkor és csak akkor állítható elő, ha

h (u) \geq 0

.
Bebizonyítjuk, hogy a feladat állításának megfelelő szám

\begin{matrix} p = (n - 1) b_{1} b_{2} ... b_{n} - a_{1} - ... - a_{n} . \end{matrix}

(1)

Vizsgáljuk az

u

és

p - u

számokat. Tetszőleges

i

-re

\begin{matrix} a_{i} ξ_{i} (u) + a_{i} ξ_{i} (p - u) \equiv p \equiv - a_{i} (mod b_{i}), \end{matrix}

amiből ‐ mivel

a_{i}

és

b_{i}

relatív prímek ‐

\begin{matrix} ξ_{i} (u) + ξ_{i} (p - u) \equiv - 1 (mod b_{i}) . \end{matrix}

(3)

Mivel

ξ_{i}

értéke mindig

0

és

b_{i} - 1

közé esik, (3) csak úgy teljesülhet, ha

ξ_{i} (u) + ξ_{i} (p - u) = b_{i} - 1

. Ezt beírva

h (u)

-ba és

h (p - u)

-ba,

\begin{matrix} \begin{matrix} h (u) + h (p - u) = \frac{u - a_{1} ξ_{1} (u) - ... - a_{n} ξ_{n} (u) + (p - u) - a_{1} ξ_{1} (p - u) - ... - a_{n} ξ_{n} (p - u)}{b_{1} b_{2} ... b_{n}} = \\ = \frac{p - a_{1} (ξ_{1} (u) + ξ_{1} (p - u)) - ... - a_{n} (ξ_{n} (u) + ξ_{n} (p - u))}{b_{1} b_{2} ... b_{n}} = \\ = \frac{((n - 1) b_{1} b_{2} ... b_{n} - a_{1} - ... - a_{n}) - a_{1} (b_{1} - 1) - ... - a_{n} (b_{n} - 1)}{b_{1} b_{2} ... b_{n}} = - 1. \end{matrix} \end{matrix}

Ebből következik, hogy a

h (u)

és

h (p - u)

egész számok közül pontosan az egyik nemnegatív, azaz

u

és

p - u

közül pontosan az egyik állítható elő.