1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ (1) There seems to be some $l$ popping out of nowhere in your attempt. Are they typos? (2) For the case $b = 7$, why do you say "$a$ is odd"? $\endgroup$
    – VTand
    Commented Dec 6, 2022 at 16:06
  • 2
    $\begingroup$ I am guessing $l$ was meant to be $k$. Also, why does $a$ have to be odd for $b=7$, should it not exactly be even, and then $a=6$ works? In fact, it seems that $(n,n+1)$ for $n\in\mathbb{N}$ is always a solution, and in fact the only solutions. I just tested this for all $b<5000$ with a very naive program, but I have no proof as of yet. $\endgroup$ Commented Dec 6, 2022 at 16:25
  • $\begingroup$ Does this answer your question? Do there exist positive integers $a,b$ with $a\bmod p &lt; b\bmod p$ for all primes $p$ $\endgroup$
    – Mike
    Commented Dec 6, 2022 at 16:32
  • $\begingroup$ @Mike No, there is no coprime restriction in your linked question. $\endgroup$
    – VTand
    Commented Dec 6, 2022 at 16:34
  • $\begingroup$ I have significantly increased the difficulty of this problem. 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. $\endgroup$
    – user33096
    Commented Dec 6, 2022 at 17:31

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I have significantly increased the difficulty of this problem. 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. $\endgroup$
    – user33096
    Commented Dec 6, 2022 at 17:31
  • 3
    $\begingroup$ @user33096 it is the responsibility of the person asking to be clear in their question. You [general you] cannot be making a moving target on here as in asking something and then edit your question to asking something different, as people put effort into answering. Hopefully you get an answer to your revised question, but this is a fair answer to the question that was up at the time so it should stay. $\endgroup$
    – Mike
    Commented Dec 6, 2022 at 18:03
  • 1
    $\begingroup$ I tend to agree with Mike. Posting a new question asking for all solutions, and linking to this one, would probably have been the wiser move. Nevertheless, I'll see if I can't cook up a proof for you today. $\endgroup$ Commented Dec 7, 2022 at 9:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .