Write
$$(1+\sqrt7)^k=a_k+b_k\sqrt7.$$
For each integer \(n\ge 2\), let \(g(n)\) be the least positive \(k\) such that
$$a_k\equiv 1 \pmod{n},\qquad b_k\equiv 0 \pmod{n};$$
if no such \(k\) exists, then \(g(n)=0\). The goal is to evaluate
$$G(N)=\sum_{n=2}^{N} g(n)$$
for \(N=10^6\). The C++, Python, and Java implementations do this by viewing \(1+\sqrt7\) inside the finite ring \(R_n=(\mathbb Z/n\mathbb Z)[\sqrt7]\) and computing its multiplicative order whenever that order exists.
Let
$$u=1+\sqrt7.$$
Then \(g(n)\) is exactly the smallest positive exponent \(k\) for which \(u^k=1\) in \(R_n\). Everything in the solution follows from understanding this order prime by prime, then rebuilding composite moduli with the Chinese remainder theorem.
Represent an element \(a+b\sqrt7\) by the pair \((a,b)\). Multiplication becomes
$$(a,b)\times(c,d)=\bigl(ac+7bd,\ ad+bc\bigr)\pmod{n},$$
because \((a+b\sqrt7)(c+d\sqrt7)=(ac+7bd)+(ad+bc)\sqrt7\).
So checking whether \((1+\sqrt7)^k\equiv 1\) is the same as checking whether repeated pair multiplication sends \((1,1)\) to \((1,0)\).
The norm of \(a+b\sqrt7\) is
$$N(a+b\sqrt7)=a^2-7b^2.$$
For \(u\) we get
$$N(u)=1^2-7\cdot 1^2=-6.$$
If \(u^k=1\) modulo \(n\), then norms give
$$(-6)^k\equiv 1 \pmod{n}.$$
This is impossible when \(2\mid n\) or \(3\mid n\), so every multiple of \(2\) or \(3\) has \(g(n)=0\). Conversely, if \(\gcd(n,6)=1\), then \(-6\) is invertible modulo \(n\), hence \(u\) is a unit in a finite group and some positive order must exist.
Let \(p\ge 5\) be prime with \(p\ne 7\). The key question is whether \(7\) is a quadratic residue modulo \(p\). By Euler's criterion,
$$\left(\frac{7}{p}\right)\equiv 7^{(p-1)/2}\pmod{p}\in\{1,-1\}.$$
If \(\left(\frac{7}{p}\right)=1\), then \(x^2-7\) splits into two distinct linear factors modulo \(p\). Therefore
$$R_p\cong \mathbb F_p\times \mathbb F_p,$$
and every unit has order dividing \(p-1\). In particular,
$$g(p)\mid (p-1).$$
If \(\left(\frac{7}{p}\right)=-1\), then \(x^2-7\) is irreducible modulo \(p\), so \(R_p\) is the field \(\mathbb F_{p^2}\). Its multiplicative group has size \(p^2-1\), hence
$$g(p)\mid (p^2-1)=(p-1)(p+1).$$
The implementation starts from the appropriate upper bound and strips away prime factors one by one. Whenever a candidate divisor \(q\) satisfies \(u^{M/q}=1\), the current order bound \(M\) can be reduced by \(q\).
The prime \(7\) behaves differently because
$$x^2-7\equiv x^2 \pmod{7}.$$
If we write \(\varepsilon=\sqrt7\) modulo \(7\), then \(\varepsilon^2=0\), so the binomial theorem collapses to
$$(1+\varepsilon)^k=1+k\varepsilon \pmod{7}.$$
This equals \(1\) exactly when \(k\equiv 0\pmod{7}\), therefore
$$g(7)=7.$$
For higher prime powers, let \(t=g(p^e)\). Reducing modulo \(p^e\) shows that \(g(p^{e+1})\) must be a multiple of \(t\), while the extra factor can only come from one more power of \(p\). So the only possibilities are
$$g(p^{e+1})\in\{t,\ pt\}.$$
The implementation checks this directly: if \(u^t\equiv 1\pmod{p^{e+1}}\), the order stays \(t\); otherwise it is multiplied by \(p\).
Suppose
$$n=\prod_{i=1}^{r} p_i^{e_i},\qquad \gcd(n,6)=1.$$
The Chinese remainder theorem gives the ring decomposition
$$R_n\cong \prod_{i=1}^{r} R_{p_i^{e_i}}.$$
The image of \(u\) in this product has one component in each prime-power ring. An exponent kills the whole product exactly when it kills every component, so
$$g(n)=\operatorname{lcm}\bigl(g(p_1^{e_1}),g(p_2^{e_2}),\dots,g(p_r^{e_r})\bigr).$$
This is why the algorithm spends most of its effort on prime powers: once those orders are known, every composite \(n\) is reconstructed by factorization plus one \(\operatorname{lcm}\) chain.
Take
$$n=35=5\cdot 7.$$
For \(p=5\), the Legendre symbol is \(\left(\frac{7}{5}\right)=\left(\frac{2}{5}\right)=-1\), so \(g(5)\mid 24\). Using pair arithmetic modulo \(5\),
$$u^2=(3,2),\qquad u^3=(2,0).$$
Therefore
$$u^{12}=(2,0)^4=(1,0),\qquad u^6=(2,0)^2=(4,0)\ne (1,0),$$
so
$$g(5)=12.$$
For \(p=7\), Step 3 already showed that
$$g(7)=7.$$
Now combine the two prime components:
$$g(35)=\operatorname{lcm}(12,7)=84.$$
This mirrors the full solution on a small modulus: compute prime orders, lift if necessary, then join them with the Chinese remainder theorem.
Because every multiple of \(2\) or \(3\) contributes \(0\), the total can be written as
$$G(N)=\sum_{\substack{2\le n\le N\\ \gcd(n,6)=1}} g(n).$$
So the problem is no longer "search powers separately for every \(n\)". Instead it becomes a preprocessing problem: build all prime-power orders up to \(N\), factor each admissible \(n\), take the least common multiple of its prime-power contributions, and accumulate the answer.
The C++, Python, and Java implementations all follow the same pipeline. First they represent \(a+b\sqrt7\) as a pair and use binary exponentiation to test whether a candidate exponent sends \(u\) back to \(1\) modulo a chosen modulus. This makes order tests cheap enough to repeat many times.
Next they build a smallest-prime-factor sieve up to \(N\). For each prime \(p\ge 5\), they determine whether \(7\) is a quadratic residue using Euler's criterion, choose the correct upper bound for \(g(p)\), and reduce that bound by testing prime divisors. The exceptional prime \(7\) is handled separately at the base level, and then every prime order is lifted through \(p^2,p^3,\dots\) with the rule from Step 3.
Finally, for each \(n\le N\) with \(\gcd(n,6)=1\), the sieve provides the factorization of \(n\). The implementation looks up the cached order for each prime power, takes their \(\operatorname{lcm}\), and adds the result to the running total.
Let the search limit be \(N\). Building the smallest-prime-factor sieve costs \(O(N\log\log N)\) time and \(O(N)\) memory. Factoring each admissible \(n\) then takes \(O(\log N)\) time on average. The prime and prime-power preprocessing requires repeated binary exponentiation for a modest number of candidate divisors, so the overall running time is close to \(O(N\log N)\) in practice, with \(O(N)\) memory for the sieve and cached prime-power orders.
Schreibe
$$(1+\sqrt7)^k=a_k+b_k\sqrt7.$$
Für jede ganze Zahl \(n\ge 2\) sei \(g(n)\) das kleinste positive \(k\) mit
$$a_k\equiv 1 \pmod{n},\qquad b_k\equiv 0 \pmod{n};$$
existiert kein solches \(k\), so ist \(g(n)=0\). Gesucht ist
$$G(N)=\sum_{n=2}^{N} g(n)$$
für \(N=10^6\). Die C++-, Python- und Java-Implementierungen interpretieren \(1+\sqrt7\) dabei als Element des endlichen Rings \(R_n=(\mathbb Z/n\mathbb Z)[\sqrt7]\) und berechnen seine multiplikative Ordnung, sobald sie existiert.
Setze
$$u=1+\sqrt7.$$
Dann ist \(g(n)\) genau der kleinste positive Exponent \(k\), für den \(u^k=1\) in \(R_n\) gilt. Die gesamte Lösung besteht darin, diese Ordnung zuerst für Primzahlpotenzen zu verstehen und anschließend zusammengesetzte Moduli per chinesischem Restsatz wieder zusammenzusetzen.
Ein Element \(a+b\sqrt7\) wird als Paar \((a,b)\) dargestellt. Die Multiplikation lautet
$$(a,b)\times(c,d)=\bigl(ac+7bd,\ ad+bc\bigr)\pmod{n},$$
denn \((a+b\sqrt7)(c+d\sqrt7)=(ac+7bd)+(ad+bc)\sqrt7\).
Damit bedeutet \((1+\sqrt7)^k\equiv 1\), dass wiederholte Paarmultiplikation das Element \((1,1)\) auf \((1,0)\) abbildet.
Die Norm von \(a+b\sqrt7\) ist
$$N(a+b\sqrt7)=a^2-7b^2.$$
Für \(u\) erhält man
$$N(u)=1^2-7\cdot 1^2=-6.$$
Falls \(u^k=1\) modulo \(n\), folgt durch Normbildung
$$(-6)^k\equiv 1 \pmod{n}.$$
Das ist unmöglich, sobald \(2\mid n\) oder \(3\mid n\). Also gilt für alle Vielfachen von \(2\) oder \(3\): \(g(n)=0\). Umgekehrt ist bei \(\gcd(n,6)=1\) die Norm invertierbar; dann ist \(u\) eine Einheit in einer endlichen Gruppe und eine positive Ordnung existiert sicher.
Sei \(p\ge 5\) prim mit \(p\ne 7\). Entscheidend ist, ob \(7\) quadratischer Rest modulo \(p\) ist. Nach dem Kriterium von Euler gilt
$$\left(\frac{7}{p}\right)\equiv 7^{(p-1)/2}\pmod{p}\in\{1,-1\}.$$
Ist \(\left(\frac{7}{p}\right)=1\), dann zerfällt \(x^2-7\) modulo \(p\) in zwei verschiedene Linearfaktoren. Somit
$$R_p\cong \mathbb F_p\times \mathbb F_p,$$
und jede Einheit hat Ordnung, die \(p-1\) teilt. Insbesondere
$$g(p)\mid (p-1).$$
Ist \(\left(\frac{7}{p}\right)=-1\), dann ist \(x^2-7\) irreduzibel modulo \(p\), also ist \(R_p\) der Körper \(\mathbb F_{p^2}\). Dessen multiplikative Gruppe hat Größe \(p^2-1\), daher
$$g(p)\mid (p^2-1)=(p-1)(p+1).$$
Die Implementierung startet mit dieser oberen Schranke und entfernt Primfaktoren nacheinander. Immer wenn \(u^{M/q}=1\) gilt, kann die aktuelle Schranke \(M\) durch \(q\) geteilt werden.
Die Primzahl \(7\) ist speziell, denn
$$x^2-7\equiv x^2 \pmod{7}.$$
Schreibt man \(\varepsilon=\sqrt7\) modulo \(7\), so gilt \(\varepsilon^2=0\), und der binomische Lehrsatz vereinfacht sich zu
$$(1+\varepsilon)^k=1+k\varepsilon \pmod{7}.$$
Das ist genau dann gleich \(1\), wenn \(k\equiv 0\pmod{7}\). Also
$$g(7)=7.$$
Für höhere Primzahlpotenzen sei \(t=g(p^e)\). Die Reduktion modulo \(p^e\) zeigt, dass \(g(p^{e+1})\) ein Vielfaches von \(t\) sein muss, und der zusätzliche Faktor kann nur aus genau einer weiteren Potenz von \(p\) stammen. Deshalb gibt es nur die zwei Möglichkeiten
$$g(p^{e+1})\in\{t,\ pt\}.$$
Die Implementierung testet dies direkt: Falls \(u^t\equiv 1\pmod{p^{e+1}}\), bleibt die Ordnung \(t\); sonst wird sie mit \(p\) multipliziert.
Sei nun
$$n=\prod_{i=1}^{r} p_i^{e_i},\qquad \gcd(n,6)=1.$$
Dann liefert der chinesische Restsatz die Ringzerlegung
$$R_n\cong \prod_{i=1}^{r} R_{p_i^{e_i}}.$$
Das Bild von \(u\) hat in jedem Primzahlpotenzring eine Komponente. Ein Exponent tötet das gesamte Produkt genau dann, wenn er jede einzelne Komponente tötet. Daher
$$g(n)=\operatorname{lcm}\bigl(g(p_1^{e_1}),g(p_2^{e_2}),\dots,g(p_r^{e_r})\bigr).$$
Genau deshalb konzentriert sich der Algorithmus auf Primzahlpotenzen: Sind deren Ordnungen bekannt, entsteht jedes zusammengesetzte \(n\) nur noch durch Faktorisierung und eine \(\operatorname{lcm}\)-Verkettung.
Nimm
$$n=35=5\cdot 7.$$
Für \(p=5\) gilt \(\left(\frac{7}{5}\right)=\left(\frac{2}{5}\right)=-1\), also \(g(5)\mid 24\). Mit Paararithmetik modulo \(5\) erhält man
$$u^2=(3,2),\qquad u^3=(2,0).$$
Daraus folgt
$$u^{12}=(2,0)^4=(1,0),\qquad u^6=(2,0)^2=(4,0)\ne (1,0),$$
also
$$g(5)=12.$$
Für \(p=7\) liefert Schritt 3 bereits
$$g(7)=7.$$
Damit ergibt sich
$$g(35)=\operatorname{lcm}(12,7)=84.$$
Dieses kleine Beispiel spiegelt exakt die vollständige Methode wider: Primordnungen bestimmen, gegebenenfalls heben und danach per CRT zusammenführen.
Da alle Vielfachen von \(2\) oder \(3\) den Beitrag \(0\) liefern, kann man die Gesamtsumme als
$$G(N)=\sum_{\substack{2\le n\le N\\ \gcd(n,6)=1}} g(n)$$
schreiben. Das Problem ist also kein separates Probieren für jedes \(n\), sondern eine Vorverarbeitungsaufgabe: alle Primzahlpotenz-Ordnungen bis \(N\) vorberechnen, jedes zulässige \(n\) faktorisieren, die Beiträge per \(\operatorname{lcm}\) kombinieren und aufsummieren.
Die C++-, Python- und Java-Implementierungen folgen demselben Ablauf. Zuerst stellen sie \(a+b\sqrt7\) als Paar dar und verwenden binäre Exponentiation, um schnell zu testen, ob ein Kandidatenexponent \(u\) modulo eines gegebenen Modulus wieder auf \(1\) bringt. Dadurch werden Ordnungsprüfungen effizient genug für viele Wiederholungen.
Danach wird ein Sieb der kleinsten Primfaktoren bis \(N\) aufgebaut. Für jede Primzahl \(p\ge 5\) wird per Euler-Kriterium entschieden, ob \(7\) quadratischer Rest ist; daraus folgt die passende obere Schranke für \(g(p)\), die anschließend durch Primfaktor-Tests verkleinert wird. Die Primzahl \(7\) wird im Basisfall separat behandelt, und anschließend werden die Ordnungen auf \(p^2,p^3,\dots\) nach der Regel aus Schritt 3 gehoben.
Am Ende liefert das Sieb für jedes \(n\le N\) mit \(\gcd(n,6)=1\) seine Faktorisierung. Die Implementierung liest die zwischengespeicherten Ordnungen der Primzahlpotenzen ab, bildet ihr \(\operatorname{lcm}\) und addiert den Wert zur laufenden Summe.
Sei \(N\) die Obergrenze. Das Sieb der kleinsten Primfaktoren benötigt \(O(N\log\log N)\) Zeit und \(O(N)\) Speicher. Danach kostet das Faktorisieren eines zulässigen \(n\) im Mittel \(O(\log N)\). Die Vorberechnung für Primzahlen und Primzahlpotenzen verwendet wiederholte binäre Exponentiation für eine begrenzte Zahl von Kandidatenteilern; insgesamt liegt die Laufzeit in der Praxis nahe bei \(O(N\log N)\), bei \(O(N)\) Speicher für Sieb und Primzahlpotenz-Ordnungen.
Şunu yazalım:
$$(1+\sqrt7)^k=a_k+b_k\sqrt7.$$
Her \(n\ge 2\) tamsayısı için \(g(n)\), aşağıdaki koşulu sağlayan en küçük pozitif \(k\) olsun:
$$a_k\equiv 1 \pmod{n},\qquad b_k\equiv 0 \pmod{n}.$$
Böyle bir \(k\) yoksa \(g(n)=0\) alınır. İstenen toplam
$$G(N)=\sum_{n=2}^{N} g(n)$$
ve hedef değer \(N=10^6\)'dır. C++, Python ve Java implementasyonları bunu \(1+\sqrt7\) elemanını \(R_n=(\mathbb Z/n\mathbb Z)[\sqrt7]\) sonlu halkasında ele alıp çarpımsal mertebesini hesaplayarak yapar.
Şunu tanımlayalım:
$$u=1+\sqrt7.$$
O zaman \(g(n)\), \(R_n\) içinde \(u^k=1\) yapan en küçük pozitif üsttür. Çözümün tamamı, bu mertebeyi önce asal kuvvetlerde anlamak, sonra Çin Kalan Teoremi ile bileşik modlara geri kurmak üzerine kuruludur.
\(a+b\sqrt7\) elemanını \((a,b)\) çiftiyle temsil edelim. Çarpma kuralı
$$(a,b)\times(c,d)=\bigl(ac+7bd,\ ad+bc\bigr)\pmod{n}$$
şeklindedir; çünkü \((a+b\sqrt7)(c+d\sqrt7)=(ac+7bd)+(ad+bc)\sqrt7\).
Dolayısıyla \((1+\sqrt7)^k\equiv 1\) demek, \((1,1)\) çiftinin art arda çarpımlarla \((1,0)\) çiftine dönmesi demektir.
\(a+b\sqrt7\) için norm
$$N(a+b\sqrt7)=a^2-7b^2$$
olur. \(u\) için bu değer
$$N(u)=1^2-7\cdot 1^2=-6$$
çıkar. Eğer \(u^k=1\) ise normlar da eşit olacağından
$$(-6)^k\equiv 1 \pmod{n}$$
olmalıdır. Bu, \(n\) sayısı \(2\) ya da \(3\) ile bölünüyorsa imkansızdır. Bu nedenle \(2\) veya \(3\) katı olan tüm modlarda \(g(n)=0\) olur. Tersine, \(\gcd(n,6)=1\) ise \(-6\) tersinirdir; dolayısıyla \(u\) sonlu birim grubunda yer alır ve pozitif bir mertebe mutlaka vardır.
\(p\ge 5\) ve \(p\ne 7\) olan bir asal alalım. Belirleyici nokta, \(7\)'nin \(p\) modunda karesel artık olup olmamasıdır. Euler kriterine göre
$$\left(\frac{7}{p}\right)\equiv 7^{(p-1)/2}\pmod{p}\in\{1,-1\}.$$
Eğer \(\left(\frac{7}{p}\right)=1\) ise \(x^2-7\), \(p\) modunda iki farklı lineer çarpana ayrılır. Böylece
$$R_p\cong \mathbb F_p\times \mathbb F_p,$$
ve her birim elemanın mertebesi \(p-1\)'i böler. Özellikle
$$g(p)\mid (p-1).$$
Eğer \(\left(\frac{7}{p}\right)=-1\) ise \(x^2-7\), \(p\) modunda indirgenemez; bu durumda \(R_p\), \(\mathbb F_{p^2}\) cismidir. Çarpımsal grubun büyüklüğü \(p^2-1\) olduğundan
$$g(p)\mid (p^2-1)=(p-1)(p+1).$$
Uygulama uygun üst sınırla başlar ve bu sınırın asal bölenlerini tek tek dener. \(u^{M/q}=1\) testi sağlanıyorsa mevcut sınır \(M\), \(q\) ile küçültülür.
\(7\) asalı özel davranır; çünkü
$$x^2-7\equiv x^2 \pmod{7}.$$
\(7\) modunda \(\varepsilon=\sqrt7\) yazarsak \(\varepsilon^2=0\) olur ve binom açılımı
$$(1+\varepsilon)^k=1+k\varepsilon \pmod{7}$$
şeklinde sadeleşir. Bu ifade ancak \(k\equiv 0\pmod{7}\) iken \(1\)'e eşittir. Dolayısıyla
$$g(7)=7.$$
Daha yüksek asal kuvvetlerde \(t=g(p^e)\) olsun. \(p^e\)'ye indirgeme, \(g(p^{e+1})\)'nin \(t\)'nin katı olması gerektiğini gösterir; ek çarpan da yalnızca bir tane daha \(p\) olabilir. Bu yüzden
$$g(p^{e+1})\in\{t,\ pt\}$$
olur. Implementasyon bunu doğrudan sınar: \(u^t\equiv 1\pmod{p^{e+1}}\) ise mertebe değişmez, değilse \(p\) ile çarpılır.
Şimdi
$$n=\prod_{i=1}^{r} p_i^{e_i},\qquad \gcd(n,6)=1$$
olsun. Çin Kalan Teoremi halka ayrışımını verir:
$$R_n\cong \prod_{i=1}^{r} R_{p_i^{e_i}}.$$
\(u\) elemanı bu çarpımda her asal kuvvet için bir bileşene sahiptir. Bir üssün tüm çarpımda \(1\) elde etmesi için her bileşende de \(1\) vermesi gerekir. O halde
$$g(n)=\operatorname{lcm}\bigl(g(p_1^{e_1}),g(p_2^{e_2}),\dots,g(p_r^{e_r})\bigr).$$
Algoritmanın önce asal kuvvet mertebelerini önbelleğe almasının nedeni tam olarak budur: bileşik bir \(n\) için geriye sadece çarpanlara ayırma ve bir \(\operatorname{lcm}\) zinciri kalır.
Şunu ele alalım:
$$n=35=5\cdot 7.$$
\(p=5\) için \(\left(\frac{7}{5}\right)=\left(\frac{2}{5}\right)=-1\), dolayısıyla \(g(5)\mid 24\). Mod \(5\) altında çift aritmetiği ile
$$u^2=(3,2),\qquad u^3=(2,0)$$
elde edilir. Buradan
$$u^{12}=(2,0)^4=(1,0),\qquad u^6=(2,0)^2=(4,0)\ne (1,0)$$
olduğu için
$$g(5)=12$$
sonucu çıkar. \(p=7\) için ise Adım 3 doğrudan
$$g(7)=7$$
verir. İkisini birleştirince
$$g(35)=\operatorname{lcm}(12,7)=84$$
olur. Bu küçük örnek, gerçek çözümün kullandığı akışın aynısını gösterir: asal mertebeleri bul, gerekiyorsa asal kuvvetlere kaldır, sonra CRT ile birleştir.
\(2\) veya \(3\) katları zaten \(0\) katkı verdiği için toplam
$$G(N)=\sum_{\substack{2\le n\le N\\ \gcd(n,6)=1}} g(n)$$
şeklinde yazılabilir. Böylece problem, her \(n\) için bağımsız kuvvet araması yapmak yerine bir ön işleme problemine dönüşür: \(N\)'e kadar tüm asal kuvvet mertebelerini hazırla, her uygun \(n\)'i çarpanlarına ayır, \(\operatorname{lcm}\) ile birleştir ve topla.
C++, Python ve Java implementasyonlarının akışı aynıdır. Önce \(a+b\sqrt7\) çifti üzerinde hızlı üs alma kullanılır; böylece belirli bir üssün, seçilen mod altında \(u\) elemanını yeniden \(1\)'e götürüp götürmediği hızlıca test edilir. Mertebe aramasının temel işlemi budur.
Sonra \(N\)'e kadar en küçük asal bölen tablosu kurulur. Her \(p\ge 5\) asalı için Euler kriteriyle \(7\)'nin karesel artık olup olmadığı belirlenir; buna göre \(g(p)\) için uygun üst sınır seçilir ve asal bölen testleriyle küçültülür. İstisnai asal \(7\) taban durumda ayrı ele alınır, ardından mertebeler \(p^2,p^3,\dots\) boyunca Adım 3'teki kuralla yükseltilir.
Son aşamada, \(\gcd(n,6)=1\) olan her \(n\le N\) için sieve tablosu çarpanlara ayırmayı verir. Implementasyon, ilgili asal kuvvet mertebelerini önbellekten alır, bunların \(\operatorname{lcm}\)'ini hesaplar ve sonucu toplam cevaba ekler.
Üst sınır \(N\) olsun. En küçük asal bölen eleği \(O(N\log\log N)\) zamanda kurulur ve \(O(N)\) bellek kullanır. Bundan sonra uygun bir \(n\)'in çarpanlara ayrılması ortalama \(O(\log N)\) sürer. Asallar ve asal kuvvetler için yapılan ön işleme kısmında, sınırlı sayıda aday bölen üzerinde hızlı üs alma testleri vardır; toplam çalışma pratikte \(O(N\log N)\) civarındadır. Bellek kullanımı sieve ve asal kuvvet mertebe tablosu nedeniyle \(O(N)\)'dir.
Escribimos
$$(1+\sqrt7)^k=a_k+b_k\sqrt7.$$
Para cada entero \(n\ge 2\), definimos \(g(n)\) como el menor \(k>0\) tal que
$$a_k\equiv 1 \pmod{n},\qquad b_k\equiv 0 \pmod{n};$$
si no existe tal \(k\), entonces \(g(n)=0\). El objetivo es calcular
$$G(N)=\sum_{n=2}^{N} g(n)$$
para \(N=10^6\). Las implementaciones en C++, Python y Java reinterpretan \(1+\sqrt7\) como un elemento del anillo finito \(R_n=(\mathbb Z/n\mathbb Z)[\sqrt7]\) y calculan allí su orden multiplicativo.
Sea
$$u=1+\sqrt7.$$
Entonces \(g(n)\) es exactamente el menor exponente positivo \(k\) para el cual \(u^k=1\) en \(R_n\). La idea central consiste en entender este orden para cada potencia prima y después recomponer los módulos compuestos mediante el teorema chino del resto.
Representamos \(a+b\sqrt7\) por el par \((a,b)\). La multiplicación queda
$$(a,b)\times(c,d)=\bigl(ac+7bd,\ ad+bc\bigr)\pmod{n},$$
porque \((a+b\sqrt7)(c+d\sqrt7)=(ac+7bd)+(ad+bc)\sqrt7\).
Así, comprobar \((1+\sqrt7)^k\equiv 1\) equivale a comprobar que el par \((1,1)\) llega a \((1,0)\) tras multiplicación repetida.
La norma de \(a+b\sqrt7\) es
$$N(a+b\sqrt7)=a^2-7b^2.$$
Para \(u\) resulta
$$N(u)=1^2-7\cdot 1^2=-6.$$
Si \(u^k=1\) módulo \(n\), entonces al tomar normas se obtiene
$$(-6)^k\equiv 1 \pmod{n}.$$
Eso es imposible cuando \(n\) es divisible por \(2\) o por \(3\), de modo que en esos casos \(g(n)=0\). En cambio, si \(\gcd(n,6)=1\), la norma es invertible y \(u\) pertenece al grupo de unidades de un anillo finito, así que necesariamente tiene orden positivo.
Sea \(p\ge 5\) primo con \(p\ne 7\). Lo importante es decidir si \(7\) es residuo cuadrático módulo \(p\). Por el criterio de Euler,
$$\left(\frac{7}{p}\right)\equiv 7^{(p-1)/2}\pmod{p}\in\{1,-1\}.$$
Si \(\left(\frac{7}{p}\right)=1\), entonces \(x^2-7\) se descompone en dos factores lineales distintos módulo \(p\), y por tanto
$$R_p\cong \mathbb F_p\times \mathbb F_p.$$
Cada unidad de este producto tiene orden divisor de \(p-1\), así que
$$g(p)\mid (p-1).$$
Si \(\left(\frac{7}{p}\right)=-1\), entonces \(x^2-7\) es irreducible módulo \(p\), de modo que \(R_p\) es el cuerpo \(\mathbb F_{p^2}\). Su grupo multiplicativo tiene tamaño \(p^2-1\), luego
$$g(p)\mid (p^2-1)=(p-1)(p+1).$$
La implementación parte de esta cota superior y va quitando factores primos. Siempre que \(u^{M/q}=1\), la cota actual \(M\) puede dividirse por \(q\).
El primo \(7\) es especial porque
$$x^2-7\equiv x^2 \pmod{7}.$$
Si escribimos \(\varepsilon=\sqrt7\) módulo \(7\), entonces \(\varepsilon^2=0\), y el binomio se simplifica a
$$(1+\varepsilon)^k=1+k\varepsilon \pmod{7}.$$
Esto es igual a \(1\) exactamente cuando \(k\equiv 0\pmod{7}\), así que
$$g(7)=7.$$
Para una potencia prima mayor, sea \(t=g(p^e)\). La reducción módulo \(p^e\) obliga a que \(g(p^{e+1})\) sea múltiplo de \(t\), y el cociente adicional solo puede aportar una potencia más de \(p\). Por tanto, las únicas opciones son
$$g(p^{e+1})\in\{t,\ pt\}.$$
La implementación lo comprueba directamente: si \(u^t\equiv 1\pmod{p^{e+1}}\), el orden permanece en \(t\); si no, pasa a \(pt\).
Supongamos ahora que
$$n=\prod_{i=1}^{r} p_i^{e_i},\qquad \gcd(n,6)=1.$$
El teorema chino del resto da la descomposición
$$R_n\cong \prod_{i=1}^{r} R_{p_i^{e_i}}.$$
La imagen de \(u\) tiene una componente en cada anillo de potencia prima. Un exponente anula el producto completo si y solo si anula cada componente, por lo que
$$g(n)=\operatorname{lcm}\bigl(g(p_1^{e_1}),g(p_2^{e_2}),\dots,g(p_r^{e_r})\bigr).$$
Por eso el algoritmo se apoya en una caché de órdenes para potencias primas: una vez precalculadas, cualquier \(n\) compuesto se resuelve mediante factorización y una cadena de \(\operatorname{lcm}\).
Tomemos
$$n=35=5\cdot 7.$$
Para \(p=5\), se tiene \(\left(\frac{7}{5}\right)=\left(\frac{2}{5}\right)=-1\), así que \(g(5)\mid 24\). Con aritmética de pares módulo \(5\),
$$u^2=(3,2),\qquad u^3=(2,0).$$
Entonces
$$u^{12}=(2,0)^4=(1,0),\qquad u^6=(2,0)^2=(4,0)\ne (1,0),$$
de donde
$$g(5)=12.$$
Para \(p=7\), el Paso 3 ya mostró que
$$g(7)=7.$$
Finalmente,
$$g(35)=\operatorname{lcm}(12,7)=84.$$
Este ejemplo pequeño reproduce exactamente la lógica completa de la solución: calcular órdenes primos, levantarlos si hace falta y combinarlos mediante CRT.
Como todos los múltiplos de \(2\) o \(3\) aportan \(0\), la suma total puede escribirse como
$$G(N)=\sum_{\substack{2\le n\le N\\ \gcd(n,6)=1}} g(n).$$
Así, el problema deja de ser una búsqueda independiente para cada \(n\) y pasa a ser una tarea de preprocesamiento: calcular todas las órdenes de potencias primas hasta \(N\), factorizar cada \(n\) admisible, tomar el \(\operatorname{lcm}\) de sus contribuciones y acumular el resultado.
Las implementaciones en C++, Python y Java siguen la misma secuencia. Primero representan \(a+b\sqrt7\) como un par y usan exponenciación binaria para comprobar rápidamente si un exponente candidato hace que \(u\) vuelva a \(1\) bajo un módulo dado. Ese es el bloque fundamental de todas las pruebas de orden.
Después construyen una criba del menor factor primo hasta \(N\). Para cada primo \(p\ge 5\), determinan con el criterio de Euler si \(7\) es o no un residuo cuadrático, escogen la cota superior correcta para \(g(p)\) y la reducen comprobando divisores primos. El primo \(7\) se trata por separado en el caso base, y luego las órdenes se levantan a \(p^2,p^3,\dots\) siguiendo la regla del Paso 3.
Por último, para cada \(n\le N\) con \(\gcd(n,6)=1\), la criba proporciona su factorización. La implementación consulta el orden almacenado de cada potencia prima, calcula su \(\operatorname{lcm}\) y añade ese valor a la suma acumulada.
Sea \(N\) el límite de búsqueda. Construir la criba del menor factor primo cuesta \(O(N\log\log N)\) tiempo y \(O(N)\) memoria. Factorizar un \(n\) admisible requiere en promedio \(O(\log N)\). El preprocesamiento de primos y potencias primas usa exponenciación binaria repetida para un número moderado de divisores candidatos, así que el tiempo total queda cerca de \(O(N\log N)\) en la práctica, con \(O(N)\) memoria para la criba y la tabla de órdenes de potencias primas.
把
$$(1+\sqrt7)^k=a_k+b_k\sqrt7$$
展开。对每个整数 \(n\ge 2\)，定义 \(g(n)\) 为满足
$$a_k\equiv 1 \pmod{n},\qquad b_k\equiv 0 \pmod{n}$$
的最小正整数 \(k\)；如果这样的 \(k\) 不存在，就令 \(g(n)=0\)。题目要求计算
$$G(N)=\sum_{n=2}^{N} g(n)$$
在 \(N=10^6\) 时的值。C++、Python 和 Java 实现都把 \(1+\sqrt7\) 放到有限环 \(R_n=(\mathbb Z/n\mathbb Z)[\sqrt7]\) 中来处理，并把 \(g(n)\) 解释为这个元素在该环单位群中的乘法阶。
记
$$u=1+\sqrt7.$$
那么 \(g(n)\) 就是使 \(u^k=1\) 在 \(R_n\) 中成立的最小正指数。整个解法的关键，是先逐个分析素数幂模数上的阶，再用中国剩余定理把合数模数恢复出来。
把元素 \(a+b\sqrt7\) 表示为二元组 \((a,b)\)。乘法规则是
$$(a,b)\times(c,d)=\bigl(ac+7bd,\ ad+bc\bigr)\pmod{n},$$
因为
$$(a+b\sqrt7)(c+d\sqrt7)=(ac+7bd)+(ad+bc)\sqrt7.$$
所以判断 \((1+\sqrt7)^k\equiv 1\) 是否成立，等价于判断从 \((1,1)\) 出发反复做这种乘法，最终是否到达 \((1,0)\)。
\(a+b\sqrt7\) 的范数为
$$N(a+b\sqrt7)=a^2-7b^2.$$
对 \(u\) 来说，
$$N(u)=1^2-7\cdot 1^2=-6.$$
如果 \(u^k=1\) 模 \(n\)，那么取范数后必须有
$$(-6)^k\equiv 1 \pmod{n}.$$
当 \(n\) 被 \(2\) 或 \(3\) 整除时，这显然不可能成立，因此所有 \(2\) 的倍数或 \(3\) 的倍数都满足 \(g(n)=0\)。反过来，如果 \(\gcd(n,6)=1\)，那么 \(-6\) 在模 \(n\) 下可逆，\(u\) 就是有限单位群中的一个元素，因此一定存在某个正整数阶。
设 \(p\ge 5\) 是素数且 \(p\ne 7\)。关键问题是 \(7\) 在模 \(p\) 下是不是二次剩余。由 Euler 判别法，
$$\left(\frac{7}{p}\right)\equiv 7^{(p-1)/2}\pmod{p}\in\{1,-1\}.$$
如果 \(\left(\frac{7}{p}\right)=1\)，那么 \(x^2-7\) 在模 \(p\) 下分解成两个不同的一次因子，于是
$$R_p\cong \mathbb F_p\times \mathbb F_p.$$
这个直积中的每个单位分量都落在 \(\mathbb F_p^\times\) 里，所以其阶一定整除 \(p-1\)。因此
$$g(p)\mid (p-1).$$
如果 \(\left(\frac{7}{p}\right)=-1\)，那么 \(x^2-7\) 在模 \(p\) 下不可约，此时 \(R_p\) 就是域 \(\mathbb F_{p^2}\)。它的乘法群大小是 \(p^2-1\)，于是
$$g(p)\mid (p^2-1)=(p-1)(p+1).$$
实现先从这个上界出发，然后按素因子逐个尝试缩小它。只要某个因子 \(q\) 满足 \(u^{M/q}=1\)，当前候选阶 \(M\) 就可以再除以 \(q\)。
素数 \(7\) 是例外，因为
$$x^2-7\equiv x^2 \pmod{7}.$$
设 \(\varepsilon=\sqrt7\) 在模 \(7\) 下的像，那么 \(\varepsilon^2=0\)。这样一来，二项式展开直接退化为
$$(1+\varepsilon)^k=1+k\varepsilon \pmod{7}.$$
它等于 \(1\) 当且仅当 \(k\equiv 0\pmod{7}\)，所以
$$g(7)=7.$$
接着看更高的素数幂。设 \(t=g(p^e)\)。模 \(p^e\) 的约化说明 \(g(p^{e+1})\) 必须是 \(t\) 的倍数，而从 \(p^e\) 提升到 \(p^{e+1}\) 这一层时，额外增加的部分至多再多一个因子 \(p\)。因此只可能出现
$$g(p^{e+1})\in\{t,\ pt\}.$$
实现直接测试这两种情况：如果 \(u^t\equiv 1\pmod{p^{e+1}}\)，阶保持为 \(t\)；否则阶变成 \(pt\)。
设
$$n=\prod_{i=1}^{r} p_i^{e_i},\qquad \gcd(n,6)=1.$$
由中国剩余定理可得
$$R_n\cong \prod_{i=1}^{r} R_{p_i^{e_i}}.$$
元素 \(u\) 在这个直积里有若干个分量。一个指数想让整个直积中的元素回到 \(1\)，就必须同时让每个分量都回到 \(1\)。因此
$$g(n)=\operatorname{lcm}\bigl(g(p_1^{e_1}),g(p_2^{e_2}),\dots,g(p_r^{e_r})\bigr).$$
这说明为什么算法会先把所有素数幂的答案缓存下来：一旦局部阶都准备好了，任意合数 \(n\) 只需要分解质因数，然后做一条 \(\operatorname{lcm}\) 链即可。
考虑
$$n=35=5\cdot 7.$$
对 \(p=5\)，有 \(\left(\frac{7}{5}\right)=\left(\frac{2}{5}\right)=-1\)，所以 \(g(5)\mid 24\)。在模 \(5\) 的二元组乘法下，
$$u^2=(3,2),\qquad u^3=(2,0).$$
于是
$$u^{12}=(2,0)^4=(1,0),\qquad u^6=(2,0)^2=(4,0)\ne (1,0),$$
从而得到
$$g(5)=12.$$
而对 \(p=7\)，步骤 3 已经说明
$$g(7)=7.$$
把两个局部结果合并，就有
$$g(35)=\operatorname{lcm}(12,7)=84.$$
这个例子完整演示了实现所做的事情：先求素数模数上的阶，必要时提升到素数幂，再通过中国剩余定理把它们合成为合数模数上的答案。
因为所有 \(2\) 的倍数和 \(3\) 的倍数都贡献 \(0\)，总和可以写成
$$G(N)=\sum_{\substack{2\le n\le N\\ \gcd(n,6)=1}} g(n).$$
这样一来，题目就不再是“对每个 \(n\) 单独暴力搜索幂次”，而变成了一个预处理问题：先求出所有不超过 \(N\) 的素数幂局部阶，再把每个可行的 \(n\) 分解质因数、取对应局部阶的最小公倍数，并加入总和。
C++、Python 和 Java 实现采用完全相同的流程。第一步是用二元组表示 \(a+b\sqrt7\)，并通过二进制快速幂来测试某个候选指数是否能把 \(u\) 送回单位元 \(1\)。这样，阶的判定就变得足够高效，可以在预处理阶段反复使用。
接下来，程序建立一个到 \(N\) 为止的最小质因子表。对每个 \(p\ge 5\) 的素数，先用 Euler 判别法判断 \(7\) 是否为二次剩余，据此选定 \(g(p)\) 的上界，再通过试除这些上界的素因子来缩小阶。特殊素数 \(7\) 单独作为基例处理，而更高的 \(p^2,p^3,\dots\) 则用步骤 3 的提升规则递推出来。
最后，对于每个满足 \(\gcd(n,6)=1\) 的 \(n\le N\)，最小质因子表直接给出它的分解。实现读取对应素数幂的缓存阶，取它们的 \(\operatorname{lcm}\)，再累加到最终答案里。
设上界为 \(N\)。构造最小质因子表需要 \(O(N\log\log N)\) 时间和 \(O(N)\) 空间。此后，每个可行的 \(n\) 都能在平均 \(O(\log N)\) 时间内完成分解。素数与素数幂部分的预处理，需要对少量候选因子执行快速幂测试，因此整体运行时间在实践中接近 \(O(N\log N)\)，空间复杂度为 \(O(N)\)，主要来自筛表和素数幂阶缓存。
Запишем
$$(1+\sqrt7)^k=a_k+b_k\sqrt7.$$
Для каждого целого \(n\ge 2\) обозначим через \(g(n)\) наименьшее положительное \(k\), для которого
$$a_k\equiv 1 \pmod{n},\qquad b_k\equiv 0 \pmod{n};$$
если такого \(k\) нет, то \(g(n)=0\). Требуется вычислить
$$G(N)=\sum_{n=2}^{N} g(n)$$
при \(N=10^6\). Реализации на C++, Python и Java рассматривают \(1+\sqrt7\) как элемент конечного кольца \(R_n=(\mathbb Z/n\mathbb Z)[\sqrt7]\) и ищут его мультипликативный порядок там, где этот порядок существует.
Положим
$$u=1+\sqrt7.$$
Тогда \(g(n)\) есть минимальный положительный показатель \(k\), для которого \(u^k=1\) в \(R_n\). Всё решение строится на том, чтобы понять этот порядок сначала для степеней простых чисел, а затем собрать составные модули с помощью китайской теоремы об остатках.
Элемент \(a+b\sqrt7\) представляется парой \((a,b)\). Умножение имеет вид
$$(a,b)\times(c,d)=\bigl(ac+7bd,\ ad+bc\bigr)\pmod{n},$$
поскольку
$$(a+b\sqrt7)(c+d\sqrt7)=(ac+7bd)+(ad+bc)\sqrt7.$$
Следовательно, проверка \((1+\sqrt7)^k\equiv 1\) сводится к проверке того, что повторное умножение переводит \((1,1)\) в \((1,0)\).
Норма элемента \(a+b\sqrt7\) равна
$$N(a+b\sqrt7)=a^2-7b^2.$$
Для \(u\) получаем
$$N(u)=1^2-7\cdot 1^2=-6.$$
Если \(u^k=1\) по модулю \(n\), то из равенства норм следует
$$(-6)^k\equiv 1 \pmod{n}.$$
Это невозможно, если \(n\) делится на \(2\) или на \(3\). Значит, для всех таких модулей \(g(n)=0\). Если же \(\gcd(n,6)=1\), то \(-6\) обратим по модулю \(n\), элемент \(u\) является единицей в конечной группе, и положительный порядок обязательно существует.
Пусть \(p\ge 5\) - простое число, \(p\ne 7\). Нужно понять, является ли \(7\) квадратичным вычетом по модулю \(p\). По критерию Эйлера,
$$\left(\frac{7}{p}\right)\equiv 7^{(p-1)/2}\pmod{p}\in\{1,-1\}.$$
Если \(\left(\frac{7}{p}\right)=1\), то многочлен \(x^2-7\) раскладывается на два различных линейных множителя, и потому
$$R_p\cong \mathbb F_p\times \mathbb F_p.$$
Порядок любой единицы в таком произведении делит \(p-1\), следовательно
$$g(p)\mid (p-1).$$
Если \(\left(\frac{7}{p}\right)=-1\), то \(x^2-7\) неприводим по модулю \(p\), и \(R_p\) является полем \(\mathbb F_{p^2}\). Его мультипликативная группа имеет размер \(p^2-1\), значит
$$g(p)\mid (p^2-1)=(p-1)(p+1).$$
Реализация стартует с этой верхней оценки и по одному удаляет простые множители. Если для некоторого делителя \(q\) выполняется \(u^{M/q}=1\), текущая оценка \(M\) уменьшается в \(q\) раз.
Простой \(7\) особый, потому что
$$x^2-7\equiv x^2 \pmod{7}.$$
Если обозначить через \(\varepsilon=\sqrt7\) образ корня по модулю \(7\), то \(\varepsilon^2=0\). Тогда биномиальная формула схлопывается в
$$(1+\varepsilon)^k=1+k\varepsilon \pmod{7}.$$
Это равно \(1\) тогда и только тогда, когда \(k\equiv 0\pmod{7}\), поэтому
$$g(7)=7.$$
Теперь пусть \(t=g(p^e)\). Сведение по модулю \(p^e\) показывает, что \(g(p^{e+1})\) обязано быть кратно \(t\), а дополнительный множитель может дать только ещё одну степень \(p\). Значит, возможны лишь два случая:
$$g(p^{e+1})\in\{t,\ pt\}.$$
Реализация проверяет это напрямую: если \(u^t\equiv 1\pmod{p^{e+1}}\), порядок остаётся равным \(t\); иначе он умножается на \(p\).
Пусть
$$n=\prod_{i=1}^{r} p_i^{e_i},\qquad \gcd(n,6)=1.$$
Тогда китайская теорема об остатках даёт разложение
$$R_n\cong \prod_{i=1}^{r} R_{p_i^{e_i}}.$$
Образ \(u\) в этом произведении имеет по одной компоненте в каждом кольце по модулю степени простого. Экспонента возвращает весь элемент к \(1\) тогда и только тогда, когда она возвращает к \(1\) каждую компоненту. Следовательно,
$$g(n)=\operatorname{lcm}\bigl(g(p_1^{e_1}),g(p_2^{e_2}),\dots,g(p_r^{e_r})\bigr).$$
Именно поэтому алгоритм заранее вычисляет ответы для степеней простых чисел: после этого для любого составного \(n\) остаётся лишь факторизация и цепочка вычислений \(\operatorname{lcm}\).
Возьмём
$$n=35=5\cdot 7.$$
Для \(p=5\) имеем \(\left(\frac{7}{5}\right)=\left(\frac{2}{5}\right)=-1\), значит \(g(5)\mid 24\). В парной арифметике по модулю \(5\) получаем
$$u^2=(3,2),\qquad u^3=(2,0).$$
Отсюда
$$u^{12}=(2,0)^4=(1,0),\qquad u^6=(2,0)^2=(4,0)\ne (1,0),$$
то есть
$$g(5)=12.$$
Для \(p=7\) шаг 3 уже дал
$$g(7)=7.$$
Поэтому
$$g(35)=\operatorname{lcm}(12,7)=84.$$
Этот маленький пример в точности повторяет полную схему решения: сначала порядки по простым модулям, затем при необходимости подъём к степеням простого, и наконец склейка по CRT.
Поскольку все кратные \(2\) и \(3\) дают вклад \(0\), суммарную функцию удобно переписать так:
$$G(N)=\sum_{\substack{2\le n\le N\\ \gcd(n,6)=1}} g(n).$$
Тем самым задача перестаёт быть отдельным поиском степеней для каждого \(n\). Она превращается в задачу предварительных вычислений: найти все порядки для степеней простых чисел до \(N\), разложить каждый допустимый \(n\), взять \(\operatorname{lcm}\) соответствующих локальных ответов и прибавить его к общей сумме.
Реализации на C++, Python и Java следуют одной и той же схеме. Сначала они представляют \(a+b\sqrt7\) как пару и используют бинарное возведение в степень, чтобы быстро проверять, возвращает ли выбранный показатель элемент \(u\) к единице по заданному модулю. Именно на этом построены все тесты порядка.
Затем строится таблица наименьших простых делителей до \(N\). Для каждого простого \(p\ge 5\) по критерию Эйлера определяется, является ли \(7\) квадратичным вычетом, выбирается правильная верхняя граница для \(g(p)\), и эта граница уменьшается проверкой её простых делителей. Особый простой \(7\) обрабатывается отдельно в базовом случае, а дальше порядки последовательно поднимаются к \(p^2,p^3,\dots\) по правилу из шага 3.
После этого для каждого \(n\le N\) с \(\gcd(n,6)=1\) факторизация получается из таблицы почти мгновенно. Код берёт сохранённые порядки соответствующих степеней простых чисел, вычисляет их \(\operatorname{lcm}\) и добавляет результат к накопленной сумме.
Пусть верхняя граница равна \(N\). Построение таблицы наименьших простых делителей занимает \(O(N\log\log N)\) времени и \(O(N)\) памяти. После этого факторизация одного допустимого \(n\) в среднем стоит \(O(\log N)\). Предварительные вычисления для простых чисел и их степеней используют бинарное возведение в степень для умеренного числа кандидатных делителей, поэтому полное время работы на практике близко к \(O(N\log N)\). Память остаётся \(O(N)\), поскольку хранятся таблица делителей и кэш порядков для степеней простых.
نكتب
$$(1+\sqrt7)^k=a_k+b_k\sqrt7.$$
ولكل عدد صحيح \(n\ge 2\)، نعرّف \(g(n)\) بأنه أصغر \(k\) موجب يحقق
$$a_k\equiv 1 \pmod{n},\qquad b_k\equiv 0 \pmod{n};$$
وإذا لم يوجد مثل هذا \(k\) فنأخذ \(g(n)=0\). المطلوب هو حساب
$$G(N)=\sum_{n=2}^{N} g(n)$$
عند \(N=10^6\). تعتمد تطبيقات C++ وPython وJava على النظر إلى \(1+\sqrt7\) بوصفه عنصراً في الحلقة المنتهية \(R_n=(\mathbb Z/n\mathbb Z)[\sqrt7]\)، ثم حساب رتبته الضربية كلما كانت هذه الرتبة موجودة.
لنضع
$$u=1+\sqrt7.$$
عندئذ تكون \(g(n)\) هي أصغر أسّ موجب يجعل \(u^k=1\) داخل \(R_n\). الفكرة الأساسية في الحل هي فهم هذه الرتبة أولاً على قوى الأعداد الأولية، ثم إعادة بناء حالة العدد المركب باستعمال مبرهنة البواقي الصينية.
نمثل العنصر \(a+b\sqrt7\) بالزوج \((a,b)\). وعندها تصبح عملية الضرب
$$(a,b)\times(c,d)=\bigl(ac+7bd,\ ad+bc\bigr)\pmod{n},$$
لأن
$$(a+b\sqrt7)(c+d\sqrt7)=(ac+7bd)+(ad+bc)\sqrt7.$$
إذن التحقق من أن \((1+\sqrt7)^k\equiv 1\) يكافئ التحقق من أن الضرب المتكرر ينقل \((1,1)\) إلى \((1,0)\).
نورم العنصر \(a+b\sqrt7\) هو
$$N(a+b\sqrt7)=a^2-7b^2.$$
وبالنسبة إلى \(u\) نحصل على
$$N(u)=1^2-7\cdot 1^2=-6.$$
إذا تحقق \(u^k=1\) بترديد \(n\)، فلا بد بعد أخذ النورم من أن يكون
$$(-6)^k\equiv 1 \pmod{n}.$$
وهذا مستحيل إذا كان \(n\) يقبل القسمة على \(2\) أو \(3\). لذلك كل مضاعف لـ \(2\) أو \(3\) يعطي \(g(n)=0\). أما إذا كان \(\gcd(n,6)=1\)، فإن \(-6\) يكون معكوساً بترديد \(n\)، وبالتالي يكون \(u\) عنصراً وحدوياً في مجموعة منتهية، ومن ثم توجد له رتبة موجبة حتماً.
ليكن \(p\ge 5\) عدداً أولياً و\(p\ne 7\). السؤال الحاسم هو: هل \(7\) بقايا تربيعية بترديد \(p\) أم لا؟ وفق معيار أويلر،
$$\left(\frac{7}{p}\right)\equiv 7^{(p-1)/2}\pmod{p}\in\{1,-1\}.$$
إذا كان \(\left(\frac{7}{p}\right)=1\)، فإن \(x^2-7\) ينشطر إلى عاملين خطيين مختلفين بترديد \(p\)، ومن ثم
$$R_p\cong \mathbb F_p\times \mathbb F_p.$$
كل عنصر وحدوي في هذا الجداء له رتبة تقسم \(p-1\)، ولذلك
$$g(p)\mid (p-1).$$
أما إذا كان \(\left(\frac{7}{p}\right)=-1\)، فإن \(x^2-7\) يكون غير قابل للاختزال بترديد \(p\)، وعندها تصبح \(R_p\) هي الحقل \(\mathbb F_{p^2}\). زمرة الضرب فيه عدد عناصرها \(p^2-1\)، لذا
$$g(p)\mid (p^2-1)=(p-1)(p+1).$$
تنطلق التطبيقات من هذا الحد الأعلى، ثم تحاول حذف عوامله الأولية واحداً بعد آخر. كلما تحقق الشرط \(u^{M/q}=1\)، أمكن تقليص الحد الحالي \(M\) بقسمة \(q\).
العدد الأولي \(7\) حالة خاصة لأن
$$x^2-7\equiv x^2 \pmod{7}.$$
إذا كتبنا \(\varepsilon=\sqrt7\) بترديد \(7\)، فلدينا \(\varepsilon^2=0\)، ومن ثم ينهار توسع ذي الحدين إلى
$$(1+\varepsilon)^k=1+k\varepsilon \pmod{7}.$$
وهذا يساوي \(1\) بالضبط عندما \(k\equiv 0\pmod{7}\)، ولذلك
$$g(7)=7.$$
الآن لنفترض أن \(t=g(p^e)\). إن الاختزال بترديد \(p^e\) يبيّن أن \(g(p^{e+1})\) لا بد أن يكون مضاعفاً لـ \(t\)، والزيادة الممكنة عند الانتقال إلى مستوى أعلى لا تتجاوز عاملاً إضافياً واحداً من \(p\). لذا لا توجد إلا حالتان:
$$g(p^{e+1})\in\{t,\ pt\}.$$
وتفحص التطبيقات ذلك مباشرة: إذا كان \(u^t\equiv 1\pmod{p^{e+1}}\) بقيت الرتبة كما هي، وإلا ضُربت في \(p\).
افترض أن
$$n=\prod_{i=1}^{r} p_i^{e_i},\qquad \gcd(n,6)=1.$$
عندئذ تعطي مبرهنة البواقي الصينية التفكيك
$$R_n\cong \prod_{i=1}^{r} R_{p_i^{e_i}}.$$
وللعنصر \(u\) مركبة في كل حلقة من هذه الحلقات. ولكي يعود العنصر كله إلى \(1\)، يجب أن تعود كل مركبة إلى \(1\) في الوقت نفسه. لذلك
$$g(n)=\operatorname{lcm}\bigl(g(p_1^{e_1}),g(p_2^{e_2}),\dots,g(p_r^{e_r})\bigr).$$
ولهذا السبب تحديداً تحسب الخوارزمية رتب قوى الأوليات أولاً وتخزنها: بعد ذلك يصبح كل \(n\) مركب مجرد عملية تحليل إلى عوامل أولية ثم سلسلة من عمليات \(\operatorname{lcm}\).
لنأخذ
$$n=35=5\cdot 7.$$
بالنسبة إلى \(p=5\)، لدينا \(\left(\frac{7}{5}\right)=\left(\frac{2}{5}\right)=-1\)، ولذلك \(g(5)\mid 24\). وباستخدام حساب الأزواج بترديد \(5\) نحصل على
$$u^2=(3,2),\qquad u^3=(2,0).$$
ومن ثم
$$u^{12}=(2,0)^4=(1,0),\qquad u^6=(2,0)^2=(4,0)\ne (1,0),$$
أي إن
$$g(5)=12.$$
أما بالنسبة إلى \(p=7\)، فقد أعطت الخطوة 3 مباشرة
$$g(7)=7.$$
وعليه
$$g(35)=\operatorname{lcm}(12,7)=84.$$
هذا المثال الصغير يوضح المنهج الكامل كما هو مطبق فعلياً: نحسب الرتب على العوامل الأولية، نرفعها عند الحاجة إلى قوى أولية أعلى، ثم ندمجها بواسطة مبرهنة البواقي الصينية.
بما أن كل مضاعف لـ \(2\) أو \(3\) يساهم بقيمة \(0\)، يمكن كتابة المجموع الكلي على الصورة
$$G(N)=\sum_{\substack{2\le n\le N\\ \gcd(n,6)=1}} g(n).$$
وهكذا تتحول المسألة من بحث مستقل عن الأس لكل \(n\) إلى مسألة تجهيز مسبق: نحسب جميع رتب قوى الأوليات حتى \(N\)، ونحلل كل \(n\) صالح، ونأخذ \(\operatorname{lcm}\) للمساهمات المحلية، ثم نضيف الناتج إلى الجواب النهائي.
تتبع تطبيقات C++ وPython وJava المسار نفسه. أولاً تُستخدم أزواج \((a,b)\) لتمثيل \(a+b\sqrt7\)، ثم يُستعمل الأس السريع الثنائي لاختبار ما إذا كان أس مرشح يعيد العنصر \(u\) إلى الواحد بترديد معين. هذا هو الاختبار الأساسي الذي تبنى عليه كل خطوات حساب الرتبة.
بعد ذلك تُبنى مصفوفة أصغر عامل أولي حتى \(N\). ولكل أولي \(p\ge 5\) يُحسم، بواسطة معيار أويلر، ما إذا كان \(7\) بقايا تربيعية أم لا، ثم يُختار الحد الأعلى المناسب لـ \(g(p)\) ويُقلص بفحص عوامله الأولية. ويُعالج الأولي \(7\) على نحو منفصل في الحالة الأساسية، ثم تُرفع الرتب إلى \(p^2,p^3,\dots\) وفق القاعدة المذكورة في الخطوة 3.
وأخيراً، لكل \(n\le N\) يحقق \(\gcd(n,6)=1\)، تعطي مصفوفة أصغر عامل أولي تحليله مباشرة. تقرأ الشيفرة الرتب المخزنة لقوى الأوليات الموافقة، وتحسب \(\operatorname{lcm}\) بينها، ثم تضيف الناتج إلى المجموع التراكمي.
إذا كان الحد الأعلى هو \(N\)، فإن بناء مصفوفة أصغر عامل أولي يكلف \(O(N\log\log N)\) زمناً و\(O(N)\) ذاكرة. بعد ذلك، يصبح تحليل أي \(n\) صالح في المتوسط \(O(\log N)\). أما المعالجة المسبقة الخاصة بالأوليات وقواها فتعتمد على عدد محدود من اختبارات الأس السريع، لذلك يكون الزمن الكلي قريباً من \(O(N\log N)\) عملياً، مع ذاكرة \(O(N)\) مخصصة للمصفوفة ولقيم الرتب على قوى الأوليات.