P942
projecteuler.net

Mersenne's Square Root

ℹ️Published on Saturday, 26th April 2025, 11:00 pm; Solved by 107;
Difficulty level: 34

Given a natural number $q$, let $p = 2^q - 1$ be the $q$-th Mersenne number.

Let $R(q)$ be the minimal square root of $q$ modulo $p$, if one exists. In other words, $R(q)$ is the smallest positive integer $x$ such that $x^2 - q$ is divisible by $p$.

For example, $R(5)=6$ and $R(17)=47569$.

Find $R(74\,207\,281)$. Give your answer modulo $10^9 + 7$.

Note: $2^{74207281}-1$ is prime.



Soluzione

Last modified: February 25, 2026. Website built with Franklin.jl and the lovely Julia programming language.