# 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!

-
I don't have time to write out a full solution, but think about the Chinese remainder theorem. –  Qiaochu Yuan May 22 '11 at 14:35
$n=3$ is a counterexample, no? –  Gerry Myerson May 23 '11 at 0:49

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.

-
is $q$ always a prime, or any kind of odd number? –  IBS May 26 '11 at 8:38
@IBS: Almost any kind of odd number. The $3$'s have been stripped out in each part, for special consideration. So $q$ in each part is any odd number not divisible by $3$. –  André Nicolas May 26 '11 at 14:11

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.

-
Thanks, but it's still not enough... it doesn't tell me what happens in all the rest of the cases (i.e $n$ isn't 1 or 7 modulo 8) –  IBS May 22 '11 at 14:30