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?


  • $\begingroup$ I don't have time to write out a full solution, but think about the Chinese remainder theorem. $\endgroup$ – Qiaochu Yuan May 22 '11 at 14:35
  • $\begingroup$ $n=3$ is a counterexample, no? $\endgroup$ – 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.

  • $\begingroup$ is $q$ always a prime, or any kind of odd number? $\endgroup$ – IBS May 26 '11 at 8:38
  • $\begingroup$ @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$. $\endgroup$ – 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.

  • $\begingroup$ 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) $\endgroup$ – IBS May 22 '11 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.