An integer and its inverse modulo prime, both less than half of the prime

Question

Question:

A prime number $p$ is mundane if there exist positive integers $a$ and $b$ less than $p/2$ such that $\frac{ab-1}{p}$ is a positive integer. Find, with proof, all prime numbers that are not mundane.
(HMIC 2023/2)

I have found by manually checking the only non-mundane primes are $2, 3, 5, 7, 13$. I did not check for large values because: a) I don't think the question expected me to do that and b) the below attempt "shows" that it is very difficult for large prime to be non-mundane.

Attempt:
The above-listed primes are clearly non-mundane. We are trying to show all others are mundane. We basically need to find two numbers $a,b$ whose product is $kp+1$ for $k \in \Bbb N$ such that $1<a,b<p/2$. However, $1<ab<p^2/4$. So, as we increase $p$, the number of possible values of $k$ in that range increases (quadratic grows faster than linear), so it is highly probable that we will succeed in finding such $a,b$.
Working on this heuristic, we are looking for a pair $(k,a)$ such that $p/2>a>k/2$ and $a \mid kp+1$.

Note that $k=1$ works more often than not. That is if $p+1$ has a divisor other than $2$ or $(p+1)/2$, then we're done. If not, then $(p+1)/2$ is a prime. I could not find much about prime pairs $(p, 2p-1)$ except that it's an open problem whether there are infinitely many of them.

Suppose $(p+1)/2$ is prime, then $p \equiv 1 \pmod 3$, so that $(2p+1)/3$ is an integer. If it is not a prime, then we're done (as $3\sqrt{2p+1}<p/2$) for sufficiently large $p$).

However, I don't think analyzing cases is the way forward. One approach I haven't considered is rephrasing the problem to finding $a,b \in \{2,3, \ldots, \frac{p-1}2\}$ such that $a \equiv b^{-1} \pmod p$. However, at the top of my head, I can't think of a property of inverses modulo a prime, so maybe this is a dead end.

Answer 1

There is a very simple approach here; just make sure you will assess the special cases, which are very small numbers.

Case $1$: The prime is of the form $p=9k+2$, then:

$$\frac{\frac{4p+1}{9} \times 9-1}{p}.$$

Case $2$: The prime is of the form $p=9k+4$, then: $$\frac{\frac{2p+1}{9} \times 9-1}{p}.$$

Case $3$: The prime is of the form $p=9k+8$, then:

$$\frac{\frac{p+1}{9} \times 9-1}{p}.$$

Case $4$: The prime is of the form $p=9k+5$, then:

$$\frac{\frac{7p+1}{18} \times 18-1}{p}.$$

Case $5$: The prime is of the form $p=9k+7$, then:

$$\frac{\frac{5p+1}{18} \times 18-1}{p}.$$

Case $6$: The prime is of the form $p=9k+1$, then:

$$\frac{2k \times (\frac{9k}{2}-4)-1}{9k+1}.$$

---

PS: How was the answer developed?

Since $ab$ must be of the form $np+1$ for some $n \in \mathbb N$ it's worth investigating the cases where $n=1,2,3,4$. Here is the point where the idea of module $9$ appears simply because $2\times 4 <9$. Then, finding the constants $9$ and $18$ is not a big deal. The tricky part is Case $6$, which can be investigated in the most natural way as follows:

$$ab-1=n(9k+1) \implies a=\frac{9nk+n+1}{b} \implies \\ b<\frac{9k+1}{2}, \\ a=\frac{9nk+n+1}{b} < \frac{9k+1}{2}.$$

Hence, we must have:

$$\frac{9k+1}{2} >b> 2n, \\ b \mid 9nk+n+1.$$

At this point, assuming $b=2k$ gives us the fact that we must have:

$$b \mid kn+n+1,$$

such that $n \leq k-1.$

Now, putting $n=k-1$, just as a guess, leads to:

$$2k \mid k^2,$$

which is trivially true because $k$ was initially even because $9k+1$ is supposed to be a prime.

Answer 2

There are no larger primes which are non-mundane than what you've indicated. To prove this, there are several cases to handle, with the following only considering odd primes. First, if $p \equiv 3 \pmod{4} \;\to\; p + 1 = 4k$ for some integer $k$, then $4$ and $k$ will make $p$ mundane unless $4 \ge \frac{p+1}{2} \;\to\; p \le 7$, i.e., the primes $3$ and $7$ you've already shown.

Next, for primes where $p \equiv 5 \pmod{8}$ with $p \ge 29$ (since $p = 5$ and $p = 13$ are non-mundame, as you've noted), consider any even integer from $4$ to $\frac{p-5}{4}$ inclusive, calling it $a_1$. Note that if its multiplicative inverse, call it $b_1$, is between $\frac{p+1}{2}$ and $\frac{3p-3}{4}$ inclusive, then $2b_1$ is congruent to a value between $1$ and $\frac{p-1}{2}$ (inclusive), so we can choose $a = \frac{a_1}{2}$ and $b = 2b_1$. Alternatively, if $b_1$ is an even value between $\frac{3p+1}{4}$ and $p-1$, inclusive, then since $2a_1 \lt \frac{p}{2}$, we can choose $a = 2a_1$ and $b = \frac{b_1}{2}$. Thus, the only possible way this prime may not be mundane is if all of the possible $b_1$ are odd integers between $\frac{3p+5}{4}$ and $p-2$, inclusive. However, the multiplicative inverse of $p-2$ is $\frac{p-1}{2}$ and that of $p-4$ is $\frac{p-1}{4}$, both of which are greater than $\frac{p-5}{4}$, so they need to be excluded.

Thus, there are

$$\frac{\frac{p-5}{4}-4}{2} + 1 = \frac{p-13}{8}$$

even $a_1$ integers, while there are only

$$\frac{p-6 - \frac{3p+5}{4}}{2} + 1 = \frac{p-21}{8}$$

odd $b_1$ integers available. Since this is one less than that of the $a_1$, and each multiplicative inverse is unique, this is not possible.

Similarly, for primes where $p \equiv 1 \pmod{8}$ with $p \ge 41$ (since $p = 17$ has $a = 3$ and $b = 6$ which work), consider any even integer from $4$ to $\frac{p-1}{4}$, inclusive, calling it $a_2$. As before, if any multiplicative inverse, call it $b_2$, is between $\frac{p+1}{2}$ and $\frac{3p-3}{4}$ inclusive, then $2b_2$ is congruent to a value between $1$ and $\frac{p-1}{2}$, so we can choose $a = \frac{a_2}{2}$ and $b = 2b_2$. Alternatively, if $b_2$ is an even value between $\frac{3p+5}{4}$ and $p-1$, inclusive, then since $2a_2 \lt \frac{p}{2}$, we can choose $a = 2a_2$ and $b = \frac{b_2}{2}$. Thus, the only possible way this prime may not be mundane is if all of the possible $b_2$ are odd integers between $\frac{3p+1}{4}$ and $p - 2$, inclusive. However, as before, we can exclude $p-2$. Thus, so far, we have

$$\frac{\frac{p-1}{4}-4}{2} + 1 = \frac{p-9}{8}$$

even $a_2$ integers, with up to

$$\frac{p-4 - \frac{3p+1}{4}}{2} + 1 = \frac{p-9}{8}$$

i.e., the same number of odd $b_2$ available. Since $p\equiv 1\pmod{8}$, it's of the form

$$p = 2^{c}d + 1$$

where $c$ and $d$ are positive integers, with $c \ge 3$ and $d$ being odd. If $d \ge 5$, then note that

$$\begin{equation}\begin{aligned} p - 2^{c+2} \gt 1 \\ 4p - 2^{c+2} \gt 3p + 1 \\ p - 2^{c} \gt \frac{3p + 1}{4} \end{aligned}\end{equation}$$

Thus, $p - 2^{c}$ is one of the odd integers under consideration. However, its multiplicative inverse of $\frac{p-1}{2^{c}}$ is odd, so it's not included within the set of $b_2$ values, which means this set now has a size one less than that of the set of $a_2$ values, which is not possible. This means that these primes are all mundane.

Next, consider if $d = 3$. We then have

$$2p + 1 = 2(3(2^c) + 1) + 1 = 3(2^{c+1} + 1)$$

If $2^{c+1} + 1$ is non-prime, since $c \ge 3$, then $2^{c+1} + 1 \gt 3^2$. Thus, let $a$ be $3$ times the smallest prime factor of $2^{c+1} + 1$, with $b = \frac{2p+1}{a}$, with both $a$ and $b$ being less than $\frac{p}{2}$. Otherwise, $2^{c+1} + 1$ is a Fermat prime, so $c + 1$ is a power of $2$, i.e., there's a positive integers $k \ge 2$ and $m \ge 1$ where

$$c + 1 = 2^k \;\to\; c = 2^k - 1 \;\to\; c = 4m + 3$$

However, we then have

$$\begin{equation}\begin{aligned} p & \equiv 3(2^{4})^{m}(2^3) + 1 \pmod{5} \\ & \equiv 3(1^{m})(3) + 1 \pmod{5} \\ & \equiv 0 \pmod{5} \end{aligned}\end{equation}$$

but $p \gt 5$, so it can't be a prime.

The final case to handle is $d = 1$. This then means that $p$ is a Fermat prime, i.e., $c = 2^{k}$ for some integer $k \ge 2$. We then have

$$\begin{equation}\begin{aligned} 2p + 1 & \equiv 2(2^{2^k} + 1) + 1 \pmod{5} \\ & \equiv 2(1 + 1) + 1 \pmod{5} \\ & \equiv 0 \pmod{5} \end{aligned}\end{equation}$$

Thus, we can choose $a = 5$ and $b = \frac{2p+1}{5}$, with both being less than $\frac{p}{2}$, to show these primes are also mundane.

Answer 3

I found another solution:

We claim that $2,3,5,7,13$ are the only non-mundane primes. They can be checked manually. We show all larger primes are mundane. Since we can verify small cases manually, let $p$ be a prime sufficiently large than $13$ and assume it is non-mundane.

Let $S = \{2,3,4\ldots p-2\}$. $|S| = p-3$ which is even. Moreover, $S$ can be partitioned into distinct $(p-3)/2$ unordered pairs $(i,j)$ such that $ij \equiv 1 \pmod p$. If there is such a pair $(i,j)$ such that both $i,j$ are either greater than $p/2$ or less than $p/2$, then it is easy to see that $p$ is mundane since the number of elements in $S$ greater than $p/2$ is equal to the number of elements less than $p/2$.

Hence for any such pair $(i.j)$ if $i<p/2$ then $j>p/2$ and vice-versa. Call this condition (#).

Now, consider $3^{-1}$. The possible values for it in $S$ are $\frac{p+1}{3}$ or $\frac{2p+1}{3}$. But due to (#) we discard the first, hence $p \equiv 1 \pmod 3$.
Similarly, $4^{-1}$ has possible values $\frac{p+1}{4}$, $3p+1 \over 4$, and due to (#), the first is discarded again, giving $p \equiv 1 \pmod 4$. Hence $p \equiv 1 \pmod {12}$.

Then, consider $\frac{p-13}{12} < \frac p2$. Its possible inverses are $\frac{kp-12}{13}$ for $k\in \{7,8,9,10,11,12\}$ (for that value of $k$ for which it is an integer). Smaller values of $k$ disobey (#).
Next, $\frac{p-13}{6}<\frac p2$, and its possible inverses are $\frac{kp-12}{26}$ or $\frac{(k+13)p-12}{26}$. Due to (#), the first is discarded, and we get $k$ is odd. Thus $k \in \{7,9,11\}$.
After that, $\frac{p-13}{3}<\frac p2$, whose possible inverses are $\frac{kp-12}{52}, \frac{(k+13)p-12}{52}, \frac{(k+26)p-12}{52}, \frac{(k+39)p-12}{52}$. Since $k$ is odd, we discard the first and third, and discard the second due to (#).

So, we get $k \equiv 1 \pmod 4$, i.e. $k = 9$.

But then $\frac{p-13}4 < \frac p2$, and its inverse is $\frac{9p-12}{39} = \frac{3p-4}{13} < \frac p2$, contradiction. $\blacksquare$