Feladat: B.3693 Korcsoport: 16-17 Nehézségi fok: könnyű
Megoldó(k):  Bogya Norbert 
Füzet: 2005/március, 151. oldal  PDF file
Témakör(ök): Oszthatóság, Prímszámok, Feladat
Hivatkozás(ok):Feladatok: 2004/január: B.3693

A pozitív egész k számot a p prímszámmal osztva a maradék 6. Ugyanennyi maradékot kapunk akkor is, ha az 1000-k számot osztjuk p-vel; tudjuk ezenkívül, hogy 10000-k osztható p-vel. Melyik ez a p prímszám?

Megoldás. Írjuk fel a maradékos osztásokat:
k=xp+6,(1)1000-k=yp+6,(2)10000-k=zp,(3)
ahol x, y, z nemnegatív egész számok. Az első két egyenlet különbségét vonjuk ki a harmadik egyenlet kétszereséből:
(20000-2k)-(1000-2k)=2zp-(yp+6-xp-6),19000=2zp+(x-y)p,19000=(x-y+2z)p,
vagyis p19000. De 19000=235319 és mivel a p-vel való osztás maradékaként föllépett a 6, így ez a prím annál csak nagyobb lehet, vagyis az egyetlen lehetséges prím a p=19. Ha például k=500, akkor valamennyi feltétel teljesül, így p=19.