56.7k views
1 vote
How many lattice points (points with integer coordinates) are on the line segment whose endpoints are $(3,17)$ and $(48,281)

User Derrops
by
7.1k points

1 Answer

2 votes

Any line through the points
(a,b) and
(c,d) has


\gcd(c-a,d-b)+1

lattice points. In this case, the count is GCD(45, 264) + 1.

Using Euclid's algorithm, we have

264 = 5•45 + 39

45 = 1•39 + 6

39 = 6•6 + 3

6 = 2•3 + 0

so that GCD(45, 264) = 3. Then there are 3 + 1 = 4 lattice points.

User Soteria
by
6.7k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.