Two succeeding integers in $\left(\mathbb{Z}/n\mathbb{Z}\right)^{*}$ for an odd n, and the Jacobi symbol of the latter one

Given a weird integer $n$, I intend to figure out if there exists 2 doing well 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)^{*}$) as well as additionally $\left(\frac{m}{n}\right)=1$ when $\left(\frac{m}{n}\right)$ is the Jacobi icon.

As an example: if i take $n=9$ and also $m=8\in \left(\mathbb{Z}/n\mathbb{Z}\right)^{*}$ after that i get $m-1=7\in \left(\mathbb{Z}/n\mathbb{Z}\right)^{*}$ as well as additionally $\left(\frac{m}{n}\right)=1$ which is specifically what i desire.

Exists a standard for an offered weird $n$, to find such an $m$, or perhaps simply to recognize that it exists?

Many thanks!

1
2022-06-07 14:32:58
Source Share
Answers: 2

The argument that adheres to is possibly a version of what Qiaochu Yuan desired. We will certainly make use of the portable symbols $(a/b)$ for the Jacobi icon.

It is clear that $n=3$ does not function. An all-natural prospect for $n>3$ is $m=4$. Given that it is an excellent square, it gets the job done unless $3$ separates $n$. So if $n>1$ and also $3$ does not separate $n$, there is a straightforward $m$ with the wanted building. So from currently on we just take into consideration $n$ that are divisible by $3$.

Allow $3^k$ be the best power of $3$ that separates $n$. Intend that $k$ is weird, and also $n=3^kq^2$. Our $m$ has to be conforming to $2$ modulo $3$. Hence $(m/3^k)=-1$, and also consequently $(m/q^2)=1$, for any kind of $m$ reasonably prime to $q$. It adheres to that in this instance there is no $m$ that functions. We will certainly show that in all various other instances, there is an $m$ that functions.

Look first at the instance $n=3^kq$, where $3^k$ is the biggest power of $3$ that separates $n$, $k$ is also, and also $q \ne 1$. Pick $m \equiv 2 \pmod{3}$, and also $m \equiv 4 \pmod{q}$. There is such an $m$ with $1<m<n$ by the Chinese Remainder Theorem. It is very easy to see that $m$ and also $m-1$ are reasonably prime to $n$, which $(m/n)=1$. If $q=1$ the scenario is also less complicated.

So currently we manage $n=3^kq$, where $(3,q)=1$, $k$ is weird, and also $q$ is not an excellent square. Allow $m \equiv 2 \pmod{3}$. After that $(m/3^k)=-1$. Allow $p$ be a prime that separates $q$ to an weird power (there is such a $p$ given that $q$ is not an excellent square). Pick any kind of square non - deposit $a$ of $p$. Allow $q=p^s r$, where $r$ is not divisible by $p$. If $r=1$, make use of the Chinese Remainder Theorem to generate $m$ in the appropriate array conforming to $2$ modulo $3$ and also to $a$ modulo $p$. If $r \ne 1$, make use of the Chinese Remainder Theorem to generate an $m$ in the appropriate array with $m$ conforming to $2$ modulo $3$, to $a$ modulo $p$, and also to $4$ modulo $r$. After that $(m/n)=1$ and also $m-1$ is reasonably prime to $n$, so we are ended up.

2
2022-06-07 16:12:40
Source

It could not be specifically what you desire, yet given that 1 constantly has Jacobi icon 1, we have a remedy with $m=2$ whenever 2 has Jacoby icon 1, i.e. when $n$ is 1 or 7 modulo 8.

1
2022-06-07 14:55:59
Source