Minimal Pairing Modulo $p$

Given an odd prime $p$, put the numbers $1,…,p-1$ into $\frac{p-1}{2}$ pairs such that each number appears exactly once. Each pair $(a,b)$ has a cost of $ab \bmod p$. For example, if $p=5$ the pair $(3,4)$ has a cost of $12 \bmod 5 = 2$.
The total cost of a pairing is the sum of the costs of its pairs. We say that such pairing is optimal if its total cost is minimal for that $p$.
For example, if $p = 5$, then there is a unique optimal pairing: $(1, 2), (3, 4)$, with total cost of $2 + 2 = 4$.
The cost product of a pairing is the product of the costs of its pairs. For example, the cost product of the optimal pairing for $p = 5$ is $2 \cdot 2 = 4$.
It turns out that all optimal pairings for $p = 2\,000\,000\,011$ have the same cost product.
Find the value of this product.

Consider the following pairing for an odd prime $p$, namely, $(1, p-1)$, $(2, p-2)$, $(3, p-3)$, $\ldots$, $\left(\frac{p-1}{2}, \frac{p+1}{2}\right)$. All of these pairs have a cost of $1$, because if you take an element $a$ from the first half of the array and its corresponding pair $p – a$ from the second half, this property holds: $a+b=p$, and $ab \equiv a(p-a) \equiv -a^2 \mod p$. Using Fermat’s Little Theorem we know that $a^{p-1} \equiv 1 \mod p$. So $a^2$ (i.e., $a \cdot a$) will be multiplied by $a^{p-3}$ that will be $1$, it implies that $a^2 \equiv -1 \mod p$ (since $p$ is odd).

According to this, all of the pairs we’ve established will accumulate a cost of $1$. Thus, the total cost for these pairings is $\frac{p-1}{2}$ and the cost product is $1^{p-1} = 1$. This is clearly the minimal possible total cost (and, consequently, the minimal cost product), since the cost is always positive, so no set of pairings can have total cost (and cost product) lower than that.

As for the claim that “all optimal pairings for $p = 2\,000\,000\,011$ have the same cost product”, it refers to the fact that the cost function in this context appears to be suitably “smooth” that all the minima are the same. So we don’t have to worry about other, nontrivial, pairings yielding a smaller cost. We can just use the trivial pairing we found to claim that the cost product of the optimal pairing for $p = 2\,000\,000\,011$ is $1$.

Note: In mathematics, particularly in algebraic number theory, Fermat’s Little Theorem states that if $p$ is a prime number, then for any integer $a$, the number $a^p − a$ is an integer multiple of $p$. In other words, $a^p$ divided by $p$ leaves the same remainder as $a$ divided by $p$.

More Answers: