How to compute product of Jacobi symbols

Question

Let $m>1$ be odd. I want to find the product for:

$$\prod_{\substack{(a,m)=1 \\ 1 \leq a \leq m}} \left(\frac{a}{m}\right)$$ where $\left(\frac{a}{m}\right)$ is a Jacobi symbol.

I know that each of these Jacobi symbols will have a value of either $+1$ or $-1$ depending on whether $a$ is a Quadratic residue modulo $m$ or not. So the product, consequently, has to be $+1$ or $-1$. However, I'm not sure how I can get started on counting how many of those $a$ will be quadratic residues. Any help on this?

Answer 1

Let $m=p_1^{\alpha _2}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ be the prime factorization of $m$. Then the Jacobi symbol $$\left(\frac am\right)=\left({\frac a{p_1}}\right)^{\alpha_1}\left({\frac {a}{p_2}}\right)^{\alpha _2}\cdots \left({\frac {a}{p_k}}\right)^{\alpha _k}\tag{***}\label{***}$$

There are two cases.

• $m$ has at least two distinct prime factors.

  We can reduce each $(\frac a{p_i})$ to $(\frac {a\%p_i}{p_i})$.

  Let us find, after the reduction above, how many times the factor $(\frac 1{p_1})$ appears on the right hand side of $\eqref{***}$ when $1\le a\le m$, $(a,m)=1$.

  By Chinese remainder theorem, the map $a\mapsto a\% \frac m{{p_1}^{\alpha_1}}$ from $\{a\mid 1\le a\le m, a\equiv_{p_1}1,(a,m)=1\}$ to $\{b\mid 1\le b\le\frac m{{p_1}^{\alpha_1}}, \left(b, \frac m{{p_1}^{\alpha_1}}\right)=1\}$ is a bijection. That means $(\frac 1{p_1})$ appears $\alpha_1\phi(\frac m{{p_1}^{\alpha_1}})$ times, where $\phi$ is the Euler totient function.

  Since $\frac m{{p_1}^{\alpha_1}}$ has at least one odd prime factor, $\phi(\frac m{{p_1}^{\alpha_1}})$ is even. So the product of all $(\frac1{p_1})$ is $1$, even if we pretend $(\frac1{p_1})=-1$.

  Similarly, the product of the same factors for any other factor is $1$. Hence, the entire product is $1$.

• $m$ has only one prime factor, say $m=p^\alpha$.
  For $a$ in each interval $[pi+1, pi+p-1]$, where $0\le i\le \frac mp-1$, half of them will make $(\frac ap)=1$ and the other half will make $(\frac ap)=-1$. Hence the entire product is $$ 1^{\alpha p^{\alpha-1}\frac{p-1}2}(-1)^{\alpha p^{\alpha-1}\frac{p-1}2}$$ which is

  • $1$ if $p\equiv_41$ or $\alpha$ is even
  • $-1$ if $p\equiv_43$ and $\alpha$ is odd.

To summarize, the product is $-1$ when $m$ is an odd power of a prime number that is $\equiv_43$, $1$ otherwise.