Feladat: C.210 Korcsoport: 14-15 Nehézségi fok: átlagos
Megoldó(k):  Parlagh Ildikó 
Füzet: 1990/október, 311 - 312. oldal  PDF  |  MathML 
Témakör(ök): Indirekt bizonyítási mód, Oszthatósági feladatok, Oszthatóság, Prímszámok, C gyakorlat
Hivatkozás(ok):Feladatok: 1990/március: C.210

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.

Ha egy számnak van közös osztója pq-val, akkor ‐ mivel p is és q is prímszám ‐ ez csak úgy lehetséges, ha a szám vagy p-vel, vagy q-val osztható. A pqn-nél kisebb vagy egyenlő p-vel osztható számok

p,2p,3p,...,nqp,számuk:nq;
ugyanígy a q-val osztható számok
p,2p,3p,...,npq,számuk:np;
de mivel kétszer számoltuk azokat, amelyek p-vel is és q-val is oszthatók, ezek számát, n-et le kell vonnunk. Így
f(n)=n(p+q)-n.

Tegyük fel, hogy
f(n)n=1990,
azaz
f(n)n=n(p+q)-nn=1990,
ahonnan
p+q=1991.

Egy összeg csak úgy lehet páratlan, ha egyik tagja páros, a másik páratlan. Mivel páros prímszám csak egy van, a 2, így pl. p=2, ekkor q=1989 lenne, de ez nem prímszám. Így ellentmondáshoz jutottunk, tehát feltevésünk nem lehet igaz, vagyis f(n)n nem lehet egyenlő 1990-nel.
Parlagh Ildikó (Miskolc, Herman O. Gimn., IV. o. t.)
dolgozata alapján