Lattice Points

[Sojournmh]

I've uploaded a pic of my problem below. I really just don't understand at all how to figure this out. The first problem is about proving how the number of lattice points on a line segment is equal to the gcd(a2 - a1, b2-b1) + 1. And the second problem is about proving the number of boundary lattice points between 3 points is equal to the gcd(a1, b1) + gcd(a2,b2), + gcd(a2-a1, b2-b1).

I honestly just would like someone to help walk me through this step-by-step. I would really like to understand how to write this proof and my teacher just blazed past this.

 

[Dr.Peterson]

You might want to take the easy case first, and suppose that one point is at the origin. Think about what it means for a lattice point to lie on the line from (0,0) to (a,b).

Then you can generalize, perhaps by translating both points.

Let us know what ideas you get while doing this. We want to help you learn how to do a proof yourself, without having to depend on someone else to do it for you. You don't learn proofs by only watching others do them.

 

[Sojournmh]

The only way I could think of doing it would be doing something like finding the slope of the line segment and seeing if it could be reduced. Then you could see how many times (lattice points) it hits going along that slope between the two points?

 

[Dr.Peterson]

That's one way to think about it. The number you divide by when reducing the fraction will be (almost) the number of lattice points. Do you see why? And why I say "almost"?

Don't forget to think about whether the end points are considered to be "on the segment".

 

[Sojournmh]

well you would have to plus 1. And every base case I have done proves that this works. But how would I actually write this out for two arbitrary points like it wants me to?

 

[pka]

I have never before looked into lattices. I am completely awed by the number of resources available.
Here are two: page I , page II

 

[Dr.Peterson]

well you would have to plus 1. And every base case I have done proves that this works. But how would I actually write this out for two arbitrary points like it wants me to?

So what you have, presumably, is that for points (0, 0) and (a, b), the number of lattice points is gcd(a, b) + 1.

I suggested one way to generalize is to translate: For points (a_1, b_1) and (a_2, b_2), if you shift (a_1, b_1) to (0, 0), you are subtracting a_1 and b_1 from each pair -- that is, you replace (x, y) with (x - a_1, y - b_1). What are the two points after shifting? Since shifting (translating) will not change the number of lattice points, the answer is ...

Another way is just to repeat the very same thinking in this case -- what is the slope between (a_1, b_1) and (a_2, b_2)?