Feladat: Pontversenyen kívüli P.93 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Bacsó G. ,  Balogh Z. ,  Bara T. ,  Bartolits I. ,  Ferró J. ,  Füredi Z. ,  Horváth M. ,  Lang I. ,  Móri T. ,  Petz D. ,  Reviczky J. ,  Rövid K. ,  Székely A. ,  Tarsó B. 
Füzet: 1971/november, 153 - 155. oldal  PDF  |  MathML 
Témakör(ök): Maradékos osztás, Prímszámok, Számtani sorozat, Pontversenyen kívüli probléma
Hivatkozás(ok):Feladatok: 1971/február: Pontversenyen kívüli P.93

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 a keresett számtani sorozat szomszédos tagjainak a különbségét d-vel. Ha d páratlan volna, akkor a sorozat minden második tagja páros volna, és a tagok nem lehetnének prímszámok. (Tagokként természetesen csak egész számokra gondolunk.) Tehát d osztható 2-vel. Ha d nem volna 3-mal osztható, akkor a sorozat három egymás utáni tagja közül az egyik mindig 3-mal osztható volna, tehát d a 3-mal is osztható. Hasonló módon látható be, hogy d osztható 5-tel is, és 7-tel is, vagyis d osztható 2⋅3⋅5⋅7=210-zel.
Annak érdekében, hogy lehetőleg kicsi (pozitív) számokkal dolgozzunk, d=210 különbségű sorozatot keresünk. A sorozat a kezdő tagjára szóba jövő prímeket növekvő rendben addig vizsgáljuk, míg olyat találunk, amelyre az (a+ +210i) tagok (0≤i≤9) mindegyike prím. Nyilvánvalóan a≥11.
Azt várjuk, hogy találunk olyan megoldást, melyben minden tag kisebb 2500-nál, ezért elég azt biztosítanunk, hogy a sorozat további tagjai (1≤i≤9) ne lehessenek oszthatók a 2500=50-nél kisebb prímek egyikével sem. Maga a kezdő tag is csak úgy lehet osztható ilyen prímmel, ha éppen egyenlő vele.
Kisebb számokon vizsgálódhatunk, ha az egymás utáni p értékek esetében a helyett az (a:p) osztás m maradékát tekintjük és ugyanígy d helyett a (210:p) osztás r maradékát, vagyis a=αp+m, 210=δp+r, ahol α, δ természetes számok, 0≤m<p és 0<r<p. Így a következő 10 számot tekintjük:

m,m+r,m+2r,...,m+9r,(1)
hiszen m+ri=(a+210i)-(α+δi)⋅p akkor és csak akkor osztható p-vel, ha (a+210i) osztható vele.
Mármost minden egyes fenti p-hez táblázatba gyűjtjük azokat az m értékeket, amelyek mellett (1) egyik tagja sem osztható p-vel. A 11≤p≤19 értékekre ezeket az alábbi táblázat tartalmazza. (A p≧23 esetekben rövidebb felírni a meg nem engedett m értékeket.) ‐ Pl. p=11 esetében r=1, és így m=1 még megfelelő, mert velük (1) az 1,2,...,10 számokból áll, viszont m≥2 esetén fellépne köztük 11-gyel osztható szám.
 


p  r  m  lehetséges értékei:11  1  0,  1;  13  2  0,2,4,6;  17  6  0,  6,  12,  1,  7,  13,  2,  8;  19  1  0,  1,  2,  3,  4,  5,  6,  7,  8,  9;p  r  m  nem megengedett értékei:  23  3  20,  17,  14,  11,  8,5,  2,  22,  19;  29  7  22,  15,  8,  1,  23,  16,  9,  2,  24;  31  24  7,  14,  21,  28,4,  11,  18,  25,  1;  37  25  12,  24,  36,  11,  23,  35,  10,  22,  34;  41  5  36,  31,  26,  21,  16,  11,  6,  1,  37;  43  38  5,  10,  15,  20,  25,  30,  35,  40,  42;  47  22  25,  3,  28,  6,  31,  9,  34,  12,  37.
 

Ezek alapján a sorozat kezdő száma nem lehet 11, mert ez p=13 mellett nem megengedett maradékot ad, nincs meg a 13-as sorban (másrészt megvan a 23-asban tilosként). A további keresés jelentősen egyszerűsödik, azt véve alapul, hogy a-t 11-gyel osztva csak 1-et kaphatunk maradékul. Az első ilyen prímszám a 23, de ez is p=13-ra nem megengedett maradékot ad. Hasonlóan a=67, 89 rendre a p=17, 13 prímekre nem megengedett maradékot ad, és 45, 111, 133, 155 és 177 nem prím. Az a=199 szám viszont a fenti prímekre rendre 1, 4, 12, 9, 15, 25, 13, 14, 35, 27, 11 maradékot ad, ezek mindegyike megengedett, és a=199 maga is prím, tehát az a=199 kezdő tagú, d=210 különbségű számtani sorozat első tíz tagja biztosan prímszám.
 

Megjegyzések. 1. Prím a sorozat elejére beiktatható (-11) is, de efféle problémákban pozitív számokra szokás szorítkozni.
2. Kevesebb meggondolással, felkészüléssel járna a fentiek alapján az 1+22k sorozat tagjait venni a-nak, ekkor viszont primitív, kilátástalan munkával egyenként kellene vizsgálni, hogy minden tag prím-e a sorozatokban.