Feladat: B.3733 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Nagy Csaba 
Füzet: 2005/március, 157 - 158. oldal  PDF file
Témakör(ök): Legnagyobb közös osztó, Prímszámok, Feladat
Hivatkozás(ok):Feladatok: 2004/május: B.3733

Van-e olyan m egész szám, amelyre 100+m101 és 101-m100 nem relatív prímek?

Megoldás. Legyen a=100+101m és b=101-100m, jelölje a és b legnagyobb közös osztóját d. Ha da és db, akkor d100a+101b.
100a+101b=1002+100101m+1012-101100m=1002+1012=20201.

20201 prímszám, így ha a-nak és b-nek van valódi 1-nél nagyobb osztója, az csak 20201 lehet.
A da és db oszthatóságokból a da+b is következik, ezért d100+101m+101-100m=201+m. Ebből viszont m=kd-201 adódik (k egész szám). Ha pedig d=20201, akkor m=k20201-201.
Az m=k20201-201 alakú egész számokra
a=100+101(20201k-201)=100+10120201k-101201=20201(101k-1),
b=101-100(20201k-201)=101+10020201k+100201=20201(1-100k).
Vagyis ebben az esetben a és b is többszöröse 20201-nek, ezért ez a legnagyobb közös osztójuk, tehát nem relatív prímek.
 
Megjegyzés. Vegyük észre, hogy az összes olyan m-et meghatároztuk, amelyre 100+101m és 101-100m legnagyobb közös osztója 20201. (Ha d=-20201, akkor is ugyanezeket az m értékeket kapjuk.) Minden más m esetén (100+101m;101-100m)=1.