Feladat: F.2225 Korcsoport: 14-15 Nehézségi fok: nehéz
Füzet: 1980/március, 113. oldal  PDF file
Témakör(ök): Indirekt bizonyítási mód, Prímszámok, Feladat
Hivatkozás(ok):Feladatok: 1979/november: F.2225

Adott 1 és (2n-1)2 között n darab, páronként relatív prím egész. Mutassuk meg, hogy a megadott számok között van prímszám is.

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 feladatot reductio ad absurdum módszerével oldjuk meg, azaz feltesszük, hogy az állítás nem igaz és ellentmondásra jutunk belőle.
Legyenek tehát megadott számaink a1, a2, ..., an, ahol 1<ai<(2n-1)2, és legyen ai legkisebb prímosztója pi. Mivel ai nem prímszám, van pi-n kívül még (esetleg pi-vel megegyező) prímosztója, következésképp pi2ai<(2n-1)2. Az így kapott pi prímszámok mind különbözők, hiszen ha pi-pj volna, akkor pi osztója volna ai-nek és aj-nek is, noha feltételünk szerint ai és aj relatív prím.
Így kaptunk n különböző prímszámot, melyek mindegyike kisebb (2n-1)-nél. Megmutatjuk, hogy ez lehetetlen. Ugyanis 1 és (2n-1) között (n-2) páratlan szám van (3, 5, 7, ..., 2n-3) és minden prímszám, a 2-t kivéve, páratlan. Tehát 1 és (2n-1) között legfeljebb (n-1) különböző prímszám található, ami ellentmondás.
Ez az ellentmondás igazolja állításunkat.