1
$\begingroup$

I have asked a similar question here before, and received a nice answer. I think that the next question here is equivalent, but can't seem to be able to prove it. Here goes:

Given an odd $n$, I want to find an $0\leq m\leq n-1$ s.t $m\in\left(\mathbb{Z}/n\mathbb{Z}\right)^{*}$ (i.e, $m$ is invertible modulu $n$), and also $\left(1-m^{-1}\right)\in\left(\mathbb{Z}/n\mathbb{Z}\right)^{*}$ and $\left(\frac{m}{n}\right)=1$ when $\left(\frac{m}{n}\right)$ is the Jacobi symbol.

I can prove that if we disregard the Jacobi symbol requirement, this is equivalent to finding to succeeding invertible numbers modulu $n$. But when we throw the Jacobi symbol in to the equation, I'm not sure if this is the same as my earlier question. If it is, I would greatly appreciate a proof. If not, a new answer :).

Thanks alot!

2 Answers 2

3

For any $m \in (\mathbb{Z}/n\mathbb{Z})^\star$, since $m^{-1} = m \times (m^{-1})^2$, $\left(\frac{m}{n}\right)=\left(\frac{m^{-1}}{n}\right)$. Furthermore, $-1$ is invertible, so it is the same thing to find a square residue $m$ with $1-m^{-1}$ invertible than to find a square residue $m^{-1}$ with $m^{-1}-1$ invertible.

2

$1 - m^{-1} = (m-1)/m$. $m$ and $1 - m^{-1}$ are units if and only if $m$ and $m-1$ are units.