Kezdőlap


Feladat:	F.3136	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Bérczi Gergely , Devecsery András , Felföldi Zsolt , Gyenes Zoltán , Hangya Balázs , Juhász András , Katona Zsolt , Méder Áron , Nyul Gábor , Patakfalvi Zsolt , Pogány Ádám , Rudolf Gábor , Terék Zsolt , Terpai Tamás , Tóth Ádám , Várkonyi Péter , Végh László , Zábrádi Gergely
Füzet:	1997/március, 165. oldal		PDF \| MathML
Témakör(ök):	Legnagyobb közös osztó, Teljes indukció módszere, Maradékos osztás, Oszthatósági feladatok, Prímszámok, Feladat
Hivatkozás(ok):	Feladatok: 1996/október: F.3136

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.

A feladat állítását $n$ -re vonatkozó teljes indukcióval igazoljuk.
$n = 2$ esetben $p = a_{1}$ , és $q = a_{2}$ relatív prímek. Ekkor $q$ többszörösei teljes maradékrendszert alkotnak $p$ szerint, vagyis tetszőleges $0 \leq k < p$ számhoz létezik olyan $0 \leq j < p$ , amelyre:

\begin{matrix} j \cdot q \equiv k (mod p) . \end{matrix}

Így minden

p q

-nál nagyobb

z

számot elő lehet állítani a kívánt alakban: legyen

k

z

maradéka

p

-vel osztva. A

k

-hoz találunk

p

-nél kisebb

j

-t úgy, hogy

\begin{matrix} j \cdot q \equiv k (mod p) . \end{matrix}

Ekkor

z - j q

osztható

p

-vel, legyen a hányados

l

, így

z = j q + l p

, ahol

j \geq 0

és

l \geq 0

. Ezzel

n = 2

-re igazoltuk az állítást.
Tegyük fel, hogy valamilyen

m

-re,

n \leq m

esetén az állítás igaz. Megmutatjuk, hogy ekkor

n = m + 1

esetén is igaz.
Legyen az

a_{1}

a_{2}

...

a_{m}

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

d

. Az indukciós feltétel szerint az

\frac{a_{1}}{d}

\frac{a_{2}}{d}

...

\frac{a_{m}}{d}

számokkal véges sok kivétellel minden pozitív egesz szám felírható a kérdéses alakban. Így létezik olyan

u

, hogy:

(u, a_{m + 1}) = 1

és

\frac{a_{1}}{d} v_{1} + \frac{a_{2}}{d} v_{2} + ... + \frac{a_{m}}{d} v_{m} = u

, ahol

v_{1}

v_{2}

...

v_{m}

nemnegatív egész.
Mivel

d

és

a_{m + 1}

relatív prímek (különben az

a_{1}

a_{2}

a_{3}

...

a_{m + 1}

számoknak lenne közös osztója),

u d

és

a_{m + 1}

is relatív prímek. Az előbb beláttuk, hogy a feladat állítása

n = 2

esetén igaz, azaz véges sok kivétellel minden pozitív egész szám felírható

\begin{matrix} x_{1} d u + x_{2} a_{m + 1} \end{matrix}

alakban, azaz

x_{1} v_{1} a_{1} + x_{1} v_{2} a_{2} + x_{1} v_{3} a_{3} + ... + x_{1} v_{m} a_{m} + x_{2} a_{m + 1}

alakban, ahol

x_{1} v_{1}

x_{1} v_{2}

x_{1} v_{3}

...

x_{1} v_{m}

x_{2}

nemnegatív egészek.
Ezzel a feladat állítását igazoltuk.

Terék Zsolt (Fazekas M. Főv. Gyak. Gimn., III. o.t.)