Episode I

Alice és Bob

. rész: Nem Miller-Rabin-tanúk és nem Fermat-tanúk viszonya nem prímhatványok esetén

Legyen n egy tetszőleges 1-nél nagyobb páratlan szám, amelynek legalább két egymástól különböző prímtényezője is van, azaz nem prímhatvány. Képezzük azt az e\geq 1 kitevőt és k\geq 1 páratlan számot, amelyekre teljesül az alábbi:

n-1=2^ek

A 24.19. Tétel szövegével megegyező módon legyen j_{\text{max}} a legnagyobb olyan j kitevő a \{0;1;2;\ldots;e-1\} egész számok között, amelyhez léteznek olyan x egész számok, hogy teljesül az x^{2^j}\equiv -1\pmod n kongruencia. Megjegyzés: Az említett 24.19. Tétel alapján legalább egy ilyen j kitevő biztosan létezik, tehát j_{\text{max}} is létezik.

Ugyancsak a 24.19. Tétel szövegével megegyezően jelöljük H_n-nel azon [a]_n maradékosztályok halmazát, amelyek esetén az a^{2^{j_{\text{max}}}k} hatvány 1-gyel vagy -1-gyel kongruens modulo n, azaz:

a^{2^{j_{\text{max}}}k} \equiv \pm 1\pmod n

Végül jelöljük F_n-nel azokat a modulo n maradékosztályokat, amelyek nem Fermat-tanúi n-nek.

Ekkor H_n-hez hasonlóan F_n is részcsoportot alkot a (\Z/n\Z)^{\times} multiplikatív csoportban, valamint teljesülnek az alábbiak:

  1. Ha n nem Carmichael-szám, akkor H_n\lt F_n\lt (\Z/n\Z)^{\times}
  2. Ha n Carmichael-szám, akkor H_n\lt F_n=(\Z/n\Z)^{\times}.

Szavakkal ez így fogalmazható meg: H_n valódi részcsoport F_n-ben, amely viszont akkor és csak akkor valódi részcsoport (\Z/n\Z)^{\times}-ben, ha n nem Carmichael-szám (egyébként megegyezik vele).