I'm fiddling with a question. I found a surprise. Given positive $n$ integer that is not a square, and fundamental solution $$ u^2 - n v^2 = 1 $$ with minimal integers $u \geq 1, v \geq 1,$ it is very frequent that $u \equiv -1 \pmod n$
This does fail, for $n=k^2$ it is nonsense, for $n=k^2 - 2$ we get $u=n+1,$ for $n=k^2 - 1$ we get $u = \sqrt {n+1}.$
The successes start: 2,3,5,6,10,11,13,17,18,19,22,26,27,29,37,38,41,43,50,51,53,54,58,59,61,65,66,67,73,74,82,83,85,86,89,97,101.
I have no idea why, but it appears that this works for primes $q \equiv 3 \pmod 8.$ Meanwhile, fails for primes $r \equiv 7 \pmod 8.$ Who knew? ADDED: Probably have this. Legendre showed (DICKSON's HISTORY, volume II, page 365) that a prime $q \equiv 3 \pmod 8$ gives $r^2 - q s^2 = -2.$ Then $r^2 \equiv -2 \pmod q,$ after which $$ \left( \frac{r^2 + q s^2}{2} \right)^2 - q (rs)^2 = 1 $$ with the first term $-1 \pmod q.$ In contrast, when prime $q \equiv 7 \pmod 8$ we get $r^2 - q s^2 = 2,$ so the first term comes out $1 \pmod q.$
Alright, there is one predictable family of successes, whenever there is an integer solution to $a^2 - n b^2 = -1,$ then $a^2 \equiv -1 \pmod n,$ after which we $(a^2 + n b^2)^2 - n(2ab)^2 = 1$ with $a^2 + n b^2 \equiv -1 \pmod n.$ This includes $n \equiv 1 \pmod 4$ prime, also $n = pq$ primes $p,q \equiv 1 \pmod 4$ with $(p|q)= (q|p) = -1.$
So, question is, How often does this happen?
