Feladat: 1075. matematika gyakorlat Korcsoport: 14-15 Nehézségi fok: átlagos
Megoldó(k):  Fodor Zsuzsa 
Füzet: 1967/április, 171. oldal  PDF  |  MathML 
Témakör(ök): Kombinatorikai leszámolási problémák, Oszthatósági feladatok, Prímszámok, Gyakorlat
Hivatkozás(ok):Feladatok: 1966/október: 1075. matematika gyakorlat

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.

Csak azok a sorrendek jönnek szóba, amelyek 1-re vagy 3-ra végződnek, különben a szám osztható 2-vel, nem törzsszám. Mindkétféle végződés előtt 3⋅2=6 féle sorrend lehetséges, a maradó három jegyből az első helyet 3-féleképpen tölthetjük be, minden ilyen kezdés után a másik 2 jegyet még kétféle sorrendben írhatjuk le. A vizsgálandó 12 szám:

  I. 2341,    II. 2431,    III. 3241,    IV. 3421,    V. 4231,    VI. 4321;  VII. 1243,    VIII. 1423,    IX. 2143,    X. 2413,    XI. 4123,    XII. 4213.

A számokat sorra osztjuk az egymás utáni prímszámokkal. Amelyik szám valamelyik osztásban 0 maradékot ad (és persze a hányados nagyobb 1-nél), azt töröljük, mert nem prímszám.
A II., IV., VII. és XII. szám osztható 11-gyel, mert pl. az elsőben (1+4)-(3+2)=0, ami osztható 11-gyel.1 A próba szerint a III. és a XI. szám osztható 7-tel, a X. szám 19-cel, és a VI. szám 29-cel. 2341-et az egymás utáni
3,5,7,11,13,17,19,23,29,31,37,41,43,47
páratlan prímszámokkal osztva minden esetben maradék lép föl, tehát 2341 prímszám. Nagyobb prímszámmal ugyanis már fölösleges próbálkozni, mert ha pl. 53 osztója volna 2341-nek, akkor a 2341:53=q hányados egész szám volna, éspedig 53-nál kisebb, hiszen 53q=2341<2809=532, amit 53-mal osztva q<53. Így pedig q nem lehetne prímszám a végzett osztási próbák miatt, de összetett szám sem, mert akkor lenne prímszám-osztója a fenti felsorolásban. Hasonlóan nem osztható 2341 a nála kisebb és 47-nél nagyobb prímszámok egyikével sem. A 47-tel való próba viszont még szükséges volt, mert 472=2209<2341.
Általában, egy szám prímfelbontását keresve elég azokkal a prímekkel próbálkozni, amelyeknek a négyzete nem nagyobb a számnál. Valóban, ha n összetett szám: n=a⋅b, és itt 1<ab≦b, akkor n=ab≧a2, a≦n, így vagy a, vagy a-nak prímosztója n-nek is prímosztója.
Ennek alapján a 4231 számnak a 61-ig, 1423-nak a 37-ig és 2143-nak a 43-ig terjedő prímekkel való és minden esetben maradékkal végződő osztási próbája után kimondható, hogy az illető szám prímszám.
Mindezek szerint a kérdéses számok között 4 prímszám van.
 
 Fodor Zsuzsa (Pápa, Türr I. g. I. o. t.)
1Egy természetes szám akkor és csak akkor osztható 11-gyel, ha a (jobbról számítva) páratlan sorszámú helyeken álló számjegyeinek összegéből kivonva a páros sorszámú helyeken álló számjegyeinek összegét, 11-gyel osztható számot kapunk.