Kezdőlap


Feladat:	I.19	Korcsoport: -	Nehézségi fok: -
Füzet:	2002/március, 169. oldal		PDF \| MathML
Témakör(ök):	Feladat

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.

Az ún. kis Fermat-tétel azt mondja ki, hogy ha $p$ prímszám, $a$ pedig olyan egész szám, amely nem osztható $p$ -vel, akkor az $a^{p - 1} - 1$ különbség osztható $p$ -vel, vagy másképpen írva:

\begin{matrix} a^{p - 1} \equiv 1 (mod p) . \end{matrix}

Például

2^{12} = 4096

maradékul 1-et ad 13-mal osztva.
A kis Fermat-tétel megfordítása azonban nem igaz, azaz ha az

a^{p - 1} - 1

különbség osztható

p

-vel, abból nem következik, hogy

p

prímszám. Például:

3^{340} \equiv 1 (mod 341)

, pedig

341 = 11 \cdot 31

. Vannak olyan

p

összetett számok is, amelyek minden,

p

-nél kisebb,

p

-hez relatív prím

a

-ra kielégítik a kis Fermat-tételt. Az ilyen

p

-ket felfedezőjükről Carmichael-számoknak nevezzük. A legkisebb ilyen szám az 561.
Készítsünk programot (I19.PAS,

...

), amely beolvas két természetes számot (

1 \leq N \leq M \leq 100 000

), majd kiírja az

N

és

M

közötti Carmichael számokat!