Find all pairs of positive integers $a$ and $b$ so that for every prime p coprime to $b, a\bmod p < b\bmod p$?

Question

Find all pairs of positive integers $a$ and $b$ so that for every prime p coprime to $b, a \bmod p < b \bmod p$? To clarify, $a\bmod p$ is defined to be the unique $r\in \{0,\cdots p-1\}$ so that $r\equiv a\bmod p$.

Edit: Initially, I thought it was too hard to find all solutions, so I only asked for infinitely many solutions. But now I see it's utterly trivial to find infinitely many, and because I'd like a better understanding of this problem, I'd like to ask for all solutions.

There is a nontrivial theorem that if $a$ and $b$ are positive integers such that $a\mod p \leq b\bmod p$ for all primes $p$, then $a = b$, and this problem was inspired by that theorem.

Call a pair $(a,b)$ of positive integers good if for every prime p coprime to b, $a\bmod p < b\mod p$. Clearly if there exists a prime so that $b\equiv 1\bmod p,$ then a must be divisible by that prime.

By choosing $p$ to be sufficiently large, we see that $a<b$. It suffices to check that $a\bmod p < b\bmod p$ for all primes coprime to b, it suffices to verify that $a\bmod p < b\bmod p$ for all primes less than b that are coprime to b. If a and b are both odd, then $a\mod 2 = b\bmod 2 = 1,$ contradicting the inequality. Hence at least one of $a$ and $b$ is even. $a$ cannot be congruent to $p-1\bmod p$ for any prime p coprime to $b$ as otherwise $a\bmod p\ge b\mod p.$ Suppose $a$ is even. Then a is at least $4.$ If $b=5,$ then $a\bmod k < b\bmod k$ for $k=2,3$. If b is even. We can choose $a=4,b=5$ for this to hold. Now if $b=6,$ we need $a\bmod l < 6\bmod k$ for $k=5$ and $a<6$. We can just choose $a=5.$ If $b=7,$ we need $a\bmod l < b\bmod k$ for $k=2,3,5$ and $a<b$. So $a$ is even and congruent to 0 mod 3.

Another method I was thinking of is to use the CRT to find solutions to a system of congruences $b\equiv x_i\bmod p_i$ for some distinct primes $p_i$, though I'm not sure how to make significant progress using this approach. The issue is that $b$ could be much larger than all the given $p_i$'s, and so there could be many primes less than b that would need to be checked.

Answer 1

The answer is yes, there are infinitely many such pairs. Indeed, any pair $(n,n+1)$ for $n\in\mathbb{N}$ satisfies your criterion. The proof is simple: For any prime not dividing $b=n+1$, we have $n+1=kp+c$, where $c>0$, and so $n=kp+(c-1)$, $c-1\geq 0$, meaning $n+1\bmod p>n\bmod p$.

In fact, I conjecture these are the only solutions. I'll try to work out a proof; If you are viewing this in the not-near future and there is no proof beneath this, know that I have failed.

---

(Edit 07-12-22) Success! Here is the statement and the proof.

(Edit 2 07-12-22) I've spotted a mistake in the proof. The argument can be expanded to cover $b<2a$, but I am unsure how to handle $b>2a$. I will return.

(Edit 19-12-22) I've fixed the proof, by realising that Sylvester-Schur can be applied in different ways in the two different cases.

$\bf{Definition}$. We say that a pair of positive integers $(a,b)$ are prime ordered if, for every prime not dividing $b$, we have \begin{align*} [a]_p < [b]_p\: , \end{align*} where we naturally identify the class with the principal representative in $\lbrace 0,1,\dots,p-1\rbrace$.

$\bf{Theorem}.$ The prime ordered pairs are exactly $(n,n+1)$ for $n\in\mathbb{N}$.

Proof: The fact that the pairs $(n,n+1)$ are prime ordered was proven above. Let us show that they are the only prime ordered pairs, i.e. show that any other pair $(a,b)$, $b>a+1$ is not prime ordered.

We will need the Sylvester-Schur Theorem, which I will state here.

$\bf{Theorem}$ (Sylvester-Schur). For $x>k$ positive integers, there exists an integer in the sequence $x,x+1,x+2,\dots,x+k-1$ which has a prime divisor greater than $k$.

We split the cases into $b> 2a$ and $b\leq 2a$.

$b> 2a$: Here, we will use the theorem with $x=b-a$ and $k=a$. Note that $x>k$ by assumption. We get an integer $m$ satisfying $b-a\leq m\leq b-1$ with a prime divisor $p|m$ satisfying $p>a$. Now, $p$ does not divide $b$, since if it did, $p|b-m$, and $0<b-m\leq a$, but $p>a$. By the same inequality, $[b]_p\leq a$, and $[a]_p = a$ by construction, thus we have a counterexample.

$b\leq 2a$: We use Sylvester-Schur with $x=a+1$ and $k=b-a-1$. We see $x>k$ by assumption and $k>0$ as $b>a+1$. We get an integer $m$ satisfying $a+1\leq m\leq b-1$ with a prime divisor $p|m$ satisfying $p\geq b-a$. Similar to above, we see $p$ does not divide $b$, since if it did, $p|b-m$ and $b-m\leq b-a-1$, but $p\geq b-a$.

As $a<m$ and $b>m$, and $p|m$, we see that $a=q_1p+[a]_p$ and $b=q_2p+[b]_p$ with $q_1<q_2$. However, as $p\geq b-a$, we see $q_2=q_1+1$, and this together implies $[a]_p\geq [b]_p$. Thus, we have found a counterexample.