For each odd prime \(p\), let \(R(p)\) be the least positive integer \(n\) satisfying
$$n^2-3n-1\equiv 0\pmod{p^2}.$$
The goal is to compute
$$S(L)=\sum_{p\le L} R(p)$$
for \(L=10^7\). Useful checkpoints are \(S(10)=5\), \(S(100)=1752\), and \(S(1000)=6728355\).
Write
$$f(n)=n^2-3n-1.$$
The implementation does not search over all \(n\). Instead it first determines when roots can exist modulo \(p\), computes those roots explicitly, and then lifts them once to modulo \(p^2\).
Multiplying by \(4\) and completing the square gives
$$4f(n)=4n^2-12n-4=(2n-3)^2-13.$$
Because \(p\) is odd, \(2\) is invertible modulo \(p\). Therefore
$$f(n)\equiv 0\pmod{p}\iff (2n-3)^2\equiv 13\pmod{p}.$$
So the congruence has roots modulo \(p\) exactly when \(13\) is a quadratic residue modulo \(p\).
For odd primes \(p\neq 13\), quadratic reciprocity gives
$$\left(\frac{13}{p}\right)=\left(\frac{p}{13}\right),$$
because \(13\equiv 1\pmod{4}\). The nonzero quadratic residues modulo \(13\) are
$$1,\ 3,\ 4,\ 9,\ 10,\ 12.$$
Hence roots can exist only for primes in those six residue classes modulo \(13\). This explains the residue-class filter used by the implementation before any expensive modular square-root work is attempted.
The prime \(p=13\) must be handled separately. Modulo \(13\), the congruence becomes
$$ (2n-3)^2\equiv 0\pmod{13}, $$
so there is the double root \(n\equiv 8\pmod{13}\). But
$$f(8)=8^2-3\cdot 8-1=39,$$
which is divisible by \(13\) but not by \(13^2=169\). Therefore the root modulo \(13\) does not lift to a root modulo \(13^2\), and \(p=13\) contributes nothing.
Assume now that \(p\neq 13\) and that \(13\) is a quadratic residue modulo \(p\). If
$$s^2\equiv 13\pmod{p},$$
then from \(2n-3\equiv \pm s\pmod{p}\) we obtain the two roots
$$r_1\equiv \frac{3+s}{2}\pmod{p},\qquad r_2\equiv \frac{3-s}{2}\pmod{p}.$$
A modular square root \(s\) is found with the Tonelli-Shanks algorithm. Since \(2^{-1}\equiv (p+1)/2\pmod{p}\), the division by \(2\) is just another modular multiplication.
Let \(r\) be one of the roots modulo \(p\). Any lift to modulo \(p^2\) has the form
$$n=r+tp$$
for some \(t\in\{0,1,\dots,p-1\}\). Expand \(f(r+tp)\):
$$f(r+tp)=f(r)+tp\,f'(r)+t^2p^2,$$
where
$$f'(x)=2x-3.$$
Reducing modulo \(p^2\) removes the last term, so the condition \(f(r+tp)\equiv 0\pmod{p^2}\) becomes
$$f(r)+tp\,f'(r)\equiv 0\pmod{p^2}.$$
Because \(r\) is already a root modulo \(p\), the value \(f(r)\) is divisible by \(p\). Dividing by \(p\) yields the linear congruence
$$t\,f'(r)\equiv -\frac{f(r)}{p}\pmod{p},$$
and therefore
$$t\equiv -\frac{f(r)/p}{f'(r)}\pmod{p}.$$
For \(p\neq 13\), we have \(f'(r)=2r-3\equiv \pm s\not\equiv 0\pmod{p}\), so the inverse exists. Thus each root modulo \(p\) lifts to exactly one root modulo \(p^2\).
The two roots \(r_1\) and \(r_2\) modulo \(p\) produce two lifted roots \(n_1\) and \(n_2\) modulo \(p^2\). The definition of \(R(p)\) asks for the least positive solution, so
$$R(p)=\min(n_1,n_2).$$
Summing this quantity over all contributing primes gives the desired value \(S(L)\).
Here \(13\equiv 1\pmod{3}\), so we may take \(s\equiv 1\). The two roots modulo \(3\) are
$$r_1\equiv \frac{3+1}{2}\equiv 2\pmod{3},\qquad r_2\equiv \frac{3-1}{2}\equiv 1\pmod{3}.$$
For \(r=2\),
$$f(2)=4-6-1=-3,\qquad f'(2)=1.$$
So
$$t\equiv -\frac{-3/3}{1}\equiv 1\pmod{3},$$
and the lifted root is
$$n=2+1\cdot 3=5.$$
For \(r=1\),
$$f(1)=1-3-1=-3,\qquad f'(1)=-1\equiv 2\pmod{3}.$$
Since \(2^{-1}\equiv 2\pmod{3}\),
$$t\equiv -\frac{-3/3}{2}\equiv 2\pmod{3},$$
which gives
$$n=1+2\cdot 3=7.$$
Therefore \(R(3)=5\), and because \(3\) is the only contributing prime up to \(10\), we recover the checkpoint \(S(10)=5\).
The C++, Python, and Java implementations all use the same structure. They begin with a prime sieve up to \(L\). After excluding \(2\) and \(13\), they keep only primes whose residue modulo \(13\) is one of \(1,3,4,9,10,12\). For each remaining prime, the implementation computes a square root of \(13\) modulo \(p\) via Tonelli-Shanks, constructs the two roots modulo \(p\), applies the Hensel correction above to obtain the two roots modulo \(p^2\), and adds the smaller lifted value to the running sum. Fast modular exponentiation is reused for Euler-criterion tests, modular inverses, and the Tonelli-Shanks substeps.
Generating all primes up to \(L\) with a sieve of Eratosthenes costs \(O(L\log\log L)\) time and \(O(L)\) memory. The residue-class filter removes roughly half of the odd primes immediately. Each surviving prime then needs only a constant amount of modular arithmetic plus one Tonelli-Shanks square-root computation, whose cost is polylogarithmic in \(p\). In practice the sieve dominates the memory usage, and the entire method is easily fast enough for \(L=10^7\).
Für jede ungerade Primzahl \(p\) sei \(R(p)\) die kleinste positive ganze Zahl \(n\) mit
$$n^2-3n-1\equiv 0\pmod{p^2}.$$
Gesucht ist
$$S(L)=\sum_{p\le L} R(p)$$
für \(L=10^7\). Nützliche Kontrollwerte sind \(S(10)=5\), \(S(100)=1752\) und \(S(1000)=6728355\).
Setze
$$f(n)=n^2-3n-1.$$
Die Lösung durchsucht nicht alle \(n\). Stattdessen wird zuerst geklärt, wann es Lösungen modulo \(p\) geben kann; diese Lösungen werden explizit berechnet und anschließend genau einmal auf modulo \(p^2\) gehoben.
Nach Multiplikation mit \(4\) und quadratischer Ergänzung erhält man
$$4f(n)=4n^2-12n-4=(2n-3)^2-13.$$
Da \(p\) ungerade ist, ist \(2\) modulo \(p\) invertierbar. Also gilt
$$f(n)\equiv 0\pmod{p}\iff (2n-3)^2\equiv 13\pmod{p}.$$
Damit existieren Lösungen modulo \(p\) genau dann, wenn \(13\) ein quadratischer Rest modulo \(p\) ist.
Für ungerade Primzahlen \(p\neq 13\) liefert das quadratische Reziprozitatsgesetz
$$\left(\frac{13}{p}\right)=\left(\frac{p}{13}\right),$$
weil \(13\equiv 1\pmod{4}\) ist. Die von \(0\) verschiedenen quadratischen Reste modulo \(13\) sind
$$1,\ 3,\ 4,\ 9,\ 10,\ 12.$$
Also konnen nur Primzahlen mit genau diesen sechs Restklassen modulo \(13\) beitragen. Deshalb verwendet die Implementierung schon vor der Berechnung modularer Quadratwurzeln einen solchen Vorfilter.
Die Primzahl \(p=13\) ist ein Sonderfall. Modulo \(13\) wird die Kongruenz zu
$$ (2n-3)^2\equiv 0\pmod{13}, $$
also gibt es die doppelte Losung \(n\equiv 8\pmod{13}\). Aber
$$f(8)=8^2-3\cdot 8-1=39,$$
und \(39\) ist zwar durch \(13\), aber nicht durch \(13^2=169\) teilbar. Daher hebt sich die Losung modulo \(13\) nicht zu einer Losung modulo \(13^2\), und \(p=13\) tragt nichts bei.
Nun sei \(p\neq 13\) und \(13\) ein quadratischer Rest modulo \(p\). Wenn
$$s^2\equiv 13\pmod{p},$$
dann folgt aus \(2n-3\equiv \pm s\pmod{p}\) die Wurzelformel
$$r_1\equiv \frac{3+s}{2}\pmod{p},\qquad r_2\equiv \frac{3-s}{2}\pmod{p}.$$
Eine modulare Quadratwurzel \(s\) wird mit Tonelli-Shanks berechnet. Da \(2^{-1}\equiv (p+1)/2\pmod{p}\), ist die Division durch \(2\) nur eine weitere modulare Multiplikation.
Sei \(r\) eine Losung modulo \(p\). Jede Hebung nach modulo \(p^2\) hat die Form
$$n=r+tp$$
mit \(t\in\{0,1,\dots,p-1\}\). Durch Ausmultiplizieren ergibt sich
$$f(r+tp)=f(r)+tp\,f'(r)+t^2p^2,$$
wobei
$$f'(x)=2x-3.$$
Modulo \(p^2\) verschwindet der letzte Term, also wird die Bedingung \(f(r+tp)\equiv 0\pmod{p^2}\) zu
$$f(r)+tp\,f'(r)\equiv 0\pmod{p^2}.$$
Weil \(r\) bereits eine Losung modulo \(p\) ist, ist \(f(r)\) durch \(p\) teilbar. Nach Division durch \(p\) bleibt
$$t\,f'(r)\equiv -\frac{f(r)}{p}\pmod{p},$$
und somit
$$t\equiv -\frac{f(r)/p}{f'(r)}\pmod{p}.$$
Fur \(p\neq 13\) gilt \(f'(r)=2r-3\equiv \pm s\not\equiv 0\pmod{p}\), also ist die Inverse vorhanden. Jede Losung modulo \(p\) hebt sich daher eindeutig zu einer Losung modulo \(p^2\).
Die beiden Losungen \(r_1\) und \(r_2\) modulo \(p\) liefern zwei gehobene Losungen \(n_1\) und \(n_2\) modulo \(p^2\). Gesucht ist die kleinste positive davon, also
$$R(p)=\min(n_1,n_2).$$
Die Summe uber alle beitragenden Primzahlen ist dann \(S(L)\).
Hier gilt \(13\equiv 1\pmod{3}\), also kann man \(s\equiv 1\) wahlen. Die beiden Losungen modulo \(3\) sind
$$r_1\equiv \frac{3+1}{2}\equiv 2\pmod{3},\qquad r_2\equiv \frac{3-1}{2}\equiv 1\pmod{3}.$$
Fur \(r=2\) ist
$$f(2)=4-6-1=-3,\qquad f'(2)=1.$$
Damit folgt
$$t\equiv -\frac{-3/3}{1}\equiv 1\pmod{3},$$
und die gehobene Losung lautet
$$n=2+1\cdot 3=5.$$
Fur \(r=1\) gilt
$$f(1)=1-3-1=-3,\qquad f'(1)=-1\equiv 2\pmod{3}.$$
Da \(2^{-1}\equiv 2\pmod{3}\), erhalt man
$$t\equiv -\frac{-3/3}{2}\equiv 2\pmod{3},$$
also
$$n=1+2\cdot 3=7.$$
Somit ist \(R(3)=5\). Da bis \(10\) nur \(p=3\) beitragt, folgt sofort der Kontrollwert \(S(10)=5\).
Die C++-, Python- und Java-Implementierungen folgen derselben Pipeline. Zuerst wird mit einem Sieb alle Primzahlen bis \(L\) bestimmt. Danach werden \(2\) und \(13\) ausgeschlossen, und es bleiben nur Primzahlen mit Rest \(1,3,4,9,10\) oder \(12\) modulo \(13\). Fur jede dieser Primzahlen berechnet die Implementierung mit Tonelli-Shanks eine Quadratwurzel von \(13\) modulo \(p\), konstruiert daraus die beiden Losungen modulo \(p\), wendet die obige Hensel-Korrektur an, um die beiden Losungen modulo \(p^2\) zu erhalten, und addiert die kleinere davon zur laufenden Summe. Schnelle modulare Potenzierung wird dabei sowohl fur Quadratresstests als auch fur Inversen und die Zwischenschritte von Tonelli-Shanks verwendet.
Das Sieb des Eratosthenes bis \(L\) benotigt \(O(L\log\log L)\) Zeit und \(O(L)\) Speicher. Der Restklassenfilter entfernt sofort ungefahr die Halfte aller ungeraden Primzahlen. Fur jede uberlebende Primzahl fallen dann nur wenige modulare Multiplikationen sowie eine Tonelli-Shanks-Berechnung an, also Aufwand von polylogarithmischer Grobe in \(p\). Praktisch dominiert das Sieb den Speicherverbrauch, und das gesamte Verfahren ist fur \(L=10^7\) gut geeignet.
Her tek asal \(p\) icin \(R(p)\),
$$n^2-3n-1\equiv 0\pmod{p^2}$$
kosulunu saglayan en kucuk pozitif \(n\) olsun. Hesaplanmak istenen buyukluk
$$S(L)=\sum_{p\le L} R(p)$$
olup burada \(L=10^7\) alinir. Yararlı kontrol degerleri \(S(10)=5\), \(S(100)=1752\) ve \(S(1000)=6728355\) sonucudur.
Su polinomu tanimlayalim:
$$f(n)=n^2-3n-1.$$
Uygulama tum \(n\) degerlerini denemez. Bunun yerine once hangi asallarda mod \(p\) kok olabilecegini belirler, bu kokleri acikca hesaplar ve sonra tek bir Hensel adimiyla mod \(p^2\)'ye kaldirir.
\(4\) ile carpip kare tamamlarsak
$$4f(n)=4n^2-12n-4=(2n-3)^2-13$$
elde edilir. \(p\) tek asal oldugu icin \(2\), mod \(p\)'de terslenebilir. Bu nedenle
$$f(n)\equiv 0\pmod{p}\iff (2n-3)^2\equiv 13\pmod{p}.$$
Yani mod \(p\)'de kok varligi tam olarak \(13\)'un mod \(p\)'de kare kalan olmasina baglidir.
\(p\neq 13\) olan tek asallar icin kare karsililik yasasi
$$\left(\frac{13}{p}\right)=\left(\frac{p}{13}\right)$$
sonucunu verir; cunku \(13\equiv 1\pmod{4}\). Mod \(13\)'te sifirdan farkli kare kalanlar
$$1,\ 3,\ 4,\ 9,\ 10,\ 12$$
oldugundan, ancak bu alti kalanin birine denk gelen asallar katkı yapabilir. Uygulamadaki mod \(13\) on filtresi tam olarak bundan gelir.
\(p=13\) ise ayri bir durumdur. Modulo \(13\) denklem
$$ (2n-3)^2\equiv 0\pmod{13} $$
olur ve cift katli kok \(n\equiv 8\pmod{13}\) cikar. Fakat
$$f(8)=8^2-3\cdot 8-1=39$$
olup \(39\), \(13\)'e bolunur ama \(13^2=169\)'a bolunmez. Dolayisiyla mod \(13\)'teki kok mod \(13^2\)'ye yukselemez; bu yuzden \(p=13\) hic katkı vermez.
Simdi \(p\neq 13\) olsun ve \(13\), mod \(p\)'de kare kalan olsun. Eger
$$s^2\equiv 13\pmod{p}$$
ise \(2n-3\equiv \pm s\pmod{p}\) oldugundan iki kok
$$r_1\equiv \frac{3+s}{2}\pmod{p},\qquad r_2\equiv \frac{3-s}{2}\pmod{p}$$
seklinde yazilir. \(s\) degeri Tonelli-Shanks ile bulunur. Ayrica \(2^{-1}\equiv (p+1)/2\pmod{p}\) oldugu icin \(2\)'ye bolme islemi de basit bir moduler carpma haline gelir.
Mod \(p\)'deki koklerden biri \(r\) olsun. Mod \(p^2\)'deki her aday
$$n=r+tp$$
seklindedir; burada \(t\in\{0,1,\dots,p-1\}\). Acarsak
$$f(r+tp)=f(r)+tp\,f'(r)+t^2p^2,$$
ve
$$f'(x)=2x-3$$
olur. Mod \(p^2\)'de son terim kaybolur. Bu nedenle \(f(r+tp)\equiv 0\pmod{p^2}\) kosulu
$$f(r)+tp\,f'(r)\equiv 0\pmod{p^2}$$
haline gelir. \(r\), mod \(p\)'de zaten kok oldugu icin \(f(r)\) sayisi \(p\)'ye bolunur. Her iki tarafi \(p\)'ye bolup
$$t\,f'(r)\equiv -\frac{f(r)}{p}\pmod{p}$$
ve dolayisiyla
$$t\equiv -\frac{f(r)/p}{f'(r)}\pmod{p}$$
elde edilir. \(p\neq 13\) iken \(f'(r)=2r-3\equiv \pm s\not\equiv 0\pmod{p}\) oldugundan ters her zaman vardir; yani her mod \(p\) koku mod \(p^2\)'de tek bir koka yukselir.
Iki mod \(p\) kokunden iki adet mod \(p^2\) koku elde edilir; bunlara \(n_1\) ve \(n_2\) diyelim. Tanim geregi
$$R(p)=\min(n_1,n_2)$$
alinir. Tum katkı veren asallar icin bu degerler toplandiginda \(S(L)\) elde edilir.
Burada \(13\equiv 1\pmod{3}\), dolayisiyla \(s\equiv 1\) secilebilir. Mod \(3\)'te iki kok
$$r_1\equiv \frac{3+1}{2}\equiv 2\pmod{3},\qquad r_2\equiv \frac{3-1}{2}\equiv 1\pmod{3}$$
olur. \(r=2\) icin
$$f(2)=4-6-1=-3,\qquad f'(2)=1.$$
Buna gore
$$t\equiv -\frac{-3/3}{1}\equiv 1\pmod{3}$$
ve yukseltilmis kok
$$n=2+1\cdot 3=5$$
cikar. \(r=1\) icin ise
$$f(1)=1-3-1=-3,\qquad f'(1)=-1\equiv 2\pmod{3}.$$
\(2^{-1}\equiv 2\pmod{3}\) oldugundan
$$t\equiv -\frac{-3/3}{2}\equiv 2\pmod{3}$$
ve
$$n=1+2\cdot 3=7$$
elde edilir. Dolayisiyla \(R(3)=5\) olur; \(10\)'a kadar katkı veren tek asal \(3\) oldugundan \(S(10)=5\) kontrol noktasi dogrulanir.
C++, Python ve Java uygulamalari ayni akisi izler. Once \(L\)'ye kadar asal eleği kurulur. Sonra \(2\) ve \(13\) atlanir; mod \(13\)'e gore yalnizca \(1,3,4,9,10,12\) kalinlarinda olan asallar tutulur. Kalan her asal icin Tonelli-Shanks ile \(13\)'un bir karekoku bulunur, bundan mod \(p\) kokleri uretilir, yukaridaki Hensel duzeltmesi ile mod \(p^2\) koklerine cikilir ve daha kucuk olan toplamaya eklenir. Hizli moduler us alma; kare kalan testi, ters alma ve Tonelli-Shanks adimlarinin hepsinde tekrar kullanilir.
Eratosthenes eleği ile \(L\)'ye kadar asal uretmek \(O(L\log\log L)\) zaman ve \(O(L)\) bellek gerektirir. Kalin sinif filtresi, tek asalların yaklasik yarisini hemen eler. Geriye kalan her asal icin yalnizca sabit sayida moduler carpma ve bir Tonelli-Shanks hesabi vardir; bunun maliyeti \(p\)'ye gore polilogaritmiktir. Pratikte bellek maliyetini elek belirler ve tum yontem \(L=10^7\) icin rahatlikla uygulanir.
Para cada primo impar \(p\), definimos \(R(p)\) como el menor entero positivo \(n\) que satisface
$$n^2-3n-1\equiv 0\pmod{p^2}.$$
Hay que calcular
$$S(L)=\sum_{p\le L} R(p)$$
para \(L=10^7\). Puntos de control utiles: \(S(10)=5\), \(S(100)=1752\) y \(S(1000)=6728355\).
Escribamos
$$f(n)=n^2-3n-1.$$
La idea no es buscar sobre todos los posibles \(n\), sino estudiar primero el problema modulo \(p\), identificar que primos pueden tener soluciones y luego levantar esas soluciones una sola vez hasta modulo \(p^2\).
Multiplicando por \(4\) y completando el cuadrado obtenemos
$$4f(n)=4n^2-12n-4=(2n-3)^2-13.$$
Como \(p\) es impar, \(2\) tiene inverso modulo \(p\). Por tanto,
$$f(n)\equiv 0\pmod{p}\iff (2n-3)^2\equiv 13\pmod{p}.$$
Esto muestra que la congruencia tiene soluciones modulo \(p\) exactamente cuando \(13\) es un residuo cuadratico modulo \(p\).
Para primos impares \(p\neq 13\), la reciprocidad cuadratica da
$$\left(\frac{13}{p}\right)=\left(\frac{p}{13}\right),$$
porque \(13\equiv 1\pmod{4}\). Los residuos cuadraticos no nulos modulo \(13\) son
$$1,\ 3,\ 4,\ 9,\ 10,\ 12.$$
Asi que solo pueden contribuir los primos cuyo resto modulo \(13\) pertenece a ese conjunto. Ese es precisamente el filtro previo que usa la implementacion antes de llamar a Tonelli-Shanks.
El primo \(p=13\) es excepcional. Modulo \(13\), la congruencia se reduce a
$$ (2n-3)^2\equiv 0\pmod{13}, $$
de donde sale la raiz doble \(n\equiv 8\pmod{13}\). Sin embargo,
$$f(8)=8^2-3\cdot 8-1=39,$$
y \(39\) es divisible por \(13\), pero no por \(13^2=169\). Entonces la raiz modulo \(13\) no se levanta a una raiz modulo \(13^2\), y por eso \(13\) no aporta nada a la suma.
Supongamos ahora que \(p\neq 13\) y que \(13\) es residuo cuadratico modulo \(p\). Si
$$s^2\equiv 13\pmod{p},$$
entonces de \(2n-3\equiv \pm s\pmod{p}\) se obtienen las dos raices
$$r_1\equiv \frac{3+s}{2}\pmod{p},\qquad r_2\equiv \frac{3-s}{2}\pmod{p}.$$
La raiz cuadrada modular \(s\) se calcula con Tonelli-Shanks. Como \(2^{-1}\equiv (p+1)/2\pmod{p}\), la division por \(2\) se implementa con una sola multiplicacion modular.
Sea \(r\) una de las raices modulo \(p\). Cualquier levantamiento a modulo \(p^2\) tiene la forma
$$n=r+tp$$
con \(t\in\{0,1,\dots,p-1\}\). Al expandir,
$$f(r+tp)=f(r)+tp\,f'(r)+t^2p^2,$$
donde
$$f'(x)=2x-3.$$
Modulo \(p^2\), el ultimo termino desaparece, de modo que \(f(r+tp)\equiv 0\pmod{p^2}\) equivale a
$$f(r)+tp\,f'(r)\equiv 0\pmod{p^2}.$$
Como \(r\) ya es raiz modulo \(p\), \(f(r)\) es multiplo de \(p\). Dividiendo por \(p\) queda
$$t\,f'(r)\equiv -\frac{f(r)}{p}\pmod{p},$$
y por tanto
$$t\equiv -\frac{f(r)/p}{f'(r)}\pmod{p}.$$
Cuando \(p\neq 13\), se tiene \(f'(r)=2r-3\equiv \pm s\not\equiv 0\pmod{p}\), asi que el inverso existe y cada raiz modulo \(p\) se levanta de manera unica a modulo \(p^2\).
Las dos raices modulo \(p\) producen dos raices modulo \(p^2\), digamos \(n_1\) y \(n_2\). Por definicion,
$$R(p)=\min(n_1,n_2).$$
Sumando este valor sobre todos los primos que si contribuyen se obtiene \(S(L)\).
Aqui \(13\equiv 1\pmod{3}\), asi que podemos tomar \(s\equiv 1\). Las dos raices modulo \(3\) son
$$r_1\equiv \frac{3+1}{2}\equiv 2\pmod{3},\qquad r_2\equiv \frac{3-1}{2}\equiv 1\pmod{3}.$$
Para \(r=2\),
$$f(2)=4-6-1=-3,\qquad f'(2)=1.$$
Entonces
$$t\equiv -\frac{-3/3}{1}\equiv 1\pmod{3},$$
y la raiz levantada es
$$n=2+1\cdot 3=5.$$
Para \(r=1\),
$$f(1)=1-3-1=-3,\qquad f'(1)=-1\equiv 2\pmod{3}.$$
Como \(2^{-1}\equiv 2\pmod{3}\), se obtiene
$$t\equiv -\frac{-3/3}{2}\equiv 2\pmod{3},$$
lo que da
$$n=1+2\cdot 3=7.$$
Por lo tanto \(R(3)=5\). Ademas, como \(3\) es el unico primo que aporta hasta \(10\), queda explicado el punto de control \(S(10)=5\).
Las implementaciones en C++, Python y Java siguen la misma secuencia. Primero generan los primos hasta \(L\) con una criba. Despues descartan \(2\) y \(13\), y tambien todos los primos cuyo resto modulo \(13\) no sea uno de \(1,3,4,9,10,12\). Para cada primo restante, la implementacion calcula una raiz cuadrada de \(13\) modulo \(p\) con Tonelli-Shanks, forma las dos raices modulo \(p\), aplica la correccion de Hensel mostrada arriba para obtener las dos raices modulo \(p^2\), y suma la menor de ellas. La exponenciacion modular rapida se reutiliza para las pruebas de residuo cuadratico, las inversas modulares y los pasos internos de Tonelli-Shanks.
La criba de Eratostenes hasta \(L\) cuesta \(O(L\log\log L)\) tiempo y \(O(L)\) memoria. El filtro por clases residuales elimina de inmediato aproximadamente la mitad de los primos impares. Para cada primo superviviente solo quedan unas pocas multiplicaciones modulares y una ejecucion de Tonelli-Shanks, cuyo coste es polilogaritmico en \(p\). En la practica, la memoria esta dominada por la criba, y el metodo completo es perfectamente viable para \(L=10^7\).
对每个奇素数 \(p\)，定义 \(R(p)\) 为满足
$$n^2-3n-1\equiv 0\pmod{p^2}$$
的最小正整数 \(n\)。题目要求计算
$$S(L)=\sum_{p\le L} R(p)$$
其中 \(L=10^7\)。可用于校验的结果有 \(S(10)=5\)、\(S(100)=1752\)、\(S(1000)=6728355\)。
记
$$f(n)=n^2-3n-1.$$
实现并不会直接枚举 \(n\)。核心思路是先研究模 \(p\) 是否有根，再把模 \(p\) 的根唯一提升到模 \(p^2\)。这样每个素数只需要做少量模运算。
将方程乘以 \(4\)，再配方：
$$4f(n)=4n^2-12n-4=(2n-3)^2-13.$$
由于 \(p\) 是奇素数，\(2\) 在模 \(p\) 下可逆，所以
$$f(n)\equiv 0\pmod{p}\iff (2n-3)^2\equiv 13\pmod{p}.$$
因此，模 \(p\) 有根当且仅当 \(13\) 是模 \(p\) 的二次剩余。
对所有奇素数 \(p\neq 13\)，由二次互反律可得
$$\left(\frac{13}{p}\right)=\left(\frac{p}{13}\right),$$
因为 \(13\equiv 1\pmod{4}\)。模 \(13\) 的非零平方剩余正好是
$$1,\ 3,\ 4,\ 9,\ 10,\ 12.$$
所以只有当 \(p\bmod 13\) 落在这六个剩余类中时，方程才可能有解。这正是实现中先做的快速筛选。
\(p=13\) 是特例。此时模 \(13\) 的方程变为
$$ (2n-3)^2\equiv 0\pmod{13}, $$
于是只有一个重根 \(n\equiv 8\pmod{13}\)。但
$$f(8)=8^2-3\cdot 8-1=39,$$
\(39\) 虽然能被 \(13\) 整除，却不能被 \(13^2=169\) 整除，所以这个模 \(13\) 的根不能提升到模 \(13^2\)。因此 \(p=13\) 对总和没有贡献。
现在假设 \(p\neq 13\)，且 \(13\) 是模 \(p\) 的二次剩余。若
$$s^2\equiv 13\pmod{p},$$
则由 \(2n-3\equiv \pm s\pmod{p}\) 得到
$$r_1\equiv \frac{3+s}{2}\pmod{p},\qquad r_2\equiv \frac{3-s}{2}\pmod{p}.$$
这里的模平方根 \(s\) 由 Tonelli-Shanks 算法求出。又因为 \(2^{-1}\equiv (p+1)/2\pmod{p}\)，所以除以 \(2\) 只是一轮额外的模乘。
设 \(r\) 是模 \(p\) 的一个根。模 \(p^2\) 下与之对应的候选值都可写成
$$n=r+tp,$$
其中 \(t\in\{0,1,\dots,p-1\}\)。展开后有
$$f(r+tp)=f(r)+tp\,f'(r)+t^2p^2,$$
其中
$$f'(x)=2x-3.$$
在模 \(p^2\) 下，最后一项自动消失，因此条件 \(f(r+tp)\equiv 0\pmod{p^2}\) 化为
$$f(r)+tp\,f'(r)\equiv 0\pmod{p^2}.$$
由于 \(r\) 已经是模 \(p\) 的根，\(f(r)\) 必然能被 \(p\) 整除。两边同时除以 \(p\)，得到
$$t\,f'(r)\equiv -\frac{f(r)}{p}\pmod{p},$$
从而
$$t\equiv -\frac{f(r)/p}{f'(r)}\pmod{p}.$$
当 \(p\neq 13\) 时，\(f'(r)=2r-3\equiv \pm s\not\equiv 0\pmod{p}\)，所以逆元一定存在。也就是说，每个模 \(p\) 的根都会唯一提升到一个模 \(p^2\) 的根。
模 \(p\) 的两个根 \(r_1,r_2\) 会分别提升为模 \(p^2\) 的两个根 \(n_1,n_2\)。题目定义要求取其中较小的正整数，因此
$$R(p)=\min(n_1,n_2).$$
把所有有贡献的素数对应的 \(R(p)\) 相加，就得到 \(S(L)\)。
因为 \(13\equiv 1\pmod{3}\)，可以取 \(s\equiv 1\)。于是模 \(3\) 的两个根是
$$r_1\equiv \frac{3+1}{2}\equiv 2\pmod{3},\qquad r_2\equiv \frac{3-1}{2}\equiv 1\pmod{3}.$$
对 \(r=2\)，有
$$f(2)=4-6-1=-3,\qquad f'(2)=1.$$
因此
$$t\equiv -\frac{-3/3}{1}\equiv 1\pmod{3},$$
提升后的根为
$$n=2+1\cdot 3=5.$$
对 \(r=1\)，有
$$f(1)=1-3-1=-3,\qquad f'(1)=-1\equiv 2\pmod{3}.$$
又因为 \(2^{-1}\equiv 2\pmod{3}\)，所以
$$t\equiv -\frac{-3/3}{2}\equiv 2\pmod{3},$$
从而
$$n=1+2\cdot 3=7.$$
所以 \(R(3)=5\)。而在 \(10\) 以内，只有素数 \(3\) 会产生贡献，因此立刻得到校验值 \(S(10)=5\)。
C++、Python 和 Java 实现的流程完全一致。它们先用筛法生成不超过 \(L\) 的所有素数，然后跳过 \(2\) 和 \(13\)，再把模 \(13\) 不属于 \(1,3,4,9,10,12\) 的素数全部剔除。对每个剩余素数，先用 Tonelli-Shanks 求出 \(13\) 在模 \(p\) 下的一个平方根，再构造出模 \(p\) 的两个根，接着利用上面的 Hensel 校正公式把它们提升到模 \(p^2\)，最后把较小的提升根加入总和。快速模幂在二次剩余测试、求逆和 Tonelli-Shanks 的子步骤中都会反复使用。
用埃拉托斯特尼筛法生成不超过 \(L\) 的素数需要 \(O(L\log\log L)\) 时间和 \(O(L)\) 空间。剩余类过滤会立刻去掉大约一半的奇素数。对每个保留下来的素数，只需要常数次模乘以及一次 Tonelli-Shanks 计算，其代价相对于 \(p\) 是多对数级的。实际运行中，空间主要由筛表决定，而整个算法对 \(L=10^7\) 完全可行。
Для каждого нечетного простого \(p\) определим \(R(p)\) как наименьшее положительное целое \(n\), для которого
$$n^2-3n-1\equiv 0\pmod{p^2}.$$
Нужно вычислить
$$S(L)=\sum_{p\le L} R(p)$$
при \(L=10^7\). Полезные контрольные значения: \(S(10)=5\), \(S(100)=1752\), \(S(1000)=6728355\).
Обозначим
$$f(n)=n^2-3n-1.$$
Перебор по всем \(n\) здесь не нужен. Сначала надо понять, при каких простых вообще возможны корни по модулю \(p\), затем явно найти эти корни и один раз поднять их до модуля \(p^2\).
После умножения на \(4\) и выделения полного квадрата получаем
$$4f(n)=4n^2-12n-4=(2n-3)^2-13.$$
Так как \(p\) нечетное, число \(2\) обратимо по модулю \(p\). Поэтому
$$f(n)\equiv 0\pmod{p}\iff (2n-3)^2\equiv 13\pmod{p}.$$
Значит, решения по модулю \(p\) существуют тогда и только тогда, когда \(13\) является квадратичным вычетом по модулю \(p\).
Для нечетных простых \(p\neq 13\) закон квадратичной взаимности дает
$$\left(\frac{13}{p}\right)=\left(\frac{p}{13}\right),$$
поскольку \(13\equiv 1\pmod{4}\). Ненулевые квадратичные вычеты по модулю \(13\) таковы:
$$1,\ 3,\ 4,\ 9,\ 10,\ 12.$$
Следовательно, корни возможны только для тех простых, у которых остаток по модулю \(13\) входит в этот набор. Именно такой предварительный фильтр и использует реализация.
Простое \(p=13\) является исключением. По модулю \(13\) сравнение принимает вид
$$ (2n-3)^2\equiv 0\pmod{13}, $$
то есть возникает двойной корень \(n\equiv 8\pmod{13}\). Но
$$f(8)=8^2-3\cdot 8-1=39,$$
а число \(39\) делится на \(13\), но не делится на \(13^2=169\). Значит, корень по модулю \(13\) не поднимается до корня по модулю \(13^2\), и \(p=13\) не вносит вклад.
Пусть теперь \(p\neq 13\), и \(13\) является квадратичным вычетом по модулю \(p\). Если
$$s^2\equiv 13\pmod{p},$$
то из сравнения \(2n-3\equiv \pm s\pmod{p}\) получаем два корня
$$r_1\equiv \frac{3+s}{2}\pmod{p},\qquad r_2\equiv \frac{3-s}{2}\pmod{p}.$$
Модульный квадратный корень \(s\) находится алгоритмом Тонелли-Шенкса. Поскольку \(2^{-1}\equiv (p+1)/2\pmod{p}\), деление на \(2\) сводится к обычному умножению по модулю.
Пусть \(r\) - один из корней по модулю \(p\). Любой кандидат по модулю \(p^2\) имеет вид
$$n=r+tp,$$
где \(t\in\{0,1,\dots,p-1\}\). Тогда
$$f(r+tp)=f(r)+tp\,f'(r)+t^2p^2,$$
где
$$f'(x)=2x-3.$$
По модулю \(p^2\) последний член исчезает, поэтому условие \(f(r+tp)\equiv 0\pmod{p^2}\) эквивалентно
$$f(r)+tp\,f'(r)\equiv 0\pmod{p^2}.$$
Так как \(r\) уже является корнем по модулю \(p\), величина \(f(r)\) делится на \(p\). После деления на \(p\) получаем линейное сравнение
$$t\,f'(r)\equiv -\frac{f(r)}{p}\pmod{p},$$
то есть
$$t\equiv -\frac{f(r)/p}{f'(r)}\pmod{p}.$$
При \(p\neq 13\) имеем \(f'(r)=2r-3\equiv \pm s\not\equiv 0\pmod{p}\), так что обратный элемент существует. Следовательно, каждый корень по модулю \(p\) поднимается ровно к одному корню по модулю \(p^2\).
Два корня \(r_1\) и \(r_2\) по модулю \(p\) переходят в два корня \(n_1\) и \(n_2\) по модулю \(p^2\). По определению нужно взять наименьший положительный из них:
$$R(p)=\min(n_1,n_2).$$
После суммирования по всем подходящим простым получаем \(S(L)\).
Здесь \(13\equiv 1\pmod{3}\), поэтому можно взять \(s\equiv 1\). Тогда два корня по модулю \(3\) равны
$$r_1\equiv \frac{3+1}{2}\equiv 2\pmod{3},\qquad r_2\equiv \frac{3-1}{2}\equiv 1\pmod{3}.$$
Для \(r=2\)
$$f(2)=4-6-1=-3,\qquad f'(2)=1.$$
Следовательно,
$$t\equiv -\frac{-3/3}{1}\equiv 1\pmod{3},$$
и поднятый корень равен
$$n=2+1\cdot 3=5.$$
Для \(r=1\)
$$f(1)=1-3-1=-3,\qquad f'(1)=-1\equiv 2\pmod{3}.$$
Так как \(2^{-1}\equiv 2\pmod{3}\), имеем
$$t\equiv -\frac{-3/3}{2}\equiv 2\pmod{3},$$
откуда
$$n=1+2\cdot 3=7.$$
Итак, \(R(3)=5\). Поскольку до \(10\) вклад дает только простой \(3\), контрольное значение \(S(10)=5\) сразу подтверждается.
Реализации на C++, Python и Java устроены одинаково. Сначала строится решето простых до \(L\). Затем отбрасываются \(2\) и \(13\), а также все простые, чей остаток по модулю \(13\) не входит в набор \(1,3,4,9,10,12\). Для каждого оставшегося простого реализация вычисляет один квадратный корень из \(13\) по модулю \(p\) алгоритмом Тонелли-Шенкса, строит по нему два корня по модулю \(p\), применяет приведенную выше поправку Гензеля для получения двух корней по модулю \(p^2\), а затем прибавляет к сумме меньший из них. Быстрое модульное возведение в степень используется и для проверки квадратичного вычета, и для обращения по модулю, и внутри Tonelli-Shanks.
Решето Эратосфена до \(L\) требует \(O(L\log\log L)\) времени и \(O(L)\) памяти. Фильтр по остаткам отбрасывает примерно половину нечетных простых сразу. Для каждого выжившего простого остаются лишь несколько модульных умножений и один запуск Tonelli-Shanks, то есть стоимость полилогарифмическая по \(p\). На практике память определяется почти целиком решетом, а сам алгоритм без труда работает при \(L=10^7\).
لكل عدد أولي فردي \(p\)، نعرّف \(R(p)\) بأنه أصغر عدد صحيح موجب \(n\) يحقق
$$n^2-3n-1\equiv 0\pmod{p^2}.$$
المطلوب حساب
$$S(L)=\sum_{p\le L} R(p)$$
عند \(L=10^7\). ومن قيم التحقق المفيدة \(S(10)=5\) و\(S(100)=1752\) و\(S(1000)=6728355\).
لنكتب
$$f(n)=n^2-3n-1.$$
لا تعتمد الفكرة على تجربة قيم \(n\) كلها. بدلا من ذلك نحدد اولا متى يمكن ان توجد حلول بترديد \(p\)، ثم نحسب هذه الحلول صراحة، وبعدها نرفع كل حل مرة واحدة فقط الى الترديد \(p^2\).
بعد الضرب في \(4\) واكمال المربع نحصل على
$$4f(n)=4n^2-12n-4=(2n-3)^2-13.$$
وبما ان \(p\) عدد اولي فردي، فان \(2\) قابل للعكس بترديد \(p\). لذلك
$$f(n)\equiv 0\pmod{p}\iff (2n-3)^2\equiv 13\pmod{p}.$$
وهذا يعني ان المعادلة تملك جذورا بترديد \(p\) اذا وفقط اذا كان \(13\) باقيا تربيعيا modulo \(p\).
لكل اولي فردي \(p\neq 13\)، يعطي قانون التبادلية التربيعية العلاقة
$$\left(\frac{13}{p}\right)=\left(\frac{p}{13}\right),$$
لان \(13\equiv 1\pmod{4}\). والبواقي التربيعية غير الصفرية modulo \(13\) هي
$$1,\ 3,\ 4,\ 9,\ 10,\ 12.$$
اذن لا يمكن ان يوجد حل الا عندما يكون \(p\bmod 13\) واحدا من هذه الاصناف الستة. ولهذا تستعمل الخوارزمية ترشيحا مبكرا بهذه البواقي قبل الدخول في حساب الجذور التربيعية المعيارية.
اما \(p=13\) فهو حالة خاصة. فبترديد \(13\) يصبح التطابق
$$ (2n-3)^2\equiv 0\pmod{13}, $$
ومن ثم يوجد جذر مضاعف واحد هو \(n\equiv 8\pmod{13}\). لكن
$$f(8)=8^2-3\cdot 8-1=39,$$
و\(39\) يقبل القسمة على \(13\) ولكنه لا يقبل القسمة على \(13^2=169\). لذلك لا يرتفع هذا الجذر الى حل modulo \(13^2\)، ومن ثم لا يضيف \(13\) شيئا الى المجموع.
افترض الان ان \(p\neq 13\) وان \(13\) باق تربيعي modulo \(p\). اذا وجدنا
$$s^2\equiv 13\pmod{p},$$
فان العلاقة \(2n-3\equiv \pm s\pmod{p}\) تعطي الجذرين
$$r_1\equiv \frac{3+s}{2}\pmod{p},\qquad r_2\equiv \frac{3-s}{2}\pmod{p}.$$
ويتم حساب الجذر التربيعي المعياري \(s\) بخوارزمية Tonelli-Shanks. وبما ان \(2^{-1}\equiv (p+1)/2\pmod{p}\)، فان القسمة على \(2\) لا تتطلب الا ضربا معياريا اضافيا.
ليكن \(r\) احد الجذور modulo \(p\). عندئذ يمكن كتابة كل مرشح modulo \(p^2\) على الصورة
$$n=r+tp,$$
حيث \(t\in\{0,1,\dots,p-1\}\). وبالتوسيع نحصل على
$$f(r+tp)=f(r)+tp\,f'(r)+t^2p^2,$$
مع
$$f'(x)=2x-3.$$
وبترديد \(p^2\) يختفي الحد الاخير، لذلك يصبح شرط \(f(r+tp)\equiv 0\pmod{p^2}\) مكافئا لـ
$$f(r)+tp\,f'(r)\equiv 0\pmod{p^2}.$$
ولان \(r\) جذر اصلا بترديد \(p\)، فان \(f(r)\) من مضاعفات \(p\). وبعد القسمة على \(p\) نحصل على
$$t\,f'(r)\equiv -\frac{f(r)}{p}\pmod{p},$$
ومنها
$$t\equiv -\frac{f(r)/p}{f'(r)}\pmod{p}.$$
وعندما يكون \(p\neq 13\)، نجد ان \(f'(r)=2r-3\equiv \pm s\not\equiv 0\pmod{p}\)، ولذلك يوجد المعكوس المعياري ويكون لكل جذر modulo \(p\) رفع وحيد modulo \(p^2\).
الجذران \(r_1\) و\(r_2\) modulo \(p\) ينتجان جذرين مرفوعين \(n_1\) و\(n_2\) modulo \(p^2\). وبحسب تعريف المسألة نأخذ الاصغر الموجب منهما:
$$R(p)=\min(n_1,n_2).$$
ثم نجمع هذه القيمة على جميع الاعداد الاولية التي تساهم فعلا لنحصل على \(S(L)\).
لدينا \(13\equiv 1\pmod{3}\)، ولذلك يمكن اخذ \(s\equiv 1\). ومن ثم يكون الجذران modulo \(3\) هما
$$r_1\equiv \frac{3+1}{2}\equiv 2\pmod{3},\qquad r_2\equiv \frac{3-1}{2}\equiv 1\pmod{3}.$$
بالنسبة الى \(r=2\) نجد
$$f(2)=4-6-1=-3,\qquad f'(2)=1.$$
اذن
$$t\equiv -\frac{-3/3}{1}\equiv 1\pmod{3},$$
ومن ثم يكون الجذر المرفوع
$$n=2+1\cdot 3=5.$$
اما عند \(r=1\) فنحصل على
$$f(1)=1-3-1=-3,\qquad f'(1)=-1\equiv 2\pmod{3}.$$
وبما ان \(2^{-1}\equiv 2\pmod{3}\)، نحصل على
$$t\equiv -\frac{-3/3}{2}\equiv 2\pmod{3},$$
وبالتالي
$$n=1+2\cdot 3=7.$$
اذن \(R(3)=5\). ولان \(3\) هو الاولی الوحيد الذي يساهم حتى \(10\)، فاننا نسترجع مباشرة قيمة التحقق \(S(10)=5\).
تتبع تطبيقات C++ وPython وJava المسار نفسه. فهي تبني اولا غربالا للاعداد الاولية حتى \(L\)، ثم تستبعد \(2\) و\(13\)، وتبقي فقط الاعداد الاولية التي يقع باقيها modulo \(13\) في المجموعة \(1,3,4,9,10,12\). ولكل اولي متبق تحسب الخوارزمية جذرا تربيعيا واحدا للعدد \(13\) modulo \(p\) باستعمال Tonelli-Shanks، ثم تكوّن منه الجذرين modulo \(p\)، وبعد ذلك تطبق تصحيح Hensel السابق للحصول على الجذرين modulo \(p^2\)، ثم تضيف الاصغر منهما الى المجموع. كما يعاد استخدام الاس المعياري السريع في اختبار الباقي التربيعي، وحساب المعكوسات، وخطوات Tonelli-Shanks الداخلية.
توليد جميع الاعداد الاولية حتى \(L\) بغربال اراتوستينس يحتاج الى \(O(L\log\log L)\) زمنا و\(O(L)\) ذاكرة. ترشيح البواقي modulo \(13\) يزيل نحو نصف الاعداد الاولية الفردية مباشرة. وبعد ذلك يحتاج كل اولي باق الى عدد ثابت من العمليات المعيارية مع تنفيذ واحد لخوارزمية Tonelli-Shanks، وهي كلفة متعددة اللوغاريتم في \(p\). عمليا تهيمن بنية الغربال على الذاكرة، ويظل الاسلوب كله ملائما جدا عندما \(L=10^7\).