Feladat: F.2542 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Barabás Zoltán 
Füzet: 1986/március, 109 - 110. oldal  PDF file
Témakör(ök): Legnagyobb közös osztó, Euklideszi algoritmus, Műveletek polinomokkal, Polinomok szorzattá alakítása, Feladat
Hivatkozás(ok):Feladatok: 1985/október: F.2542

Mely a természetes számokra igaz, hogy (a4+3a2+1, a3+2a) legnagyobb közös osztója 1?

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.

I. megoldás. a3+2a szorzattá bontható: a3+2a=a(a2+2). Belátjuk, hogy a4+3a3+1 a fenti szorzat mindkét tényezőjéhez relatív prím. a4+3a2+1 az első tényezővel, a-val osztva 1 maradékot ad, tehát (a4+3a2+1,a)=1. Másrészt a4+3a2+1=(a2+2)(a2+1)-1, tehát a4+3a2+1 a második tényezővel, (a2+2)-vel osztva -1 maradékot ad, így (a4+3a2+1,a2+2)=1.
Ha egy szám egy szorzat mindkét tényezőjéhez relatív prím, akkor szorzatukhoz is relatív prím, tehát (a4+3a2+1,a3+2a)=1 minden egész a-ra.
II. megoldás. Megmutatjuk, hogy minden természetes számra (a4+3a2+1,a3+2a)=1. Ha a nullát természetes számnak tekintjük, akkor a=0-ra (1,0)=1. Ha a1, akkor az euklideszi algoritmust alkalmazva:

a4+3a2+1=a(a3+2a)+(a2+1);a3+2a=a(a2+1)+a;a2+1=aa+1;a=a1.
Miután az utolsó nem-nulla maradék az 1, ezért (a4+3a2+1,a3+2a)=1.