My program get TLE

Part of my code is:

Read(K);
 for i:=1 to K do begin
   Read(j);
   Seek(j,p,q);  // find p,q so that p*q=j
                 // i use in my program const array of all
                 // primes less that sqrt(10^9)
   Write('0 1');
   a:=0;
   r:=0;
   o:=0;

// now I try to find such a,b that
// p*a-q*b=1      or
// q*b-p*a=1

   tm:=q mod p;
   for t:=1 to p do begin
     r:=r+q;
     a:=a+tm; if a>p then a:=a-p;
     b:=a-1;
     if r>=j then break;
     if b=0 then begin write(' ',r);o:=o+1; end;
     b:=b+2; if b>=p then b:=b-p;
     if r>j then break;
     if b=0 then begin write(' ',r+1);o:=o+1; end;
     if o>=2 then break;
    end;
   writeln;
  end;

How I can improve my algorithm?

1. gcd(a,b) = sa + tb where s and t are integer
2. gcd(a,b) = gcd(b mod a, a)
3. since p and q are relatively prime, gcd(p,q)=1

For example, you should not search for both non-trivial solutions.

If solutions for test of N is = 0 1 A B then A+B-1=N.
I've used that in my program, and it has been ACCEPTED.

Certainly, you should use Euclid algorithm, not a brute force checking