MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?
share|cite|improve this question
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 at 22:23
I liked your formula for $(T/N)$ a lot, and I provided a proof below. – GH from MO Feb 13 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 ? – user1952009 Feb 23 at 2:26
up vote 20 down vote accepted

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}.$$

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.