## You are here

HomeErd\H{o}s-Selfridge classification of primes

## Primary tabs

# 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)

## Mathematics Subject Classification

11A51*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections