Reciprocal Pairs

Let’s call a pair of positive integers $p$, $q$ ($p \lt q$) reciprocal, if there is a positive integer $r\lt p$ such that $r$ equals both the inverse of $p$ modulo $q$ and the inverse of $q$ modulo $p$.

For example, $(3,5)$ is one reciprocal pair for $r=2$.
Let $F(N)$ be the total sum of $p+q$ for all reciprocal pairs $(p,q)$ where $p \le N$.

$F(5)=59$ due to these four reciprocal pairs $(3,5)$, $(4,11)$, $(5,7)$ and $(5,19)$.
You are also given $F(10^2) = 697317$.

Find $F(2\cdot 10^6)$.

To solve this math problem, we need a solid understanding of modular arithmetic and inverses. It’s helpful to breakdown this problem into smaller parts before we attack the the problem as a whole. So, here’s how to approach it:

Given $p$ less than $q$, the condition given in the question means that the inverse of $p$ (mod $q$) is equal to that of $q$ (mod $p$). Let’s call this common inverse value as $r$. So:

$r * p ≡ 1$ (mod $q$)
$r * q ≡ 1$ (mod $p$)

Let’s take this one step forward:

Suppose we have the equation $r * p – 1 = h * q$ for some integer $h$. Following the same logic, we also have the equation $r * q – 1 = k * p$ for some integer $k$.

Multiplying these two equations, we get:

$r*r*p*q – r*p – r*q + 1 = h*k*p*q$

This can be rearranged to:

$r*r- (h*k) = (r/h)*p + (r/k)*q + (1/hk)*pq$

Given that $r, p, q$ must be integers, so must $(r/h)*p + (r/k)*q + (1/hk)*pq$.

Let’s look back at the problem. It’s important to note that the value of $r$ is less than $p$ which is less than $q$ (as stated in the problem). Therefore, the right side of the equation can be an integer only when the fractions ($r/h$, $r/k$, and $1/hk$) are integers themselves. This leads us to conclude that $h$, $k$, and $r$ must be the same value for the right-side of the equation to be an integer. So, this means $h = k = r$.

With the conclusion that $h$ = $k$ = $r$, we can rewrite our original equations as:

$r*p – 1 = r*q$
$r*q – 1 = r*p$

Multiplying these two equations again, we get:

$r*r*p*q – r*p – r*q + 1 = r*r*p*q$

This implies:

$r*p + r*q = 1$

Given that $r, p, q$ are positive integers, the minimum value of $p$ + $q$ should be 2r and the maximum value can be 4r (since for maximum value, during the reaching to the maximum value of $p+q$, $q>= 2r$, but $r
Here, it might be helpful to note that $r > 1$ because $p + q > 2r$.

Finally, we need to add the values of all $p+q$ pairs that satisfy these conditions for $r$ ranging from `2` to `N/2` to calculate $F(N)$. Hence, given $F(10^2) = 697317$ and we’re asked to find $F(2\cdot 10^6)$, we would need to write a code to calculate this as it would be unrealistic to manually calculate this.

The code for this would use nested loops to first calculate the pairs for each $r$ value from 2 to `N/2` then, within each loop, calculate the pairs where $p+q$ ranges from `2r` to `4r` and check if these numbers satisfy the “reciprocal” conditions. If the conditions are met, the pair of $p$ and $q$ is summed and added to a growing total.

This is a complex problem involving modular arithmetic and the use of a specific set of mathematical conditions. If there are parts of the problem you’re still unsure about, it might be helpful to work through more examples or speak with a math tutor who can explain these concepts in more detail.

Given its complexity, this problem seems to be from a math competition problem like those from the Project Euler, so understanding and solving this would require some more practice with advanced math topics including modular arithmetic and number theory.

More Answers: