How to find the first integer point cartesian plan intersection of the line joining origin and another point?

Question

I have a cartesian plane as shown in the following image:

I want to find out given a point (x,y), what is the first point with integer coordinates lies in the line joining (0,0) and (x, y).

What is an efficient approach to answer the above question?

Currently, I am just going iterating x from [1, x] by incrementing it by +1 and checking if y = x * tan(phi) is an integer, where phi is in polar for point (x,y).

But the above approach seems very slow for large x. Is there a better approach to solve this problem?

Thanks in advance.

Answer 1

I’d try proving the following: if a non-vertical line passes through $(a,b)$ (where $a,b\in Z$), then the integer points the line passes through are precisely those of the form $(ma’,mb’)$ where $m \in Z$, and $a’ = a/\gcd(a,b)$, and $b’ = b/\gcd(a,b)$.

It will follow that the ‘first point’ (by which I think you mean the closest point to the origin in the first quadrant) will be $(a’,b’)$.