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.
My teacher gave me this, and he said it was from his notes. Though, from the terminology, I wouldn't be surprised if this were from a contest.
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.
Best Answer
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.