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. szorzattá bontható: . Belátjuk, hogy a fenti szorzat mindkét tényezőjéhez relatív prím. az első tényezővel, -val osztva maradékot ad, tehát . Másrészt , tehát a második tényezővel, -vel osztva maradékot ad, így . 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 minden egész -ra. II. megoldás. Megmutatjuk, hogy minden természetes számra . Ha a nullát természetes számnak tekintjük, akkor -ra . Ha , akkor az euklideszi algoritmust alkalmazva:
Miután az utolsó nem-nulla maradék az , ezért .
|