# Elementary congruences and L-functions

In a recent article, Emmanuel Lecouturier proves a generalization of the following surprising result: for a Mersenne prime $N = 2^p - 1 \ge 31$, the element $$S = \prod_{k=1}^{\frac{N-1}2} k^k$$ is a $p$-th power modulo $N$, and observed that he did not know an elementary proof. Neither do I.

Numerical experiments suggest that $s_p$ is actually a $6p$-th power modulo $N$. I can't even see why it is a quadratic residue, i.e., why the following result (not proved in the article cited) should hold: $$T = \prod_{k=1}^{\frac{N+1}4} (2k-1)$$ is a square mod N.

For arbitrary primes $N \equiv 3 \bmod 4$, the following seems to hold: $$\Big(\frac{T}{N} \Big) = \begin{cases} - (-1)^{(h-1)/2} & \text{ if } N \equiv 3 \bmod 16, \\ - 1 & \text{ if } N \equiv 7 \bmod 16, \\ (-1)^{(h-1)/2} & \text{ if } N \equiv 11 \bmod 16, \\ + 1 & \text{ if } N \equiv 15 \bmod 16, \end{cases}$$ where $h$ is the class number of the complex quadratic number field with discriminant $-N$. This suggests a possible proof using L-functions (i.e. using methods in (Congruences for L-functions, Urbanowicz, K.S. Williams) and explains the difficulty of finding an elementary proof.

My questions:

1. Is this congruence for $(T/N)$ known?
2. How would I start attacking this result using known results on L-functions?
• I think you mean to have $(h-1)/2$ in the exponents instead of $h$. If $N \equiv 3 \pmod{4}$, the class number of $\mathbb{Q}(\sqrt{-N})$ is odd. – Jeremy Rouse Feb 12 '16 at 22:23
• I liked your formula for $(T/N)$ a lot, and I provided a proof below. – GH from MO Feb 13 '16 at 3:56
• the Lucas-Lehmer test suggests that $3$ is a generator of $(\mathbb{Z}_N,\times)$, if you suppose it is, isn't $\prod_{k \le (N-1)/2} k^k$ simplified ? – reuns Feb 23 '16 at 2:26

1. First we show that $$\left(\frac{T}{N}\right) = \begin{cases} - (-1)^{(h-1)/2} & \text{ if } N \equiv 3 \bmod 16, \\ (-1)^{(h-1)/2} & \text{ if } N \equiv 11 \bmod 16. \\ \end{cases}$$ Consider the sets $$A_0:=\{1,2,\dots,\tfrac{N-1}{2}\},\quad A_1:=\{1,3,\dots,\tfrac{N-1}{2}\},\quad A_2:=\{2,4,\dots,\tfrac{N-3}{2}\},$$ $$A_3:=\{1,2,\dots,\tfrac{N-3}{4}\},\quad A_4:=\{\tfrac{N+1}{4},\tfrac{N+5}{4},\dots,\tfrac{N-1}{2}\}.$$ Consider also the corresponding character sums $$S_i:=\sum_{a\in A_i}\left(\frac{a}{N}\right),\qquad i=0,1,2,3,4.$$ Modulo $N$, we have $2A_3=A_2$ and $-2A_4=A_1$. Therefore, $S_3=-S_2$ and $S_4=S_1$, and hence $S_1-S_2=S_3+S_4=S_0$. But also $S_1+S_2=S_0$, hence $S_1=S_0$ and $S_2=0$. On the other hand, it is known that $S_0=3h$, see e.g. Theorem 70 in Fröhlich-Taylor: Algebraic number theory. This means that $S_1=3h$, i.e. the number of quadratic nonresidues in $A_1$ equals $$n=\frac{N+1}{8}-\frac{3h}{2}=\frac{N+5}{8}-2h+\frac{h-1}{2}.$$ We conclude $$\left(\frac{T}{N}\right)=(-1)^n=(-1)^{(N+5)/8}(-1)^{(h-1)/2}.$$ This is the claimed formula (with Jeremy Rouse's correction).

2. Now we show that $$\left(\frac{T}{N}\right) = \begin{cases} - 1 & \text{ if } N \equiv 7 \bmod 16, \\ + 1 & \text{ if } N \equiv 15 \bmod 16. \end{cases}$$ We proceed as before, but this time we get $S_3=S_2$ and $S_4=-S_1$, so that $S_2-S_1=S_3+S_4=S_0$. Together with $S_2+S_1=S_0$, this yields $S_1=0$ and $S_2=S_0$. Hence the formula for $n$ simplifies to $n=(N+1)/8$, and we conclude $$\left(\frac{T}{N}\right)=(-1)^n=(-1)^{(N+1)/8}.$$

I answer only for the $3$-part of your question (I have to think more for the $2$-part).

Let $N$ be a prime $\equiv 1 \text{ (mod } 3\text{)}$. Let $\text{log} : (\mathbf{Z}/N\mathbf{Z})^{\times} \rightarrow \mathbf{F}_3$ be a discrete logarithm. We have the following identity: $$\sum_{k=1}^{\frac{N-1}{2}} k \cdot \log(k) \equiv \frac{-\log(2)}{8} \cdot \frac{N-1}{3} \text{ (mod } 3\text{)}$$

The idea is to rewrite the left hand side as a sum over $(\mathbf{Z}/N\mathbf{Z})^{\times}$ in terms of Bernoulli polynomials (which, I think, is an old idea of my advisor Loïc Merel). The proof is the following (essentially Lemme $11$ of my preprint). Let $f : \mathbf{R} \rightarrow \mathbf{\mathbf{R}}$ be the $1$-periodic function defined by $f(x) = x$ if $x \in [0,\frac{1}{2}]$, $f(\frac{1}{2}) = \frac{1}{4}$ and $f(x)=0$ if $x \in ]\frac{1}{2},1[$. Let $E(x)$ be the integer part of $x$. Let $\overline{B_2}(x) = (x-E(x))^2-(x-E(x))$ and $\overline{B}_1(x) = (x-E(x))-\frac{1}{2}$ (except that $\overline{B}_1(0):=0$) be (essentially) the second and first periodic Bernoulli functions respectively. Then we have : $$f(x) = \frac{1}{4}\cdot \overline{B}_2(2x) - \overline{B}_2(x) + \frac{1}{2}\cdot \overline{B}_1(x-\frac{1}{2})$$ (to find such identities systematically, it is convenient to compute the Fourier coefficients of $f$ and remark that the Bernoulli polynomials have nice Fourier coefficients).

Then we find : $$\sum_{k=1}^{\frac{N-1}{2}} k\cdot \log(k) \equiv \sum_{k \in (\mathbf{Z}/N\mathbf{Z})^{\times}} f(\frac{k}{N})\cdot \log(k) \text{ (mod } 3\text{)}$$ which you can simplify greatly with the Bernoulli functions (the $\log(2)$ comes from $2x$ inside $\overline{B_2}(2x)$).

In particular if $N \equiv 1 \text{ (mod } 9\text{)}$ then your $S$ is a $3$-rd power. If $N = 2^p-1 \geq 31$ is a Mersenne prime , then $\log(2) \equiv 0 \text{ (mod } 3\text{)}$ since $\log(2^p) \equiv p\log(2) \equiv0 \text{ (mod } 3\text{)}$ and $p>3$.

Although I didn't state it, I think I can also prove the following regarding the $3$-th power part: if $N = a^2-ab+b^2$ is a prime $\equiv 1 \text{ (mod } 9\text{)}$ then $b^{-2}\cdot(ab^2+ba^2)$ is a $3$-rd power modulo $N$. It follows from the same methods as in the preprint.