|
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 -re vonatkozó teljes indukcióval igazoljuk. esetben , és relatív prímek. Ekkor többszörösei teljes maradékrendszert alkotnak szerint, vagyis tetszőleges számhoz létezik olyan , amelyre: Így minden -nál nagyobb számot elő lehet állítani a kívánt alakban: legyen a maradéka -vel osztva. A -hoz találunk -nél kisebb -t úgy, hogy Ekkor osztható -vel, legyen a hányados , így , ahol és . Ezzel -re igazoltuk az állítást. Tegyük fel, hogy valamilyen -re, esetén az állítás igaz. Megmutatjuk, hogy ekkor esetén is igaz. Legyen az , , , számok legnagyobb közös osztója . Az indukciós feltétel szerint az , , , számokkal véges sok kivétellel minden pozitív egesz szám felírható a kérdéses alakban. Így létezik olyan , hogy: és , ahol , , , nemnegatív egész. Mivel és relatív prímek (különben az , , , , számoknak lenne közös osztója), és is relatív prímek. Az előbb beláttuk, hogy a feladat állítása esetén igaz, azaz véges sok kivétellel minden pozitív egész szám felírható alakban, azaz alakban, ahol , , , , , nemnegatív egészek. Ezzel a feladat állítását igazoltuk.
Terék Zsolt (Fazekas M. Főv. Gyak. Gimn., III. o.t.) |
|
|