\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf 
A New Solution to the Equation  \\
\vskip .1in
$\tau(p) \equiv 0 \pmod{p}$ 
}
\vskip 1cm
\large
Nik Lygeros\\
14 av. Condorcet\\
69100 Villeurbanne\\
France\\
\href{mailto:nlygeros@gmail.com}{\tt nlygeros@gmail.com}\\
\ \\
Olivier Rozier \\
113 av. de la Dhuys \\
93170 Bagnolet \\
France\\
\href{mailto:olivier.rozier@gmail.com}{\tt olivier.rozier@gmail.com} \\
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\vskip .2in

\begin{center}
{\it Dedicated to Jean-Pierre Serre.}
\end{center}

\vskip .2in

\begin{abstract}
The known solutions to the equation  $\tau(p) \equiv 0$ (mod $p$) were $p = 2, 3, 5, 7,$ and 2411. Here we present our method to compute the next solution,
which is $p = 7758337633$. There are no other solutions up to $10^{10}$.
\end{abstract}

 

\section{Introduction}
Our study of the Ramanujan's tau function was inspired by the reading
of \cite{Ser70}. Lygeros's interest in the congruences of the modular
function led him to a correspondence \cite{Ser88} with Serre, in 1988.
We identified a few research topics, one of them being the particular
congruence  $\tau(p) \equiv 0$ (mod $p$). For some time, the prime
integers 2, 3, 5 and 7 were regarded as the only solutions. Serre wrote
us about the solution $p=2411$ found by Newman \cite{New72} in 1972. In
another letter, Serre exposed the principle of a ``log log
philosophy'', already introduced by Atkin. After having  consulted the
latter, it appeared that the next solution could be of the order of 1
billion, if it existed. Several numerical approaches were considered.
However, computers capabilities were still inadequate to reach 1
billion.

Nearly ten years later, Henri Cohen told us about a faster method based
on the computation of Hurwitz class numbers \cite{Coh75,Coh93}.
Therefore we wrote two programs: the first one generated the
Hurwitz tables, and the other computed the congruences $\tau(p) \bmod
p$, for successive primes $p$. After several months of numerical
investigations on Rozier's computers, we found the next solution on
March 15 2010 (see \seqnum{A007659} of \textit{The On-Line
Encyclopedia of Integer Sequences}).

Here we describe the algorithm, derived from the Eichler-Selberg trace
formula, and give some indications on how obtaining an optimized
implementation. We also establish a formula related to the Catalan triangle
(\seqnum{A008315}) and used to efficiently compute arbitrary $\tau(p)$
values for primes $p$ up to $10^{10}$. This was necessary to
check the consistency of our results.

\section{Ramanujan's tau function}
The tau function (\seqnum{A000594}) is defined as the Fourier coefficients of the modular discriminant
\begin{equation}
\Delta(z) = q\prod_{n=1}^{+\infty}(1-q^{n})^{24} = \sum_{n=1}^{+\infty} \tau(n)q^{n}
\text{ , where }  q = e^{2 \pi i z}.
\end{equation}

It attracted a lot of interest from Indian mathematician Srinivasa Ramanujan. He discovered some arithmetical properties, later proved by Mordell \cite{Mor20}:
\medskip

\begin{tabular}{ll}
$\tau (nm) = \tau (n)\tau (m)$ & for $n$, $m$ relatively prime integers;\\
$\tau (p^{r+1} ) = \tau (p)\tau (p^{r}) - p^{11}\tau (p^{r-1})$ & for $p$ prime and $r$ an integer $\geq 1$.
\end{tabular}
\medskip

It turns out that the value of $\tau(n)$ for an integer $n$ can be
easily derived from the values $\tau(p)$ for all prime divisors $p$ of
$n$.  

Moreover, the tau function has well-known congruences modulo $2^{11}$,
$3^{6}$, $5^{3}$, 7, 23 and 691 \cite{Ber99, Ram16, Ser72} . For
instance, any computed value $\tau (n)$ must verify
\begin{equation}\label{Mod691} \tau(n) \equiv \sigma_{11}(n) \pmod{691}
\end{equation} where $\sigma_{11}(n)$ is the sum of the 11-th powers of
the divisors of $n$.

An upper bound, also conjectured by Ramanujan and proved by Deligne in 1974, is given by 
\begin{equation}\label{MaxTau}
|\tau (p)| \leq 2 p^{\frac{11}{2} } \text{ , for } p \text{ prime}.
\end{equation}

The theory of Galois representations attached to modular forms offers
deeper understanding of the congruences of Fourier coefficients
\cite{Ser67}. In particular, the major achievements of Serre and Deligne on the
subject provide the asymptotic density of primes $p$ such
that $\tau(p) \equiv 0$ (mod $l$) for a given prime $l$. Recent
advances even establish that $\tau(p)$ mod $l$ can be computed in
polynomial time in $\log(p)$ and $l$ \cite{Cou10}. Nevertheless, most
of the related results do not apply when $l = p$, and few are known in
that case. The question whether the equation $\tau(p) \equiv 0$ (mod
$p$) has infinitely many solutions remains open \cite{Cho05, Mur07}.
Such primes $p$ are said to be not-ordinary for the $\tau$ function
\cite{Gou97}.

\section{The log log philosophy}
If we assume that the values $\tau (p)$ are randomly distributed modulo $p$
for all primes $p$, then we can roughly evaluate the number of non-ordinary primes less than $N$, as follows:\\
$$\sum_{p\in \Pi, p \leq N }{\frac{1}{p} }   \sim \int_{e}^{N} \frac{dt}{t \log t}  = \log \log N $$
%$$\sum_{ \text{ \begin{tabular}{c} $p\in \Pi$ \\ $p<N$ \end{tabular} } }{\frac{1}{p} }   \sim \int_{e}^{N} \frac{dt}{t \log t}  = \log \log N $$
Heuristically, this number should grow very slowly to infinity as $\log
\log N$. This is referred to as the ``log log philosophy'' \cite{Rib96,
Ser88}. Furthermore, the probability that the interval  $\left[ 10^{a},
10^{b} \right]$,  $a\leq b$, contains at least a non-ordinary prime is
approximately $(b-a)/b$. Thus, if we conduct an exhaustive search
between $10^{6}$ and $10^{10}$, the estimated probability of success is
only $2/5$.

\section{Eichler-Selberg trace formula}
The modular discriminant $\Delta$ is known to be a cusp form of weight
12, in the upper-half of the complex plane. The space of such modular
forms has dimension 1. Hence $\Delta$ is an eigenform of the Hecke
operators $T_{12}(n)$ applying in this modular space, and $\tau(n) = Tr
T_{12}(n)$  for all integers $n$.

Let $k \geq 4$ be an even integer. We recall the Eichler-Selberg trace formula in the space of cusp forms of weight $k$ and level 1 \cite{Cha06}:
$$Tr T_{k}(n) = -\frac{1}{2} \sum_{|t|\leq 2\sqrt{n}} P_{k}(t,n)H(4n-t^{2}) - \frac{1}{2} \sum_{dd'=n} \min(d,d')^{k-1}$$
where $H(n)$ is the Hurwitz class number of the integer $n$ and
$P_k$ is the polynomial in two variables defined by the equation 
$P_{k}(t,n) = \frac{\rho^{k-1}-\bar{\rho}^{k-1}}{\rho-\bar{\rho}}$
with $\rho+\bar{\rho} = t$ and $\rho\bar{\rho} = n$.

The computation of Eichler-Selberg trace formula is not straightforward, and we would like an expression that gives the explicit coefficients of $P_k(t,n)$ polynomials.

From previous definition, it follows that $\rho = r e^{i\theta }$  with $r = \sqrt{n}$, $\cos\theta = \frac{t}{2\sqrt{n} }$ and
$$P_k(t,n) = n^{\frac{k-2}{2} } \frac{\sin \left( (k-1)\theta  \right) }{\sin\theta } .$$
%with $U_{k}$ : Chebyshev polynomial of second kind and degree $k$. 

It becomes obvious that $P_k(t,n)$ is closely related to Chebyshev polynomials $U_k$ of the second kind and degree $k$:
$$P_k(t,n) = n^{\frac{k-2}{2} }U_{k-2} \left( \cos\theta \right)  =  n^{\frac{k-2}{2} }U_{k-2} \left( \frac{t}{2 \sqrt{n} }  \right)$$

By applying the general expression \cite{Abr72} of $U_k$ with binomial coefficients, we get
$$P_{k}(t,n) = \sum_{i=0}^{ \frac{k}{2} - 1} (-1)^{i} 
{{k-2-i}\choose{i}} n^{i} t^{k-2-2i} .$$

Now we introduce the Hurwitz sums $s_{j}(n)$ defined by
$$s_{j}(n) = \frac{1}{2}  \sum_{|t|\leq 2\sqrt{n} } t^{j}H(4n-t^2).$$

Thus we obtain
\begin{equation}\label{TrTk} 
Tr T_{k}(n) = - \sum_{i=0}^{ \frac{k}{2} - 1} (-1)^{i} 
{{k-2-i}\choose{i}} n^{i}s_{k-2-2i}(n) - \frac{1}{2} \sum_{dd'=n} \min(d,d')^{k-1}.
\end{equation}

For $k=12$ and $p$ a prime, we get the explicit formula \cite{Cha06}:
$$\tau (p) = -s_{10}(p) + 9ps_{8}(p) - 28p^{2}s_{6}(p) + 35p^{3}s_{4}(p) - 15p^{4}s_{2}(p) + p^{5}s_{0}(p)-1.$$
\par
A congruence modulo $p$ can be derived, as follows:
\begin{equation}\label{TauModp} 
\tau (p) \equiv -s_{10}(p) -1 \pmod{p}.
\end{equation}

\section{Hurwitz sums and Catalan numbers}

For every prime $p$, it is known \cite{Coh75,Coh93}, since Kronecker, that 
\begin{equation}\label{s0}
 s_0(p) = p .
\end{equation}

Now we consider the linear system composed of equation (\ref{s0})  and trace formulas (\ref{TrTk}) for  $k = 4, 6, 8, 10, 12$ and prime $p$. 

The theory of cusp forms asserts that 
$$Tr T_{k}(p) = 
\begin{cases}
0, & \text{ if $k = 4,6,8,10$; } \\
\tau(p),  \text{if $k = 12$}.
\end{cases}.$$

\medskip

This yields a triangular system of six equations and six unknown values  $s_{j}(p)$, for $j = 0, 2, 4, 6, 8, 10 $.

$$\begin{pmatrix}
1&0&0&0&0&0\\
-p&1&0&0&0&0\\
p^2&-3p&1&0&0&0\\ 
-p^3&6p^2&-5p&1&0&0\\
p^4 & -10p^3 & 15 p^2 & -7p & 1 & 0\\
-p^5&15p^4&-35p^3&28p^2&-9p&1
\end{pmatrix}
\begin{pmatrix}
s_0(p) \\
s_2(p) \\
s_4(p) \\
s_6(p) \\
s_8(p) \\
s_{10}(p)
\end{pmatrix}
=
\begin{pmatrix}
p \\
-1 \\
-1 \\
-1 \\
-1 \\
-\tau(p)-1
\end{pmatrix}
$$

This system has determinant 1, and its inverse matrix is 

$$\begin{pmatrix}
1&0&0&0&0&0\\
p&1&0&0&0&0\\
2p^2&3p&1&0&0&0\\
5p^3&9p^2&5p&1&0&0\\
14p^4&28p^3&20p^2&7p&1&0\\
42p^5&90p^4&75p^3&35p^2&9p&1
\end{pmatrix}.
$$

In the first column appear the Catalan numbers \seqnum{A000108} $C_n =
\frac{1}{n+1} {{2n} \choose n}$,
which have generating function   $c(x) = \frac{1 - \sqrt{1-4x}}{2x} = 1
+ x + 2x^2 + 5x^3 + 14x^4 +42x^5 + \ldots $.

In the remaining columns, the non-zero coefficients are the first terms of the number sequences  $C_n(m) = [x^{n}]c^{m}(x)$, generated by the  m-th powers of  $c(x)$, for  $m = 3, 5, 7, 9, 11$ (see \seqnum{A000245}, \seqnum{A000344}). They are given by the general formula $C_{n}(m) = \frac{m}{m+2n} {{m+2n}\choose n}$
\cite{Gra89, Hog76}.
\par
The sequences  $C_n(m)$  are widely referenced in the literature with a great variety of definitions, notations, and denominations. For instance, this number family also appears in the Catalan triangle \seqnum{A008315}, which may also have other representations (e.g., \seqnum{A009766},  \seqnum{A108786}, \cite{Abr72} p796). Moreover, there are several combinatorial results involving Chebyshev polynomials  $U_k$ and  $C_n(m)$ numbers, and we only give an inversion formula, following \cite{Abr72, Lan00, Rad00}:
  $$\sum_{i=0}^{n}{C_{n-i}(2i+1)U_{2i}(x/2)}  = x^{2n} .$$

The resolution of the previous system implies the Hurwitz sums below: 
\begin{eqnarray*}
 s_2(p) &=& p^2 - 1 \\ 
 s_4(p) &=& 2p^3 - 3p - 1 \\
 s_6(p) &=& 5p^4 - 9p^2 -5p -1 \\
 s_8(p) &=& 14p^5 - 28p^3 - 20p^2 - 7p -1\\
 s_{10}(p) &=& 42p^6 - 90p^4 - 75p^3 - 35p^2 - 9p - 1 -\tau (p) .
\end{eqnarray*}
 
As a consequence of the functional equation  $c(x) = 1 + xc^2(x)$, the polynomial parts in p have the common factor $(p+1)$:
\begin{eqnarray*}
 s_2(p) &=& (p+1)(p-1) \\
 s_4(p) &= &(p+1)(2p^2-2p-1) \\
 s_{6}(p) &=& (p+1)(5p^{3} - 5p^{2} - 4p - 1) \\
 s_{8}(p) &=& (p+1)(14p^{4} - 14p^{3} - 14p^{2} - 6p -1) \\
 s_{10}(p) &=& (p+1)(42p^{5} - 42p^{4} - 48p^{3} - 27p^{2} - 8p - 1) - \tau(p) 
\end{eqnarray*}

Again, the above coefficients are issued from the number sequences $C_n(m)$ for  $m = 1, 2, 4, 6, 8, 10$ (see \seqnum{A002057}, \seqnum{A003517}), with a minus sign if  $m>1$. These are essentially the same sequences as in Shapiro's Catalan triangle \cite{Sha76}.

We have used the very last equation to compute  $\tau (p)$  numerically
from  $s_{10}(p)$. It avoids the computation of $s_k(p)$ for any
$k<10$, except for verification.


\section{Computing Hurwitz tables}
The Hurwitz numbers $H(n)$ (see \seqnum{A058305}, \seqnum{A058306}), for integers $n>0$, are closely related to the class numbers of binary quadratic forms $ax^{2}+bxy+cy^{2}$ of negative discriminant $-n$. It can be proved \cite{Coh93} that $ H(n)$ is equal to the number of integer triplets $(a,b,c)$ determined by the four conditions
\begin{enumerate}
\item $4ac - b^{2} = n$,
\item $|b| \leq a \leq c$,
\item if $a=|b|$ or $a=c$, then $b \geq 0$,
\item the triplets $(a,0,a)$ (resp. $(a,a,a)$) are counted with weight $1/2$ (resp. $1/3$).
\end{enumerate}

Hence $H(n)$ is a non-negative rational value $p/q$ with denominator $q
\leq 3$. Moreover, the first condition implies $H(n)=0$ for $n \equiv$
1 or 2 (mod 4).

%\begin{table} [H]
\begin{center}
\begin{tabular}{c|cccccccccccccccc}
 $n$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\
 \hline
 $H(n)$ & 0 & 0 & 1/3 & 1/2 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 4/3 & 0 & 0 & 2 & 3/2 
\label{tab_hur}
\end{tabular}
%\caption{Hurwitz class numbers}
\end{center}
%\end{table}

Our algorithm is directly derived from previous properties of $H(n)$,
and was written in the C language. It is indeed straightforward to
compute the Hurwitz numbers for all integers of a given
interval together, by generating all the triplets $(a,b,c)$ satisfying
conditions 2 and 3, and such that $ 4ac-b^{2} $ falls into the
interval. Somehow, this method recalls the sieve of Eratosthenes.

During and after calculations, it is convenient to store only the
integer values $6H(n)$ for $ n \equiv$ 0 or 3 (mod 4), $ N_1 \leq n <
N_2 $, where $N_1$ and $N_2$ are arbitrary integers. These two
parameters $N_1$ and $N_2$ control the granularity of computations. We
suggest adjusting them in such a manner that the temporary tables in
main memory have a smaller size than the cache memory of the CPU. Since
$6H(n)$ has a value of the order of $\sqrt{n}$, if not zero, we can use
4-bytes integers to handle those data. Empirically, there exists some
optimal value for the difference $ N_2-N_1 $, typically between 200000
and 1000000, depending on hardware specifications. The access time in
memory appears to be critical in our case.

As expected, we checked that the computation time of the Hurwitz tables
for all integers in the interval $ \left[ N; N+K \right) $, for a
constant $K$ such that $ N \gg K\gg 1 $, grows like $ N^{1/2 } $,
approximately (Table \ref{comp_hur}.).

\begin{table} [H]
\begin{center}
\begin{tabular}{|cc|}
 \hline
 \hspace{0.5cm} $N$ \hspace{0.5cm} & \hspace{0.5cm} time	\hspace{0.5cm} \\
 \hline
 0 & 0.28 s	 \\
 $10^{6}$ &	0.49 s	\\
 $10^{7}$ &	01.27 s	\\
 $10^{8}$ &	03.83 s	\\
 $10^{9}$ &	12.23 s	\\
 $10^{10}$ & 43.60 s \\
 \hline
 \end{tabular}
\caption{Computation time of Hurwitz tables between $N$ and $N+10^6$}
\label{comp_hur}
\end{center}
\end{table}

In our study, we generated the Hurwitz tables up to 40 billion, with an
overall size of 75 Gb in binary format. This made possible the
calculation of $\tau(p)$ mod $p$ for primes $p<10^{10}$. We verified
the validity of our tables by applying equation (\ref{s0}), for all
primes within several intervals of $ 10^6$ integers.

\section{Computing the tau function}
We computed the values $\tau(p)$ mod $p$, for successive primes $p$, with another program also written in the language C that uses formula (\ref{TauModp})
$$ \tau(p) \equiv -s_{10}(p) -1 \pmod{p} ,\hspace{0.5cm} \text{ where } s_{10}(p) =  \sum_{0 < t < 2\sqrt{p} } t^{10}H(4p-t^2).$$

Since all the Hurwitz tables do not fit in RAM memory, we had to load
them dynamically. Obviously, it is recommended to compute many
congruences $\tau(p)$ mod $p$ at once. We suggest dividing the Hurwitz
tables in arrays that fit in CPU cache memory and performing
calculations on each array sequentially. This optimization improves the
efficiency of the algorithm in case of an exhaustive search.

Similarly, we developed a program that gives the exact $\tau(p)$ values with the formula
$$ \tau(p) = (p+1)(42p^{5} - 42p^{4} - 48p^{3} - 27p^{2} - 8p - 1) - s_{10}(p) .$$
The upper bound (\ref{MaxTau})  provides a fair estimation of the order of $ \tau (p)$. Thus, we had to handle numbers with more than 50 digits. It can be achieved with the use of the multiprecision library PARI.

Clearly, both computation times grow roughly like $ \sqrt{p} $,
provided that the proportion of time spent to load Hurwitz tables is
small. Practically, it is the case if we compute tau function for a
sufficiently large set of consecutive primes (Table \ref{comp_tau}).
Hence the computation time for all primes $p$ up to a given integer $N$
evolves like $N^{3/2}$, approximately.

\begin{table} [H]
\begin{center}
\begin{tabular}{|ccc|}
 \hline
 \hspace{0.5cm} $N$ \hspace{0.5cm} & \hspace{0.5cm} time for $\tau(p) \bmod p$ \hspace{0.5cm} & \hspace{0.5cm} time for $ \tau(p) $ \\
 \hline
 0 &	05 s &	10 s 	\\
 $ 10^{6}$ & 08 s &	16 s 	\\
 $ 10^{7}$ & 22 s &	39 s 	\\
 $ 10^{8}$ & 72 s &	112 s 	\\
 $ 10^{9}$ & 306 s & 489 s	\\
 \hline
 \end{tabular}
\caption{Computation time of $\tau(p)$ mod $p$ and $\tau(p)$ for all primes $p$ between $N$ and $N+10^6$}
\label{comp_tau}
\end{center}
\end{table}

First investigations were conducted on a 32-bit computer with a Pentium
4 processor (2.6 GHz) and 1 Gb of RAM, between August and October,
2009. We generated the values of $\tau(p) \bmod p$ for primes $ p
< 1.5 \cdot 10^9 $. Not surprisingly, we were facing increasing
technical constraints. Then we acquired a 64-bit computer with a Core
i7 processor (2.93 GHz) and 6 Gb of RAM, and we installed a Linux
operating system. Thanks to the presence of 4 cores (8 execution
units), we could launch up to three processes for the
Hurwitz tables and four processes for the congruences simultaneously.

We generated the congruences modulo $p$ for all primes $p$ below 10
billion. The overall computation time for the Hurwitz tables and
$\tau(p)$ mod $p$ values was approximately two months, on a Core i7
processor. The Hurwitz tables computation represents a third of total
CPU time.

We also computed the exact $\tau(p)$ values for all primes $p$ up
to 1 billion, with a CPU time of about 35 hours, by launching two
processes. This does not include the computation time of the required
Hurwitz numbers, which was relatively short anyway. Finally, thousands of
$\tau(p)$ values for arbitrary primes $p$ between $ 10^9 $ and $
10^{10} $ were computed and verified by using some of the known
congruences, and systematically the congruence (\ref{Mod691}) modulo
691. It was indeed necessary to check the consistency of $\tau(p)$ mod
$p$ values using
$$\tau(p) \equiv 1 + p^{11} \pmod{691}.$$

Here we provide a very simple PARI/GP implementation of tau function which takes as input a prime number.
\begin{verbatim}
tau(p) = {
  tmax=floor(2*sqrt(p)); s10=0;
  for(t=1, tmax, s10+=(t^10)*qfbhclassno(4*p-t*t));
  return (p+1)*(42*p^5-42*p^4-48*p^3-27*p^2-8*p-1)-s10;
}
\end{verbatim}

\section{Results}
Our first significant result was the finding of a new solution to the equation $\tau(p) \equiv -1$ (mod $p$) for prime $p = 692881373$, on September 6 2009. The only other known solution was 5807. 

\begin{tabular}{rl}
$ \tau (692881373)$ & $= -2134035447986554588547794684277099135915023500378 $\\
& $= -2 \cdot 3 \cdot 16183 \cdot 45826933447 \cdot 479590473338104688515299840883663 $
\end{tabular}\\
\\
We checked the congruences modulo $ 2^{12} $, $ 3^7 $, $ 5^3 $, 7, 23 and 691. 

Our main result is the discovery of a new prime $p=7758337633$ such that $\tau(p)$ is divisible by $p$, on March 15 2010. Indeed we found that

\begin{tabular}{rl}
$ \tau (7758337633)$ & $ = 3634118031125820057253378550628821747860472052772622882 $\\
& $ = 2 \cdot 31481 \cdot 7758337633 \cdot 7439638579196209777834920016764711229817 $.
\end{tabular}\\
\\
We checked the congruences modulo $ 2^{11} $, $ 3^6 $, $ 5^3 $, 7, 23 and 691. 
The latter result was announced on the mailing list NMBRTHRY of North Dakota HECN, and added to the sequence \seqnum{A007659}.

Assuming the correctness of all computations, our study shows that 2, 3, 5, 7, 2411 and 7758337633 are the only prime solutions to the equation $\tau(p) \equiv 0$ (mod $p$) less than $ 10^{10} $.

Moreover, we give all solutions to the equations $\tau (p) \equiv q$ (mod $p$) where $ |q| \leq 100 $, and $p$ a prime, $10^8 < p < 10^{10}$ (Table \ref{tab_pepites}).

\begin{table} [H]
\begin{center}
\begin{tabular}{|rr|rr|rr|rr|rr|}
\hline
 $p$ & $q$ &  $p$ & $q$ & $p$ & $q$ & $p$ & $q$ & $p$ & $q$ \\
\hline
108306623 &  64 &	249317993 &  47 &	423822691 &  28 &	1052035739 & -84 &	2491075429 &  14 \\
117138737 & -91 &	254519539 &  47 &	459728417 & -12 &	1078801037 & -77 &	3586202561 &  68 \\
117718969 & -40 &	261550153 &  56 &	463203047 &  80 &	1155439651 &  25 &	3801305863 & -26 \\
138395681 & -18 &	315713759 &  31 &	658562939 &  24 &	1321424171 &  85 &	3981602959 & -12 \\
138576103 &  57 &	316254821 &  21 &	663781537 &  -7 &	1322068141 & -89 &	5029365641 & -94 \\
149929751 & -87 &	322980089 & -58 &	692881373 &  -1 &	1433436523 & -12 &	5267222287 & -53 \\
153096653 & -36 &	332139911 & -15 &	734238613 & -18 &	1500848449 &  35 &	5825117047 & -21 \\
165453721 & -31 &	337092443 &  76 &	781380671 & -95 &	1818264659 & -20 &	6606460087 & -55 \\
196770907 &   8 &	340972243 &  14 &	825440597 & -66 &	1854155309 &  55 &	7076349307 &  33 \\
217732523 & -97 &	349624213 &  58 &	1001976247 &  54 &	1932306841 &  19 &	7289754107 &  10 \\
221148401 &  49 &	359657993 & -42 &	1044587639 & -92 &	2338478239 &  93 &	7758337633 &   0 \\
\hline
\end{tabular}
\caption{List of pairs $(p,q)$ verifying $\tau (p) \equiv q$ (mod $p$), $|q| \leq 100$, $p$ is prime, $10^8 < p < 10^{10}$}
\label{tab_pepites}
\end{center}
\end{table}
Finally, we recall that the equation $\tau(p) \equiv 1$ (mod $p$) has known solutions 11, 23 and 691. There are no other solutions up to $10^{10}$.

\section{Acknowledgements}

We would like to thank 
Oliver Atkin,
Roman Bayon, Claude Chaunier, Henri Cohen, Thomas Papanikolaou,
Jean-Sebastien Sereni and Paul Zimmermann
for their helpful discussions.
Our new solution was
verified independently by David Harvey on March 17 2010. His
computation took about 100 CPU hours using the zn\_poly library on 10
Opteron cores.


\begin{thebibliography}{99}
 
\bibitem{Abr72}
M. Abramowitz and I. Stegun, \textit{Handbook of Mathematical Functions}, Tenth Printing, National Bureau of Standards, 1972.

\bibitem{Ber99}
B. Berndt and K. Ono, Ramanujan's unpublished manuscript on the partition and tau functions with proofs and commentary, \textit{S\'em. Lothar. Combin.} \textbf{42} (1999), 1--63. 

\bibitem{Cha06}
D. Charles, Computing the Ramanujan tau function, \textit{Ramanujan J.} \textbf{11} (2006) 221--224.

\bibitem{Cho05}
Y. Choie, W. Kohnen and K. Ono, Linear relations between modular form coefficients and non-ordinary primes, \textit{Bull. Lond. Math. Soc.} \textbf{37} (2005) 335--341.

\bibitem{Coh75}
H. Cohen, Sums involving the values at negative integers of L-functions of quadratic characters, \textit{Math. Ann.} 
\textbf{3} (1975) 271--285. 

\bibitem{Coh93}
H. Cohen, \textit{Computational Algebraic Number Theory}, Springer-Verlag, 1993. 

\bibitem{Cou10}
J.-M. Couveignes and B. Edixhoven, \textit{Computational Aspects of Modular Forms and Galois Representations}, preprint available at http://arxiv.org/abs/math/0605244.

\bibitem{Gou97}
F. Gouv\^ea, Non-ordinary primes: a story, \textit{Experiment. Math.} \textbf{6} (1997) 195--205. 

\bibitem{Gra89}
R. L. Graham, D. E. Knuth, and O. Patashnik, \textit{Concrete Mathematics}, Addison-Wesley, 1989.

\bibitem{Hog76}
V. E. Hoggatt and M. Bicknell, Catalan and related sequences arising from inverses of Pascals triangle matrices, \textit{Fibonacci Quart.} \textbf{14} (1976) 395--404.

\bibitem{Lan00}
W. Lang, On polynomials related to powers of the generating function of Catalan's numbers, \textit{Fibonacci Quart.} \textbf{38} (2000) 408--419. 

\bibitem{Mor20}
L. J. Mordell,  On Mr. Ramanujan's empirical expansions of modular functions, \textit{Proc. Cambridge Philos. Soc. 19}, 1920, pp.\ 117--124. 

\bibitem{Mur07}
V. K. Murty, A variant of Lehmer's conjecture, \textit{J. Number Theory} \textbf{123} (2007) 80--91.

\bibitem{New72}
M. Newman, \textit{A table of $\tau$(p) modulo p, p prime, $3 \leq p \leq 16067$}, National Bureau of Standards, 1972.

\bibitem{Pap05}
M. Papanikolas, A formula and a congruence for Ramanujan's $\tau$-function, \textit{Proc. Amer. Math. Soc.} \textbf{134} (2005) 333--341.

\bibitem{Rad00}
C. Radoux, Addition formulas for polynomials built on classical combinatorial sequences, \textit{J. Comput. Appl. Math.} \textbf{115} (2000) 471--477.

\bibitem{Ram16}
S. Ramanujan, On certain arithmetical functions, \textit{Trans. Cambridge Philos. Soc. 22}, 1916, pp.\ 159--184. 

\bibitem{Rib96}
P. Ribenboim, \textit{The New Book of Prime Number Records}, Springer-Verlag, 1996.

\bibitem{Ser67}
J.-P. Serre, Une interpr\'etation des congruences relatives \`a la fonction $\tau$ de Ramanujan, \textit{S\'eminaire Delange-Pisot-Poitou}, 1967/1968, ex. 14.

\bibitem{Ser70}
J.-P. Serre, \textit{Cours d'Arithm\'etique}, Presses Univ. France, 1970.

\bibitem{Ser72}
J.-P. Serre, Congruences et formes modulaires, \textit{S\'em. Bourbaki},
(1971/1972), 319--338. 

\bibitem{Ser88}
J.-P. Serre, Private correspondence, 1988/1989.

\bibitem{Sha76}
L. W. Shapiro, A Catalan triangle, \textit{Discrete Math.} \textbf{14} (1976) 83--90.

\bibitem{Slo95}
N. J. A. Sloane and S. Plouffe, \textit{The Encyclopedia of Integer Sequences}, Academic Press, 1995.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: 
Primary 11F33.

\noindent \emph {Keywords:} Tau function, non-ordinary primes, Eichler-Selberg trace formula, Hurwitz sums, Catalan triangle, Ramanujan function, computation record.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000108},
\seqnum{A000245},
\seqnum{A000344},
\seqnum{A000594},
\seqnum{A002057},
\seqnum{A003517},
\seqnum{A007659},
\seqnum{A008315},
\seqnum{A009766},
\seqnum{A058305},
\seqnum{A058306}, and
\seqnum{A108786}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received May 7 2010;
revised version received  June 30 2010.
Published in {\it Journal of Integer Sequences}, July 9 2010.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}