We describe recent results improving previous estimates of H. W. Lenstra and A. Granville on the smallest non-zero Fermat quotient. This question is motivated by applications to square-free testing (H. W. Lenstra, 1979), Fermat Last Theorem (A. Granville, 1991) and algebraic number theory and coding theory (Y. Ihara, 2006).

This is joint work with Jean Bourgain, Kevin Ford, and Sergei Konyagin.