A theorem of Gekeler compares the number of non-isomorphic automorphic representations associated with the space of cusp forms of weight $k$ on $\unicode[STIX]{x0393}_{0}(N)$ to a simpler function of $k$ and $N$, showing that the two are equal whenever $N$ is squarefree. We prove the converse of this theorem (with one small exception), thus providing a characterization of squarefree integers. We also establish a similar characterization of prime numbers in terms of the number of Hecke newforms of weight $k$ on $\unicode[STIX]{x0393}_{0}(N)$.

It follows that a hypothetical fast algorithm for computing the number of such automorphic representations for even a single weight $k$ would yield a fast test for whether $N$ is squarefree. We also show how to obtain bounds on the possible square divisors of a number $N$ that has been found not to be squarefree via this test, and we show how to probabilistically obtain the complete factorization of the squarefull part of $N$ from the number of such automorphic representations for two different weights. If in addition we have the number of such Hecke newforms for even a single weight $k$, then we show how to probabilistically factor $N$ entirely. All of these computations could be performed quickly in practice, given the number(s) of automorphic representations and modular forms as input.

We show that for any fixed base a, a positive proportion of primes become composite after any one of their digits in the base a expansion is altered; the case where a=2 has already been established by Cohen and Selfridge [‘Not every number is the sum or difference of two prime powers’, Math. Comput.29 (1975), 79–81] and Sun [‘On integers not of the form ±pa±qb’, Proc. Amer. Math. Soc.128 (2000), 997–1002], using some covering congruence ideas of Erdős. Our method is slightly different, using a partially covering set of congruences followed by an application of the Selberg sieve upper bound. As a consequence, it is not always possible to test whether a number is prime from its base a expansion without reading all of its digits. We also present some slight generalisations of these results.