6
$\begingroup$

In A Multimodular Algorithm for Computing Bernoulli Numbers, Harvey uses the following congruence for Bernoulli numbers:

$$B_k \equiv \frac{k}{1-c^k} \sum_{x=1}^{p-1} x^{k-1} h_c(x)\quad(\text{mod}\ p)$$ where $p \ge 5$ is prime; $k$ is an even integer satisfying $2 \le k \le p - 3$; $c$ is an integer satisfying $0 < c < p$ and $c^k \not\equiv 1 \pmod p$, and $$h_c(x) := \frac{(x\,\text{mod}\,p) - c(x / c\,\text{mod}\,p)}{p} + \frac{c-1}{2}$$ He says that this follows by reading Theorem 2.3 in Chapter 2 of Lang's Cyclotomic Fields 1 modulo $p$. The theorem in question is stated by Lang like this: $$\frac{1}{k} B_k = \frac{1}{1-c^k} \int_{\mathbf{Z}_p} x^{k-1}\ \text{d}E_{1,c}(x)$$ Now unfortunately I don't know anything about $p$-adic analysis, so this is a bit beyond me.

I was wondering if there is a more direct proof of the congruence Harvey uses that does not rely on $p$-adic analysis.

$\endgroup$
1
  • $\begingroup$ Indeed I did. Thanks! $\endgroup$ Commented Aug 25, 2022 at 12:08

1 Answer 1

5
$\begingroup$

$\newcommand{floor}[1]{\left\lfloor #1 \right\rfloor}$

I doubt that this answer is still useful to you, since this question is one year old. Anyway, I'll leave the answer here, and maybe it will help someone (or not).

Your congruence is, modulo details, a special case of a congruence due to Voronoi. Let $k$ be an even positive integer, and write $B_k=\dfrac{N_k}{D_k}$ in lowest terms with $D_k>0$. Let $a$ and $n$ be coprime positive integers. Voronoi congruence states [2, Proposition 9.5.20]
that \begin{equation} \tag{1}\label{voronoin} (a^k-1)N_k\equiv D_kka^{k-1}\sum_{x=1}^{n-1} x^{k-1}\floor{\frac{ax}{n}} \quad(\mathrm{mod}\ n), \end{equation} where $\floor{x}$ is the usual floor function. Note that both sides are integers.

Let $n=p$ a prime number, and suppose $D_k$ is not divisible by $p$. Thus $p\ge5$ since $D_k$ is always divisible by $6$, by Clausen-von Staudt which states that [2, Corollary 9.5.15] $$D_k=\prod_{(\ell-1)\mid k}\ell,$$ the product being over all primes $\ell$ such that $\ell-1$ divides $k$. Then \eqref{voronoin} can be written as \begin{equation} \tag{2}\label{voronoip} (a^k-1)B_k\equiv ka^{k-1}\sum_{x=1}^{p-1} x^{k-1}\floor{\frac{ax}{p}} \quad(\mathrm{mod}\ p). \end{equation}

Let $c$ be a positive integer (coprime to $p$) such that $ac\equiv 1 \ (\mathrm{mod}\ p)$, and for simplicity write $a=c^{-1}$, being an inverse modulo $p$. (Obviously $c$ can be chosen such that $0<c<p$ as in your statement.) Multiplying both sides in \eqref{voronoip} by $c^k$ we obtain \begin{equation} \tag{3}\label{voronoic} (1-c^k)B_k\equiv k\sum_{x=1}^{p-1} x^{k-1}c\floor{\frac{c^{-1}x}{p}} \quad(\mathrm{mod}\ p). \end{equation} Now, $cc^{-1}=1+pN$ for some integer $N$, and we use this as follows to relate the summands with $h_c(x)$. For $1\le x\le p-1$, so that $x=\left(x \, \mathrm{mod}\, p\right)$, we have \begin{align*} c\floor{\frac{c^{-1}x}{p}} &=\frac{cc^{-1}x}{p}-\frac{c\left(c^{-1}x \; \mathrm{mod}\, p\right)}{p} =\frac{x}{p}+Nx-\frac{c\left(c^{-1}x \; \mathrm{mod}\, p\right)}{p}\\ &=h_c(x)+Nx-\frac{c-1}{2}, \end{align*} so that \eqref{voronoic} becomes \begin{equation} \tag{4}\label{voronoitemp} (1-c^k)B_k\equiv k\sum_{x=1}^{p-1} x^{k-1}h_c(x)+ kN\sum_{x=1}^{p-1}x^{k} -k\frac{c-1}{2}\sum_{x=1}^{p-1}x^{k-1} \quad(\mathrm{mod}\ p). \end{equation} To get rid of the last two sums, recall that for all $q$ not divisible by $p-1$ one has [1, Lemma 2.5.1] \begin{equation} \notag%\tag{4}\label{modp3} \sum_{x=1}^{p-1}x^{q}\equiv 0 \quad(\mathrm{mod}\ p). \end{equation} Now we use your hypothesis $2\le k\le p-3$; then both $k-1$ and $k$ are not divisible by $p-1$, and the above implies that the last two sums in \eqref{voronoitemp} are zero. Also under this hypothesis, Clausen-von Staudt implies that $p$ does not divide $D_k$, which was used in \eqref{voronoip}. If moreover $c^k \not\equiv 1 \pmod p$ we finally arrive to your congruence \begin{equation} \notag%\tag{4}\label{modp3} B_k\equiv \frac{k}{1-c^k}\sum_{x=1}^{p-1} x^{k-1}h_c(x)\quad(\mathrm{mod}\ p). \end{equation}

[1] Cohen, Henri Number theory. Vol. I. Tools and Diophantine equations. Graduate Texts in Mathematics, 239. Springer, New York, 2007.

[2] Cohen, Henri Number theory. Vol. II. Analytic and modern tools. Graduate Texts in Mathematics, 240. Springer, New York, 2007.

(The original article by Voronoi can be accesed here. His congruence appears as Corollary IV in page 146.)

$\endgroup$
1
  • 1
    $\begingroup$ That is helpful. The pointer to Cohen's book was tremendously helpful. Thanks! This wasn't for anything super important, just a small side project of mine. So it doesn't really matter that I had to wait a bit for an answer. $\endgroup$ Commented Dec 12, 2023 at 20:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .