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?

  • $\begingroup$ 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. $\endgroup$ – Dane Bouchie Jun 20 '16 at 15:45
  • $\begingroup$ @DaneBouchie So you are saying any integer $t$ can be represented in that form? $\endgroup$ – Puzzled417 Jun 20 '16 at 15:46
  • $\begingroup$ 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. $\endgroup$ – Dane Bouchie Jun 20 '16 at 15:49
  • $\begingroup$ @DaneBouchie It says determine the maximum possible value of $b-a$ with the following property... so the answer isn't $\infty$. $\endgroup$ – Puzzled417 Jun 20 '16 at 15:50
  • $\begingroup$ 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) $\endgroup$ – 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$.
There are probably tighter bounds than that though.
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$.

  • $\begingroup$ 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$ $\endgroup$ – Empy2 Jun 20 '16 at 18:14
  • $\begingroup$ I am not seeing a pattern. Can you tell me how to solve this? It looks symmetric. $\endgroup$ – Puzzled417 Jun 20 '16 at 18:22
  • $\begingroup$ 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$. $\endgroup$ – Puzzled417 Jun 20 '16 at 18:38
  • $\begingroup$ Draw up a table with five columns p,q,a,b,b-a. The first row, from your results, is 2,3,2,5,3. When you have a few rows, try to find a connection between p,q, and the other columns. $\endgroup$ – Empy2 Jun 21 '16 at 0:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.