Kezdőlap


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

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.

Megoldás. Legyen $a = 100 + 101 m$ és $b = 101 - 100 m$ , jelölje $a$ és $b$ legnagyobb közös osztóját $d$ . Ha $d ∣ a$ és $d ∣ b$ , akkor $d ∣ 100 a + 101 b$ .

\begin{matrix} 100 a + 101 b = 100^{2} + 100 \cdot 101 m + 101^{2} - 101 \cdot 100 m = 100^{2} + 101^{2} = 20 201. \end{matrix}

20 201

prímszám, így ha

a

-nak és

b

-nek van valódi 1-nél nagyobb osztója, az csak

20 201

lehet.
A

d ∣ a

és

d ∣ b

oszthatóságokból a

d ∣ a + b

is következik, ezért

d ∣ 100 + 101 m + 101 - 100 m = 201 + m

. Ebből viszont

m = k \cdot d - 201

adódik (

k

egész szám). Ha pedig

d = 20 201

, akkor

m = k \cdot 20 201 - 201

.
Az

m = k \cdot 20 201 - 201

alakú egész számokra

\begin{matrix} a = 100 + 101 (20 201 k - 201) = 100 + 101 \cdot 20 201 k - 101 \cdot 201 = 20 201 (101 k - 1), \end{matrix}

\begin{matrix} b = 101 - 100 (20 201 k - 201) = 101 + 100 \cdot 20 201 k + 100 \cdot 201 = 20 201 (1 - 100 k) . \end{matrix}

Vagyis ebben az esetben

a

és

b

is többszöröse

20 201

-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 + 101 m

és

101 - 100 m

legnagyobb közös osztója

20 201

. (Ha

d = - 20 201

, akkor is ugyanezeket az

m

értékeket kapjuk.) Minden más

m

esetén

(100 + 101 m; 101 - 100 m) = 1