Feladat: Pontversenyen kívüli P.124 Korcsoport: - Nehézségi fok: nehéz
Megoldó(k):  Hermann Péter ,  Oláh Vera ,  Szeredi János ,  Totik Vilmos 
Füzet: 1973/január, 27 - 28. oldal  PDF file
Témakör(ök): Legnagyobb közös osztó, Oszthatóság, Számsorozatok, Pontversenyen kívüli probléma
Hivatkozás(ok):Feladatok: 1971/december: Pontversenyen kívüli P.124

Bizonyítsuk be, hogy a
{2n-3}(n=2,3,4,...)(1)
sorozat tartalmaz olyan végtelen részsorozatot, amelynek bármely két eleme relatív prím.

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.

Jelöljük az adott sorozat 2n-3 elemét an-nel és egy, a követelménynek megfelelő részsorozat k-adik elemét bk-val. (Megjegyezzük, hogy a kívánt részsorozat elemeinek összeállítása többféleképpen lehetséges.) Azt fogjuk megmutatni, hogy ha már találtunk a részsorozat céljára k számú megfelelő elemet, és ezek b1,b2,...,bk, akkor találhatunk hozzájuk olyan bk+1-et, amely amazok mindegyikéhez relatív prím (és nagyobb náluk). Egyszerűbben így mondhatjuk a talált követelményt:

bk+1és ab1b2...bk
szorzat relatív prímek.
b1 és b2 szerepére megfelel mindjárt b1=a3=5, b2=a4=13. Így a b1b2=s2 szorzathoz relatív prím, nála nagyobb an-et keresünk b3 szerepére. Azt a kizáró követelményt, hogy (2n-3)-nak ne legyen közös osztója s2-vel, azzal fogjuk biztosítani, hogy a (2n-3) közelében levő cn=an+2=2n-1 szám legyen többszöröse s2-nek. Ha ugyanis ez teljesül, akkor an és s2 bármely közös osztója egyszersmind an-nek és cn-nek is közös osztója, tehát osztója ezek különbségének, a 2-nek is. Így, ha ez a közös osztó nagyobb volna 1-nél, akkor csak 2-vel lehetne egyenlő. Ámde an és cn páratlan volta miatt ez lehetetlen, tehát an és s2 valóban relatív prímek. ‐ Ilyen feltétellel sikerül an-et találnunk.
Tekintsük az an sorozat első (s2+1) számú eleméhez, vagyis az a2,a3,..., a3+s2 számokhoz azokat a (legkisebb nemnegatív) r maradékokat, amelyek az s2-vel való osztásuknál rendre föllépnek. Így 0rs2-1, a lehetséges különböző maradékok száma s2. A tekintetbe vett elemek száma pedig 1-gyel több, van tehát legalább kettő az elemek közt, amelyekre a maradék egyenlő. Jelöljük ezeket (vagy ha több van, két ilyet) at-vel és au-val (u>t), eszerint
au-at=2u-2t=2t(2u-t-1),
osztható s2-vel; és mivel s2 páratlan, azért a zárójelbeli tényezőnek osztója: 2u-1-1=ds2, ahol d természetes szám. Így pedig az előrebocsátottak szerint ds2-2=2u-t-3=au-t-nek nincs közös osztója s2-vel, tehát lehet b3=au-t.
Eljárásunk alkalmas b1,b2,...,bk-hoz megfelelő bk+1 keresésére is, s2 helyére a b1b2...bk=sk szorzatot véve, hiszen az s2-re mondottak érvényesek sk-ra is és nem használtuk ki, hogy s2-ben éppen 2 elemét szoroztuk össze a részsorozatnak. ‐ Ezzel feladatunkat megoldottuk.
 

Megjegyzések. 1. Vehettük volna b3 szerepére a következőket is:
2ds2-1=2u-t+1-3=au-t+1,4ds2+1=2u-t+2-3=au-t+2,
hiszen két szomszédos természetes szám mindig relatív prím egymáshoz, és ha 2cs2 nek, ill. 4cs2-nek nincs közös osztója b3-mal, akkor s2-nek sincs.
2. Szemléletesen szólva: annak, hogy az an sorozatra igaz a feladat állítása, hogy tehát az an sorozatban ,,sok'' relatív prím szám van, az az oka, hogy cn=an+2 sorozatban ,,sok'' nem relatív prím számpár van. Az utóbbi állítás pontos alakja a következő: tetszőleges páratlan s számhoz van olyan n index, hogy cn osztható s-sel.