Project Euler Problem 942

Solution

Answer: 557539756

Let

$$p = 2^q-1$$

with $q=74,207,281$, and $p$ prime.

We seek the minimal positive solution of

$$x^2 \equiv q \pmod p.$$

For Mersenne primes, $2$ has order $q$ modulo $p$, so the $q$-th roots of unity in $\mathbb F_p$ are

$$1,2,2^2,\dots,2^{q-1}.$$

A classical quadratic Gauss sum identity gives, for $q\equiv1\pmod4$,

$$G=\sum_{a=0}^{q-1}\left(\frac aq\right)2^a$$

satisfying

$$G^2=q.$$

Since

$$\left(\frac 0q\right)=0, \qquad \left(\frac aq\right)= \begin{cases} 1 & a \text{ quadratic residue mod } q,\ -1 & \text{otherwise}, \end{cases}$$

we can rewrite:

$$G = 1+2\sum_{r\in QR(q)}2^r \pmod p,$$

where $QR(q)$ is the set of nonzero quadratic residues modulo $q$.

For $q\equiv1\pmod8$ (true here), this Gauss sum is the larger square root, so

$$R(q)=p-G.$$

Thus

$$R(q) = 2^{q+1}-3 - 2\sum_{r\in QR(q)}2^r.$$

We only need this modulo $M=10^9+7$, so all computations are performed modulo $M$.

A direct $O(q)$ computation is feasible.

Python code:

q = 74207281
MOD = 10**9 + 7

# mark quadratic residues mod q
qr = bytearray(q)
half = (q - 1) // 2

for i in range(1, half + 1):
    qr[(i * i) % q] = 1

s = 0
p2 = 2

for r in range(1, q):
    if qr[r]:
        s = (s + p2) % MOD
    p2 = (p2 * 2) % MOD

# p2 == 2^q mod MOD
ans = (2 * p2 - 3 - 2 * s) % MOD

print(ans)

This evaluates to:

Answer: 557539756