Modular Inverses

Consider the number $15$.
There are eight positive numbers less than $15$ which are coprime to $15$: $1, 2, 4, 7, 8, 11, 13, 14$.
The modular inverses of these numbers modulo $15$ are: $1, 8, 4, 13, 2, 11, 7, 14$
because
$1 \cdot 1 \bmod 15=1$
$2 \cdot 8=16 \bmod 15=1$
$4 \cdot 4=16 \bmod 15=1$
$7 \cdot 13=91 \bmod 15=1$
$11 \cdot 11=121 \bmod 15=1$
$14 \cdot 14=196 \bmod 15=1$

Let $I(n)$ be the largest positive number $m$ smaller than $n-1$ such that the modular inverse of $m$ modulo $n$ equals $m$ itself.
So $I(15)=11$.
Also $I(100)=51$ and $I(7)=1$.

Find $\sum I(n)$ for $3 \le n \le 2 \times 10^7$.

This is not a beginner level problem, but a rather advanced number theory problem. You’re asking to find the largest self-inverse modulo $n$ for every number from $3$ to $20,000,000$, and then sum all those values. We will call the function that gets these self-inverse numbers, $I(n)$ function as stated in the problem.

Since programming or using a mathematical software seems to be the most adequate way to find $\sum I(n)$, here I elucidate the logic instead of solving it in exact numbers.

A helpful fact to know is that for any prime number $p$, the largest self-inverse modulo $p$ is $1$ (because $1$ is its own inverse, and inverses must be less than the modulus). This is because for a prime number, every single number lesser than the prime is co-prime to the prime number.

For a composite number, finding the self-inverse modulo involves finding values coprime and less than the modulus. We then find the modular inverse of each value modulo the composite number until we find a self-inverse.

This is largely a trial and error process without resorting to a programming method, in other words, it is computationally intensive and requiring iteration due to its dependency on the properties of each individual number.

To solve it for all numbers from $3$ to $2 \times 10^7$, you’ll probably want to run a program that implements an algorithm based on the Extended Euclidean Algorithm for finding modular inverses, and then find the maximum number for which the modular inverse equals the number itself for each number in the range.

The sum of all these values would be the result of $\sum I(n)$ for $3 \le n \le 2 \times 10^7$. Unfortunately, due to the large number of computations and time it would take, it’s not feasible to provide a final answer without the aid of computing software.

More Answers: