Search Problems   RSS Feed
projecteuler.net

Mersenne's Square Root

 Published on Saturday, 26th April 2025, 11:00 pm and solved by 230
Difficulty: Level 39 [98%]

Problem 942

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.



Copied to Clipboard