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