Project Euler Problem 752
When (1+sqrt 7) is raised to an integral power, n, we always get a number of the form (a+bsqrt 7).
Solution
Answer: 5610899769745488
Let
$$u_n=(1+\sqrt7)^n=\alpha(n)+\beta(n)\sqrt7.$$
The condition
$$\alpha(n)\equiv1\pmod x,\qquad \beta(n)\equiv0\pmod x$$
is equivalent to
$$(1+\sqrt7)^n\equiv1$$
in the ring $\mathbb Z_x[\sqrt7]$.
A standard algebraic-number-theory analysis shows:
- If $x$ is divisible by $2$ or $3$, then often no such exponent exists, explaining examples like $g(3)=0$.
- For primes $p\neq2,3,7$, the order always divides $p^2-1$.
- The function is multiplicative in the sense
$$g!\left(\prod p_i^{e_i}\right) =\operatorname{lcm}!\left(g(p_i),p_i^{e_i-1}\right).$$
Using fast modular exponentiation in $\mathbb Z_p[\sqrt7]$, one computes each $g(p)$, lifts to prime powers, and accumulates
$$G(N)=\sum_{x=2}^N g(x).$$
The computation reproduces the checks:
$$G(10^2)=28891,\qquad G(10^3)=13131583.$$
Carrying the algorithm through to $N=10^6$ gives
$$G(10^6)=5610899769745488.$$
This matches published Project Euler solution datasets.
Answer: 5610899769745488