# Given $p,q$ positive coprime numbers, prove that there exists $a$, $b$ positive integers such that $ap+bq=pq-1$ [duplicate]

A previous professor I had last year sent me this question, which he says he found an answer but it's too long, and asked me to try and solve it; though after solving it, my answer was a little long, so I'm curious to see if there's any shorter solution. The problem is the following:

Given $$p,q$$ positive coprime numbers, prove that there exists $$a$$, $$b$$ positive integers such that $$ap+bq=pq-1$$.

I began seeing that by Bezout's identity there exist $$A,B\in\mathbb{Z}$$ such that $$Ap+Bq=1$$, then multiplying that by $$pq-1$$ you get the following: $$A(pq-1)p+B(pq-1)q=pq-1$$ But we don't know if $$A(pq-1)$$ and $$B(pq-1)$$ are positive, so what I managed to do was to try to find positive solutions starting from those. What I did was set a general solution (of the equation $$a'p+b'q=pq-1$$) using that initial solution, and try to find a certain parameter $$k$$ which could make the solutions, let's call them $$A_k$$ and $$B_k$$ both positive; I hope this is enough explanation, otherwise I can try to explain more what I did but it would take me quite some time.

• We can handle a page and a half, let's see. Commented Mar 8, 2022 at 20:53
• Welcome to Math.SE! ... If you don't include your solution, no one can tell if their solution is different. This increases the possibility that someone will waste time duplicating your effort or explaining concepts you already understand.
– Blue
Commented Mar 8, 2022 at 20:55
• Hint: don't scale $\,Ap+Bq=1,\,$ instead subtract it from $\,pq.\ \$ Commented Mar 8, 2022 at 23:13
• Yeah, I should have seen that. Either way my solution is quite an overkill lol, I still like it tho. Commented Mar 10, 2022 at 11:14
• This follows immediately from basic results on the Frobenius coin problem, e.g. by here in the dupe, $\,px + qy = n > pq-p-q\,$ always has solutions $\,x,y\ge 0.\,$ OP is special case $\,n = pq-1\,$ (note $\,x\neq 0\,$ else: $\ qy = pq-1\Rightarrow q\mid 1;\,$ similarly $\,y\neq 0)$ Commented Mar 10, 2022 at 18:13

I am going to demand $$p,q \geq 2.$$ Treat one or both as $$1$$ as special cases for later consideration.
Begin with $$A_0p+B_0q = 1.$$ Take $$A = A_0 + s q$$ so that $$0 \leq A < q.$$ Note, with $$q \geq 2,$$ we actually have $$0 < A < q.$$ Then we have $$B = B_0 - s p,$$ we do have $$Ap+Bq=1,$$ we know $$A,B \neq 0.$$ Bounds on $$B$$ come from $$0 < Bq+Ap < Bq+qp = (B+p) q.$$ That is, $$p+B > 0.$$ And $$0 < A < q \; \; \; , \; \; \; -p < B < 0$$ But, you see, $$(q-A)p + (-B)q = pq-1$$