given an odd prime n, is there an simple or elegant way to solve an equation
A + modinv(A,n) mod n == -1
whereby modinv(A,n) is the modular multiplicative inverse of A modulo n (i.e. A * modinv(A,n) mod n == 1).
Stated in other terms, the equation sums up A with its modinv in order to yield n-1. The fact that the equation mixes A with its inverse poses a difficulty I am unable to surpass.
How can I identify such As?
Thank You in advance for any hint in useful direction.
You want to solve $$ x + x^{-1} \equiv -1 \mod p $$ for some odd prime p. This is equivalent to $$ x^2 + x + 1 \equiv 0 \mod p $$ where we have multiplied both sides by $x$ and moved everything to the left hand side. If you remember the quadratic formula, the solutions of the above equations are $$ x_{1,2}=\frac{-1 \pm \sqrt{1-4}}{2}=\frac{-1\pm \sqrt{-3}}{2}. $$ The prime $p$ is odd, so $2$ is invertible and we don't have any problems with the denominator. The only problem left is computing $\sqrt{-3} \mod p$. Note that there isn't always a solution to the above equation. $-3$ can either be a square or not be one depending on $p$. To be more precise, you can deduce from quadratic reciprocity that $-3$ is a square mod $p$ if and only if $$ \left(\dfrac{-3}{p}\right)=1 \text{ or } 0 $$ which is equivalent to $$ p \equiv 1,3,7 \mod 12 $$