0

I want to get an upper bound for the smallest $a$ and a natural number $n$ such that the Jacobisymbol is $$ \big(\frac{a}{n}\big) = -1. $$

I know the following: Let $p>3$ be prime and let $a_p$ be the smallest quadratic non-residue mod $p$. Then $$ a_p \leq \begin{cases} 0{,}9\cdot p^{\frac{1}{4}}\cdot \ln(p), \text{ for } n\equiv 1 \pmod 4, \\ 1{,}1\cdot p^{\frac{1}{4}}\cdot \ln(p), \text{ for } n\equiv 3 \pmod 4. \end{cases} $$

Furthermore, I know that for a number $n$ there exists an $a$ such that $ \big(\frac{a}{n}\big) = -1 $ if and only if $n$ is not a perfect square.

I suppose that this is the same for composite $n$. My thoughts for the proof (here only for $\equiv 1\pmod 4$). Let $n$ be a natural number with $n\equiv 1\pmod 4$. Furthermore let $a_p$ be the smallest element such that the Jacobisymbol $$ \big(\frac{a_p}{n}\big) = -1. $$ If $n$ is prime, we get $a_p \leq 0{,}9\cdot n^{\frac{1}{4}}\cdot \ln(n)$ right away.

Now let $n$ be composite with its prime decomposition $ n = \prod\limits_{p\in\mathbb P} p^{\alpha_p}. $ To clearify a point an advance: It is possible that this number has prime divisors $p\equiv 3\pmod 4$. That's why I will use the formula with $1,{1}\cdot\dots$ once.

Then we get for the Jacobisymbol $$ -1 = \big(\frac{a_p}{n}\big) = \prod\limits_{p\in\mathbb P}\big(\frac{a_p}{p}\big)^{\alpha_p}. $$

Here I am stuck. I could have a look at the greatest prime divisor $p_m$. But it might be, that the smallest quadratic non-residue for this divisor is very small, whereas it is very big for smaller divisors. So I cannot conclude that is smaller than $ 1{,}1\cdot p^{\frac{1}{4}}\cdot \ln(p) $ for all $p$.

Lereu
  • 424
  • 1
    If you want $a$ to be a quadratic nonresidue modulo $n$, then it suffices for it to be a quadratic nonresidue modulo any prime dividing $n$. – Gerry Myerson Jan 25 '24 at 12:06
  • @GerryMyerson Ok, but I want to the Jacobisymbol to be $-1$. Consider $n = 11\cdot 13\cdot 23$. Then the number $2$ is a quadratic nonresidue mod n, and the legendre symbols $(2,11) = (2,13) = -1$ and $(2,23) = 1$. But the Jacobisymbol $(2,n) = 1$. – Lereu Jan 25 '24 at 12:26
  • The title of your question says "smallest quadratic nonresidue", and the first sentence says "smallest quadratic nonresidue". I know you want the Jacobi symbol to be negative, but I don't know why. It seems to me to be much more significant that $2$ is a nonresidue modulo $15$, than that the Jacobi symbol is $+1$. – Gerry Myerson Jan 25 '24 at 21:11
  • 1
    @GerryMyerson You are totally right, I am sorry. I edited my question. – Lereu Jan 26 '24 at 08:49
  • https://oeis.org/A112046 is a tabulation of something close to what you want. Unfortunately, it says nothing about estimates. – Gerry Myerson Jan 26 '24 at 09:06

0 Answers0