Feladat: 1283. matematika feladat Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Földesi Tamás ,  Harsányi János ,  Holzer Pál ,  Hörcher J. ,  ifj. Jankovich I. ,  Jakab Károly ,  Kolostori J. ,  Mandl Béla ,  Radovics György ,  Seidl Gábor ,  Vajda József 
Füzet: 1937/március, 205 - 206. oldal  PDF  |  MathML 
Témakör(ök): Maradékos osztás, Legkisebb közös többszörös, Oszthatóság, Feladat
Hivatkozás(ok):Feladatok: 1937/január: 1283. matematika feladat

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 törzsszámok természetes sorrendje p-ig

p1,p2,...,pr,p.
Jelölje αk azon kitevőt, amellyel pkαk<p<pkαk+1.
Az ilyen módon meghatározott αk kitevőkkel képezzük a
P=p1α1p2α2...prαr
szorzatot. Ekkor lP, ahol l=1,2,3,..., osztható a p-nél kisebb bármely n számmal, tehát lP±1 az n-nel osztva maradékul 1-et, ill. n-1-et ad.
Ha már most P=pQ+r, ahol 0<r<p, akkor véges számú próba után1 megtaláljuk l azon legkisebb pozitív értékét, amellyel már lr+1p ill. lr-1p egész szám; azonban utóbbi lehet zérus is.
Ha l ezen legkisebb értéke λ1, ill. λ2, akkor N1=λ1P+1 azon legkisebb szám, mely p-vel osztható, de a p-nél kisebb n számmal osztva, a maradék 1, míg N2=λ2P-1 azon legkisebb szám, mely p-vel osztható, de a p-nél kisebb n számmal osztva, a maradék n-1.
Pl. p=11 esetben a p-nél kisebb törzsszámok 2,3,5,7 és
P=23⋅32⋅5⋅7=2520.
Már most 2520=229⋅11+1, azaz r=1. Nyilván
λ1=10ésλ2=1
úgy, hogy
N1=25201ésN2=2519.
25201:11=2291; bármely 11-nél kisebb számmal osztva N1-et, a maradék +1.
2519:11=229; bármely 11-nél kisebb n számmal osztva N2-t, a maradék n-1.
 
Harsányi János (Ág. ev. g. VIII. o. Bp.).

 

I. Jegyzet. A P szám nem más, mint a p-nél kisebb számok legkisebb közös többszöröse.
 

II. Jegyzet. Pl. p=7 esetében P=22⋅3⋅5=60.
Azonban
60=8⋅7+4,azazr=4.
Nyilván 2⋅4-1=7, azaz λ2=2 és N2=2⋅60-1=119 azon legkisebb szám, mely 7-tel osztható, de a 7-nél kisebb n számmal osztva, a maradék n-1.
Másrészt 5⋅4+1=21 a legkisebb az lr+1 alakú számok sorában mely 7-tel osztható, úgy, hogy N1=5⋅10+1=301 azon legkisebb szám, mely 7-tel osztható, de a 7-nél kisebb n számmal osztva, a maradék 1.
1A próbák száma<p; vagy keresnünk kell az rx±1=py határozatlan egyenletek legkisebb poz. egész megoldásait (ill. rx-1=py esetében y=0 is lehet).