# Determine the maximum value of $b-a$, where $a$ and $b$ are positive integers with the following property

If $p$ and $q$ are distinct prime numbers, then there are integers $x_0$ and $y_0$ such that $1 = px_0+qy_0$. Determine the maximum value of $b-a$, where $a$ and $b$ are positive integers with the following property: If $a \leq t \leq b$, and $t$ is an integer, then there are integers $x$ and $y$ with $0 \leq x \leq q-1$ and $0 \leq y \leq p-1$ such that $t = px + qy$.

The first statement is obvious. It follows from Bezout's identity. Also if we want to determine the maximum value of $b-a$ it needs to be for all distinct primes $p,q$, so how do we ensure that?

• By definition of the question the answer is technically $a = -\infty$, $b = \infty$, $b - a = \infty$ to create the maximum value. The question is poorly worded. – Dane Bouchie Jun 20 '16 at 15:45
• @DaneBouchie So you are saying any integer $t$ can be represented in that form? – Puzzled417 Jun 20 '16 at 15:46
• I'm just pointing out the question (I'm guessing you were given) is poorly worded. It asks for the maximum range. I think the meant the minimum value of $b-a$, for all $t$ such that ... etc. – Dane Bouchie Jun 20 '16 at 15:49
• @DaneBouchie It says determine the maximum possible value of $b-a$ with the following property... so the answer isn't $\infty$. – Puzzled417 Jun 20 '16 at 15:50
• Well as long as $t$ is some positive integer, we simply pick the largest values such that $a <= t <= b$. Therefore we choose $a = 0$ and $b = \infty$ to get $b-a = \infty$. $\infty$ is the maximum possible value of $b-a$. (Corrected that $a$ needs to be a positive integer) – Dane Bouchie Jun 20 '16 at 15:53

If $t<p$ and $t<q$, then you can't have $x\geq0$ and $y\geq0$ with $t=px+qy$.
So $a\geq\min(p,q)$.
And the highest possible value for $t$ is $p(q-1)+q(p-1)$,
so $b\leq2pq-p-q$.
If $p=3$ and $q=5$, the possible numbers are: $$0,3,6,9,12;5,8,11,14,17;10,13,16,19,22\\ =0,3,5,6,8,9,10,11,12,13,14,16,17,19,22$$ so the largest value of $b-a$ comes for $a=8$ and $b=14$.
• Try $2\&3$, $2\&5$, $2\&7$, $3\&5$, $3\&7$,$5\&7$ until you find a pattern for $a$ or $b$ or $b-a$ – Empy2 Jun 20 '16 at 18:14
• I get $0,2,3,4,5,7$ for $2,3$ and $0,2,4,5,6,7,8,9,11,13$ for $2,5$. – Puzzled417 Jun 20 '16 at 18:38