Kezdőlap


Feladat:	Gy.2590	Korcsoport: 16-17	Nehézségi fok: könnyű
Megoldó(k):	Steiner Melinda
Füzet:	1990/november, 390 - 391. oldal		PDF \| MathML
Témakör(ök):	Legnagyobb közös osztó, Euklideszi algoritmus, Gyakorlat
Hivatkozás(ok):	Feladatok: 1989/december: Gy.2590

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.

Ismeretes, hogy az $A$ és $B$ számok $d = (A, B)$ legnagyobb közös osztója osztja az $A - n \cdot B$ számot is minden $n$ egészre.
Ha $n = 1988$ , akkor

\begin{matrix} a - 1988 B = 1989^{1990} - 1988^{1990} - 1988 \cdot 1989^{1989} + 1988^{1990} = \\ = 1989^{1989} (1989 - 1988) = 1989^{1989} . \end{matrix}

A

és

B

számok legnagyobb közös osztójának tehát többszöröse a

B

-t előállító különbség első tagja,

1989^{1989}

, így

d

a második tagnak,

1988^{1989}

-nek is osztója.
Mivel

1988

és

1989

szomszédos egész számok, a legnagyobb közös osztójuk

1

, nincs tehát közös prímtényezőjük. A számelmélet alaptétele szerint ekkor a hatványaiknak sem lehet közös prímtényezője.

1988^{1989}

és

1989^{1989}

tehát relatív prímek, így

A

és

B

is azok.

Steiner Melinda (Bonyhád, Petőfi S. Gimn., I. o. t.)

dolgozata nyomán

Megjegyzések. 1. Hasonló eredményre jutunk, ha elvégezzük a két szám legnagyobb közös osztóját szolgáltató euklidészi algoritmus első osztási lépését:

\begin{matrix} (1989^{1990} - 1988^{1990}) : (1989^{1989} - 1988^{1989}) = 1989 \\ \frac{1989^{1990} - 1989 \cdot 1988^{1989}}{1989 \cdot 1988^{1989} - 1988^{1990}} . \end{matrix}

Azt kaptuk, hogy

A = 1989 B + 1988^{1989}

, így

(A, B) = (B, 1988^{1989})

, ahonnan az ismertetett megoldás szerint kaphatjuk a végeredményt.
2. Hasonló okoskodással általában is igazolható, hogy

(a^{n} - b^{n}, a^{m} - b^{m}) = a^{(n, m)} - b^{(n, m)}

, ha

a

és

b

relatív prímek. A feladatban

a = 1989

b = 1988

n = 1990

m = 1989