Über die Pseudoprimzahlen. (Q2579837)

Als Pseudoprimzahl wird eine zusammengesetzte Zahl \(m\) bezeichnet, für die bei beliebigem zu \(m\) teilerfremdem \(a\) die Kongruenz \(a^{m-1} \equiv 1 \) (mod \(m\)) besteht. (Der kleine Fermatsche Satz gilt ja bekanntlich nicht nur für Primzahlen.) Es wird gezeigt: Eine Pseudoprimzahl muß Produkt von mindestens drei voneinander verschiedenen ungeraden Primzahlen sein. Bildet man alle Zerlegungen \(m = pn \) (\(p = \) Primzahl), so ist dafür, daß \(m\) Pseudoprimzahl ist, notwendig und hinreichend, daß \(m - 1\) durch \(p - 1\) teilbar ist. Unterhalb \(10\,000\) gibt es sieben Pseudoprimzahlen, die sämtlich aus drei Faktoren zusammengesetzt sind. Die kleinste Pseudoprimzahl aus vier Faktoren ist \(63\,973 = 7 \cdot 13 \cdot 19 \cdot 37\).