Conjecture: all primes $p>5$ have smaller primes $q_1,q_2$ s.t. $p \pmod {q_1} = p \pmod {q_2}$

Question

I assert

$\forall p \in \mathbb P\text{ where }p>5 : \exists q_1,q_2\in\mathbb P\text{ such that }q_1<q_2<p$ and $$p\!\!\!\!\pmod {q_1} = p\!\!\!\!\pmod {q_2}$$

E.g. $7 \equiv 1 \pmod {2}\text{ and } 7\equiv 1 \pmod {3}$ so, $7\pmod{2}=7\pmod{3}$

I am almost certain this is true. In fact, I think there's a minimum number of such duplicates which increases without bound, e.g. you'll find at least two distinct duplicate pairs $(q_1,q_2)$ for all primes $\geq 31$.

I am wondering whether anyone sees an easy proof for this, or failing that, a good heuristic argument for why it's true. (Also, is that legal use of mod notation?)

Addendum (Shubhrajit Bhattacharya)

For any prime $p$, define $\Phi(p)$ to be the number of unordered pairs $\{q_1,q_2\}$ of primes smaller than $p$ such that $$p\!\!\!\!\pmod{q_1}=p\!\!\!\!\pmod{q_2}$$ It has been clear that $\Phi(p)\geq1$ for all primes $p\geq 5$. Now, a reasonable question is that how $\Phi(p)$ grows as $p\rightarrow\infty$?

A not so useful formula for $\Phi(p)$. Let $\omega(n)$ denotes the number of distinct prime factors of $n$. Let $$\delta(a,p)=\begin{cases}0\quad\text{if $(p-a)$ is a prime power}\\\binom{\omega(p-a)}{2}\quad\text{otherwise}\end{cases}$$

For any prime $q<p$, we must have that $q\leq p-2$ as $p\geq5$. Then $p\pmod{q}\leq q-1\leq p-3$. Then the remainder can be at most $p-3$ when we divide $p$ by a prime $q<p$. Now, if $p-a$ is not a power of prime, any pair of two distinct prime factors of $p-a$ counts in $\Phi(p)$. Now, $\binom{\omega(p-a)}{2}$ such unordered pairs are there. When $p-a$ is a prime power, we certainly can't get two distinct primes modulo which $p$ is $a$. So, we get that $$\boxed{\Phi(p)=\sum_{m=1}^{p-3}\delta(m,p)}$$ for all $p\geq5$

Answer 1

Yes this is true. This is equivalent to saying that one of $p-1, p-2$ is divisible by at least two distinct primes.

Case 1: $p-1$ is not a power of two. Then $p-1$ is even and has an odd prime factor, and $p \equiv 1 \pmod 2$ and $p \equiv 1 \pmod {\text{"odd prime factor"}}$.

Case 2: $p-1$ is a power of two. Then $p$ is a Fermat prime, i.e. $p = 2^{2^n} +1$.

Then $p-2 = 2^{2^n} - 1 = (2^{2^{n-1}}-1)(2^{2^{n-1}}+1)$. Just pick an odd prime factor from each factor and we have $p \equiv 2 \pmod {\text{"them"}}$. Here observe that $\gcd\{2^{2^{n-1}}-1,2^{2^{n-1}}+1\} = 1$ and $p> 5$.

Answer 2

A very rough idea:
If $p$ is prime then $p-1$ has unique factorization in the form $p-1=2^k\cdot p_1^{n_1}\cdot p_2^{n_2}\cdots p_m^{c_m}$. If such $p_i$ exists then we have $p\equiv 1\mod 2$ and $p\equiv 1\mod p_i$. Therefore we consider $p-1=2^k$.
Here $p=2^k+1$. Since $p$ is prime then $p$ must be a Fermat Number, i.e. $p=2^{2^a}+1$ for some natural number $a$. So $p=2^{2^a}+1=(2^{2^a}-1)+2=(2^{2^{a-1}}-1)(2^{2^{a-1}}+1)+2$. Note that $2^{2^{a-1}}-1$ and $2^{2^{a-1}}+1$ would be odd, then they must contain distinct prime factors, which cannot be $2$. For such prime $p_1$ in $2^{2^{a-1}}-1$ and $p_2$ in $2^{2^{a-1}}+1$, we have the same remainder.

Answer 3

If $p-1$ is not a power of two, then there is a prime $q\neq 2$ dividing $p-1$. Also, $p-1$ is even. Then we have $p \equiv 1 \pmod 2$ and $p \equiv 1 \pmod q$, as desired.

If $p-1$ is a power of two, then consider the number $p-2$. If $p-2$ is divisible by two distinct primes $r$ and $s$ (note that $r,s>2$ as $p-2$ is odd), then $p \equiv 2 \pmod r$ and $p\equiv 2\pmod s$, as desired.

We are left with the case when $p-1$ is a power of two and $p-2$ is a power of a prime. We shall prove that this case is impossible. Write $p-1=2^k$ and $p-2=m^n$ where $m$ is prime. Note that $2^k-m^n=1$, which cannot happen if $n\ge 2$ due to Mihailescu theorem. Therefore $p-2$ is prime. But then, since $p-2$ and $p$ are primes, $p-1$ is divisible by three, which is a contradiction as $p-1$ is a power of two.