Detailed mathematical approach

Problem Summary

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.

Mathematical Approach

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.

Step 1: Turn the Power Condition into Ring Arithmetic

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.

Step 2: Prime Moduli and the Legendre Symbol

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\).

Step 3: The Exceptional Prime \(7\) and Order Lifting

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\).

Step 4: Composite Moduli from the Chinese Remainder Theorem

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.

Step 5: Worked Example with \(n=35\)

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.

Step 6: From Local Orders to the Global Sum

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.

How the Code Works

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.

Complexity Analysis

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.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=752
2. Legendre symbol: Wikipedia - Legendre symbol
3. Euler's criterion: Wikipedia - Euler's criterion
4. Finite field: Wikipedia - Finite field
5. Multiplicative order: Wikipedia - Multiplicative order
6. Chinese remainder theorem: Wikipedia - Chinese remainder theorem