# Erdős-Selfridge classification of primes

Paul Erdős and John Selfridge classified primes $p$ thus: If the largest prime factor of $p+1$ is 2 or 3, then $p$ is in class 1+. Otherwise, assign to $c$ the class of the largest prime factor of $p+1$, then $p$ is in class $(c+1)+$. Class 1+ primes are of the form $2^{i}3^{j}-1$ for $i>-1$ and $j>-1$.

According to this scheme, $p<200$ are sorted thus:

Class 1+: 2, 3, 5, 7, 11, 17, 23, 31, 47, 53, 71, 107, 127, 191 ( listed in A005105 of Sloane’s OEIS)

Class 2+: 13, 19, 29, 41, 43, 59, 61, 67, 79, 83, 89, 97, 101, 109, 131, 137, 139, 149, 167, 179, 197, 199 (A005106)

Class 3+: 37, 103, 113, 151, 157, 163, 173, 181, 193 (A005107)

Class 4+: 73

A005113 lists the smallest prime of class $n+$.

Clearly, all Mersenne primes are class 1+. The known Fermat primes show slightly more variety: 257 is class 3+ while 65537 is class 4+.

## References

• 1 R. K. Guy, Unsolved Problems in Number Theory. New York: Springer-Verlag (2004)
Title Erdős-Selfridge classification of primes ErdHosSelfridgeClassificationOfPrimes 2013-03-22 16:05:02 2013-03-22 16:05:02 PrimeFan (13766) PrimeFan (13766) 5 PrimeFan (13766) Definition msc 11A51 Erdos-Selfridge classification of primes