Two succeeding integers in $\left(\mathbb{Z}/n\mathbb{Z}\right)^{*}$ for an odd n, and the Jacobi symbol of the latter one Given an odd integer $n$, I want to find out if there exists two succeeding integers, $1\leq m-1<m\leq n-1$ s.t both are invertible (i.e $m,m-1\in \left(\mathbb{Z}/n\mathbb{Z}\right)^{*}$) and also $\left(\frac{m}{n}\right)=1$ when $\left(\frac{m}{n}\right)$ is the Jacobi symbol.
For example: if i take $n=9$ and $m=8\in \left(\mathbb{Z}/n\mathbb{Z}\right)^{*}$ then i get $m-1=7\in \left(\mathbb{Z}/n\mathbb{Z}\right)^{*}$ and also $\left(\frac{m}{n}\right)=1$ which is exactly what i want. 
Is there a criterion for a given odd $n$, to find such an $m$, or even just to know that it exists?
Thanks!
 A: The argument that follows is probably a variant of what Qiaochu Yuan had in mind.  We will use the compact notation $(a/b)$ for the Jacobi symbol.
It is clear that $n=3$ does not work.  A natural candidate for $n>3$ is $m=4$. Since it is a perfect square, it does the job unless $3$ divides $n$.  So if $n>1$ and  $3$ does not divide $n$, there is a simple $m$ with the desired property.  So from now on we only consider $n$ that are divisible by $3$.
Let $3^k$ be the greatest power of $3$ that divides $n$.  Suppose that $k$ is odd, and $n=3^kq^2$.   Our $m$ must be congruent to $2$ modulo $3$.  Thus $(m/3^k)=-1$, and therefore $(m/q^2)=1$, for any $m$ relatively prime to $q$.  It follows that in this case there is no $m$ that works.  We will show that in all other cases, there is an $m$ that works.
Look first at the case $n=3^kq$, where $3^k$ is the largest power of $3$ that divides $n$, $k$ is even, and $q \ne 1$.  Choose $m \equiv 2 \pmod{3}$, and $m \equiv 4 \pmod{q}$.  There is such an $m$ with $1<m<n$ by the Chinese Remainder Theorem.  It is easy to see that $m$ and $m-1$ are relatively prime to $n$, and that $(m/n)=1$.  If $q=1$ the situation is even easier.
So now we deal with $n=3^kq$, where $(3,q)=1$, $k$ is odd, and $q$ is not a perfect square.  Let $m \equiv 2 \pmod{3}$.  Then $(m/3^k)=-1$.  Let $p$ be a prime that divides $q$ to an odd power (there is such a $p$ since $q$ is not a perfect square).  Choose any quadratic non-residue $a$ of $p$.  Let $q=p^s r$, where $r$ is not divisible by $p$.  If $r=1$, use the Chinese Remainder Theorem to produce $m$ in the right range congruent to $2$ modulo $3$ and to $a$ modulo $p$.  If $r \ne 1$, use the Chinese Remainder Theorem to produce an $m$ in the right range with $m$ congruent to $2$ modulo $3$, to $a$ modulo $p$, and to $4$ modulo $r$.  Then $(m/n)=1$ and $m-1$ is relatively prime to $n$, so we are finished.  
A: It might not be exactly what you want, but since 1 always has Jacobi symbol 1, we have a solution with $m=2$ whenever 2 has Jacoby symbol 1, i.e. when $n$ is 1 or 7 modulo 8.
