A Polynomial Modulo the Square of a Prime

Let $f(n) = n^2 – 3n – 1$.
Let $p$ be a prime.
Let $R(p)$ be the smallest positive integer $n$ such that $f(n) \bmod p^2 = 0$ if such an integer $n$ exists, otherwise $R(p) = 0$.

Let $SR(L)$ be $\sum R(p)$ for all primes not exceeding $L$.

Find $SR(10^7)$.

This problem is quite complex and would require substantial mathematics and programming knowledge to solve. However, here’s a general breakdown of how to approach it:

1. **Understanding the problem**
The function $f(n) = n^2 – 3n – 1$ is a quadratic function and you are looking for values of $n$ such that $f(n)$ is a multiple of $p^2$, where $p$ is a prime number. The function $R(p)$ gives the smallest such $n$ (if it exists) and $0$ otherwise. The function $SR(L)$ is the sum of all $R(p)$ for all primes less than or equal to $L$.

2. **A key observation**
Since $p^2|f(n)$ if and only if $p|f(n)$, we can focus on finding $n$ such that $f(n)$ is a multiple of $p$ instead of $p^2$.

3. **Solving for each prime**
We can solve the quadratic congruence equation $n^2 – 3n – 1 \equiv 0 \mod p$ for each prime $p$ up to $10^7$ using quadratic reciprocity and the Chinese remainder theorem (or any method to solve quadratic congruences). If a solution exists, we take the smallest positive one as $R(p)$ and add it to our running total.

4. **Efficiency**
To find all primes up to $10^7$ and compute $R(p)$ for each, this can be done efficiently using a Sieve of Eratosthenes and then a binary search for each prime.

However, the complexities involved in forming this particular computation are quite extensive, and involves some very specialized mathematical theories such as number theory, quadratic residues, and congruences. It would also likely require the use of programming to accomplish in a reasonable amount of time.

Realistically, this problem is beyond the scope of standard high school education, and even most undergraduate courses. It would be more typical of advanced university or Math Olympiad level questions. Speaking of exact solutions without involving specific algorithms and software would be infeasible.

More Answers: