Grid points on a straight line segment

Question

On squared paper, a straight segment is drawn from the point (0, 0) to the point (12, 18), where the coordinates are whole numbers.

How many points with whole-number coordinates lie on the segment, counting both endpoints? Find the general rule for a segment from (0, 0) to (a, b).

Accepted Answer

Seven points. In general, gcd(a, b) + 1. Parametrise. The points on the segment are (12t, 18t) for t from 0 to 1. For both coordinates to be whole numbers, t must be a fraction that turns both 12t and 18t into integers. Write t = p/q in lowest terms: then q must divide 12 and q must divide 18, so q divides the greatest common divisor of 12 and 18, which is 6. The allowed values of t are 0, 1/6, 2/6, ..., 6/6: seven values. List them. (0, 0), (2, 3), (4, 6), (6, 9), (8, 12), (10, 15), (12, 18). Each is the previous one plus (2, 3), and (2, 3) is (12, 18) divided by the gcd. General rule. A seg…

Grid points on a straight line segment

Your answer

Discussion

Learn the concepts

Related questions