On the number of false witnesses for a composite number

Abstract

Ifais not a multiple ofnand${a^{n - 1}}\;\nequiv \;1\bmod \,n$, thennmust be composite andais called a "witness" forn. Let$F(n)$denote the number of "false witnesses" forn, that is, the number of$a\bmod n$with${a^{n - 1}} \equiv 1\bmod n$. Considered here is the normal and average size of$F(n)$forncomposite. Also considered is the situation for the more stringent Euler and strong pseudoprime tests.