# How often does the fundamental Pell solution satisfy a certain congruence?

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? • The Pell equation implies $u^2\equiv 1\pmod n$, so if $n$ is prime you must have $u\equiv\pm1\pmod n$, ne? – Steven Stadnicki Jun 1 '18 at 0:42
• @StevenStadnicki I like it! Once $q \equiv 3 \pmod 4,$ the immediate difference between $q \equiv 3,7 \pmod 8,$ is Legendre $(2|q)$ – Will Jagy Jun 1 '18 at 0:44
• @StevenStadnicki the primes are now settled. Crucial result going back to Legendre gives the remaining cases. – Will Jagy Jun 1 '18 at 2:39
• Is there even a question here? – Infinity Jun 2 '18 at 20:39