Question

If given the equation bx+dy+a=0 of a line ? in the plane, with 3 coefficients b,d,a, are integers expressed with, n bits (at most). One must determine whether line L passes through any point with integer coordinates. This is a problem that can be solved efficiently in the worst case in Θ time. What is that worst case time? Or is it impossible to do so?

Answer 1

Ans). We have a Diophantine equation (an equation of the form ax+by+c=0). Well, by using euclidean algorithm, we have integer solution for bx+dy=gcd(b,d).

Doing some analysis, we can find out the in order for a diophantine equation bx+dy+a=0 to have integer solution, we need only one condition : a is a multiple of gcd(b,d).

Thus the whole problem boils down to finding gcd which can be done in O(log(min(b,d))).

Therefore, the overall worst case complexity is O( Log( min(b,d) ) ).

Hope it helped! Feel free to ask any dount in comments. Don't forget to upvote if it helped :).