Project Euler Problem 717

Solution

Answer: 1603036763131

Let

$$A=2^{(2^p)},\qquad q=\left\lfloor \frac{A}{p}\right\rfloor .$$

We need

$$f(p)=q \bmod 2^p,\qquad g(p)=f(p)\bmod p.$$

The key observation is that since $A$ is divisible by $2^p$,

$$pq + r = A$$

with $r=A\bmod p$, and therefore

$$pq \equiv -r \pmod{2^p}.$$

Because $p$ is odd, it has an inverse modulo $2^p$, so

$$f(p)\equiv -r,p^{-1}\pmod{2^p}.$$

Now write

$$2^p = 2 + kp,$$

where

$$k = \frac{2^p-2}{p}=2\cdot \frac{2^{p-1}-1}{p}.$$

Define the Fermat quotient

$$n=\frac{2^{p-1}-1}{p}\pmod p.$$

Also let

$$r = 2^{,2^p \bmod (p-1)} \bmod p.$$

A short modular manipulation gives the remarkably simple formula

$$g(p)\equiv r n + (r \bmod 2)\pmod p.$$

This matches the given checks:

The following Python computes the required value efficiently.

PythonRun

Explanation of the important lines:

d = pow(2, p, p - 1) computes $2^p \bmod (p-1)$.
r = pow(2, d, p) computes $2^{2^p} \bmod p$.
pow(2, p - 1, p * p) computes $2^{p-1} \bmod p^2$, allowing extraction of the Fermat quotient.
The final formula for each prime is:

PythonRun

Running the program gives:

$$G(10^7)=1603036763131.$$

Answer: 1603036763131