And now I am thinking to myself I wonder if anyone can provide a constructive proof of that theorem instead of just proving my conjecture, should I post a new question or update original question? Or are these both not appreciated moves. Thanks!
@Slugger I'm not a moderator, but... You could post a new question. When the original question is clear, changing it is not good as it usually invalidates existing answers (in rare cases it doesn't invalidate any of them and is not so bad). That said, a purely constructive proof can go as follows.
Take p<q such that gcd(p,q)=1. Let r in [1..p] such that qr≡1 (mod p). Then (p−1)·(q−1) ≡ (r−1)·q (mod p) so we get a solution. Now take k=a·p+b·q>p·q−p−q and we wish to form k+1. Let r'=p−r. If b≥r' then k+1≡a·p+(b−r')·q (mod p) and so we get a solution. If b<r' then it cannot be that a<(q·r−1)/p otherwise a·p+b·q≤(q·r−1−p)+(p−r−1)·q<p·q−p−q, and hence k+1≡(a−(q·r−1)/p)·p+(b+r)·q and so we get a solution.
