Question about any 2 distinct primes and the difference between their multiples I've been thinking about the following situation.


*

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

*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$.  

*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$ 

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

*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. 
 A: 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 $. 
