Az Egri Ho Si Minh Tanárképző Főiskola Tud. Közleményei. 1978. (Acta Academiae Paedagogicae Agriensis : Nova series ; Tom. 14)

továbbá abszolút pszeudoprímnek nevezzük, ha n minden a természetes szám vonatkozásában pszeudoprím. Könnyű belátni, hogy minden összetett n természetes szám végtelen sok a egész vonatkozásában pszeudoprím, még akkor is ha megkívánjuk, hogy n és a relatív prímek legyenek. Ugyanis tetszőleges összetett n esetén, ha a = n * fc+l (ahol k tetszőleges egész), akkor (n, a) = 1 és nyilván (13) is teljesül, ezért n pszeudoprím az a vonatkozásában. K. Szymiczek a következő kérdést tette fel: Melyek azok az n összetett természetes számok, melyek csak az a = n • A:+l alakú egészek vonatkozásában pszeudoprímek az («, a) = 1 feltétel mellett? (Lásd A. Rotkiewicz [13], 143. oldal, Problem, 46). A következőkben választ adunk K. Szymiczek kérdésére, bebizonyítjuk a következő tételt. 4. Tétel: Egy n összetett természetes szám (n, a) = 1 feltétel mellett akkor és csak akkor csupán az a — n • k+\ alakú egészek vonatkozásában pszeudoprím, ha («-1, ip(n))= 1. (A tételt más megfogalmazásban lásd [9]-ben). r Bizonyítás: Legyen n — ír pf

1 i=l A 2. Tétel bizonyításából következik, hogy az x

n =x (mod n) kongruencia rt-hez relatív prím megoldásainak száma akkor és csak akkor 1, ha d-d

x = d

2 = ... d

r = 1, vagyis ha («-1, <PÍPfi)) = 1 minden i = 1, 2,. . . , r esetén. Ez a feltétel azonban ekvivalens az (n-1, <p(n)) = 1 feltétellel és az egyetlen (JC, ri) = 1 feltételt kielégítő megoldás nyilván x = l(mod n) vagyis x = k ' n+1. Ebből, és az a vonatkozású pszeudoprímek definíciójából már következik az állítás. Megjegyezzük, hogy végtelen sok olyan n természetes szám létezik, mely kielégíti a 4. Tétel feltételeit. Ilyenek például az n = vagy az n = 2 p{p prím) alakú számok, hiszen (2*-l,2*-l)= 1 és(2p-l,p-l)= 1. Vizsgáljuk most meg, hogy mi a feltétele annak, hogy egy összetett n természetes szám abszolút pszeudoprím legyen. A definíció alapján n nyilván akkor és csak akkor abszolút pszeudoprím, ha a (13) kongruencia indentikusan teljesül. Ennek feltételét viszont már megadtuk az előzőekben, E Hewitt tételének bizonyítása során: n négyzetmentes, és ha n = p

x, p

2, . . p

r, akkor (p,--1) | («-1) minden í = 1, 2,. . . , r esetén. A feltételekből az is következik, hogy n páratlan (p

x =£2), mert ellenkező esetben n-1 páratlan és így nem osztható egy páros p,—1 egész számmal. De az is következik, hogy r > 3, ugyanisr = 2esetén ip\-\) I (pip

2-l)relációbólpip

2-l = (Pi-1)P2+P2-1 miatt (pj — — 1) I (p

2 —1) és hasonlóan (p

2-1) | (PI-1) adódna, amiből p

t = p

2 következne. Ez viszont lehetetlen, mert már láttuk, hogy n négyzetmentes. Tehát a következő eredményt kaptuk: 5. tétel: Egy n összetett természetes szám akkor és csak akkor abszolút pszeudoprím, ha páratlan, négyzetmentes, legalább három különböző páratlan prímtényező szorzata és n minden p prímtényezőjére (p— 1) | (n—1). Ezt a tételt először R. D. Carmichael [2] bizonyította, a mi bizonyításunk azonban különbözik az általa adott bizonyítástól. 463