Question about any 2 distinct primes and the difference between their multiples

Question

I've been thinking about the following situation.

1. Let $p$,$q$ be two distinct primes.

2. Let $a,b \le pq$ be any two numbers such that $a \ge b$ where $p$ divides $a$ or $b$ and $q$ divides the other. For example, if $p=2,q=3$, it could be that $a=0, b=0$ or it could be that $a=3, b=2$.

3. Now, $0 \le a-b \le pq$ but there are only $\frac{(p+1)(q+1)}{2}$ possible distinct values, so there are $pq+1 - \frac{(p+1)(q+1)}{2} = \frac{(p-1)(q-1)}{2}$ values that are not possible where $a,b \le pq$

4. There are $(p-1)(q-1)$ integers less than $pq$ that are relatively prime to $pq$.

5. It is clear that any integer that is not relatively prime to $pq$ is part of the $\frac{(p+1)(q+1)}{2}$ possible distinct values since for any $x \le pq$ that is not relatively prime to $pq$, $a=x, b=0$ is one such value.

Let me give an example of what I am seeing: for $p=3,q=5$, the $4$ integers relatively prime to $15$ that match an $a-b$ are: $1 =6-5$, $2=5-3$, $4=9-5$, $7=10-3$ and the $4$ integers relatively prime that do not match any $a-b$ are: $8, 11, 13, 14$

---

Edit: After thinking more about this, I realized that my original hypothesis is wrong. For clearly, if $\frac{pq}{2} > p+q$, then $pq - p -q$ is an example since $\frac{pq}{2} < pq - p - q < pq$

For this reason, I am modifying my question. The above example is clearly the upper bound of the largest integer less than $pq$ that is satisfied by $a - b$ and which is relatively primt to $pq$.

My question is now: what is the lower bound of the first integer that cannot be satisfied by $a-b$.

My hypothesis is that this first value is $p+q$. I can show that this cannot be satisfied by $a-b$ since if it could, we would have (assuming $p>q$), $cp - dq = p+q$ where $cp > dq$ and $1 \le c \le q-1$ and $1 \le d \le p-q$. But then $(c-1)p - (d+1)q = 0$ which is impossible.

I suspect that the way to prove this is using the CRT. If I can find the argument, I will post the answer.

Answer 1

I believe that the least integer relatively prime to $pq$ that is not satisfied by $a-b$ where $a,b \le pq$ is $p+q$. Please let me know if someone sees a mistake or if my argument can be simplified.

Here's my reasoning.

(1) We can assume $p>q$ without any loss of generality.

(2) Each of the following represents a distinct nonzero congruence class of $q$ with each item having at least one more equivalent term than the item above.

• $p-q$
• $2p - q \equiv 2p - 2q \pmod q$
• $3p - q \equiv 3p - 2q \equiv 3p - 3q \pmod q$
• $\vdots$
• $(q-1)p - q \equiv (q-1)p - 2q \equiv \dots \equiv (q-1)p - (q-1)q \pmod q$

(3) $\exists c,d$ such that $p = cq + d$ where $c \ge 1$ and $0 < d < q$

(4) Each item in step #2 consists of at least $c$ additional terms since:

• $p-q \equiv p - 2q \equiv \dots \equiv p - cq \pmod q$
• $2p-2q \equiv 2p - 2(2q) \equiv \dots \equiv 2p - c(2q) \pmod q$
• $\vdots$

(5) So, it follows that each integer $x \le cq$ can be represented as a $x=a-b$ where $p$ divides $a$ or $b$ and $q$ divides the other and $a,b \le pq$

(6) It further follows that each integer $cq < x \le (c+1)q$ can be represented as $x=a-b$ since each item other than $p-q$ has at least one additional term. If $x \equiv p-q \pmod q$, then since $p - q = cq + d - q = (c-1)q + d$, then $x = cq + d = p$.

(7) To complete the argument, we need to show that this follows up to $x < p+q = (c+1)q + d$. From step #6, for all $i < d$, we know that $(c+1)q + i \not\equiv p-q \pmod q$. Since each item other than $2p-q$ has at least one additional term, we just not need to handle $(c+1)q + i \equiv 2p - q \pmod q$. The argument is roughly the same as step #6. If $(c+1)q + i \equiv 2p - q \pmod q$, then since $2p - q = cq + i$, then $cq + i + q = 2p - q + q = 2p \le pq$.

---

One other thing I noticed is that if $x < pq$ has the form $cp + dq$ where $c,d \ge 1$, it follows that it will not equal any $a - b$.

Here's the argument

(1) Assume that $cp + dq < pq$ and $cp + dq = ep - fq$ so that $p(e-c) = q(d+f)$.

(2) But this is impossible since $0 < e-c < q$

---

This raises the question of whether every $x < pq$ where there is no $a,b$ such that $x = a - b$ has the form $cp+dq$.

I believe the answer is that for all $0 \le x \le pq$, either there exists $a,b$ such that $x = a -b$ or $x$ has the form of $x=ep + fq$ and no such $a,b \le pq$ exists.

Here's the argument:

(1) Let $x$ be any integer such that $0 \le x \le pq$

(2) Let $e$ be the smallest integer such that there exists an integer $f$ such that $x + ep = fq$

(3) Assume $2pq > x + ep > pq$ (Otherwise, $x = fq - ep$)

(4) Then $pq > x - (q-e)*p = x -pq + ep > 0$

(5) So, it follows that $x = (q-e)*p + gq$ for some integer $g > 0 $.