Lattice points in a line

[Carlitos]

A point (x,y) in the plane is called a lattice point if both
coordinates x and y are integers.

Conjecture:
Given two lattice points (0,a) and (b,0) the number of lattice points
in the line joining them is gcd(a,b)+1.

Prove or disprove.

[Andres Santana]

Explain: "in the line joining them"...

--
arsh

[Carlitos]

The line joining (0,a) and (b,0).

On Nov 3, 4:00 pm, Andres Santana <andres.sant...@gmail.com> wrote:
> Explain: "in the line joining them"...
>

[Andres Santana]

I went to graph it using this tool: http://graph.seriesmathstudy.com/

And the function: f(x) = -x+6 

So: a=6 , b=6, gcd(6,6)=6 so there must be 7 lattice point in the line joining (0,6) and (6,0). I counted them there are actually 7. But still trying to figure out the relation with the GCD. 

Values to the function:

X 0 1 2 3 4 5 6 7 8

Y 6 5 4 3 2 1 0 -1 -2

Haven't found so much...

--
arsh

[Andres Santana]

Another thing:

GCD(a, 0) = |a|

So if you take a=0 or b=0 then we'll get the same number plus the zero...

I know this probably don't prove it...

--
arsh

[Carlitos]

Solution 1 (Analytical argument)

We can state this problem more precisely: find all integer solutions
to the equation,
(1) y = (-b/a)x + b, 0 <= x <= a.

Let d denote the greatest common divisor a and b. Hence, there exist
integers r and s such that
a = rd, and b = sd. Now, we can rewrite equation (1) as follows,
y = (-s/r)x + b.

Furthermore, note that y is an integer if and only if x is a multiple
of r. And that there are d+1
multiple of r between 0 and a. Therefore there are d+1 lattice points
between (a,0) and (0,b).


Solution 2 (Geometric argument)

First, consider a more general problem: lattice points in a
rectangular region, and particularly, in a
square region:

a = 1,

* *
* *

a = 2,

* * *
* * *
* * *

a = 3,

* * * *
* * * *
* * * *
* * * *

Now, it's clear that the diagonal contains a+1 lattice points and the
gcd(a,a) = a.
Thus the number of lattice points between (a,0) and (0,a) is gcd(a,a)
+1.

What about a rectangular region? From solution 1 we know that ab =
rsd^2. Hence a rectangular
region contains the same number of lattice points as the square of
side d. Therefore, the number of
lattice points between (a,0) and (0,b) is gcd(a,b)+1.

[Andres Santana]

Carlos correct me if I'm wrong but I think at my level expending too much time on this demonstration won't help me much. I understand covering other topics is more crucial at this point. What do you think?

Thanks.

--
arsh

[Carlitos]

You're definitely wrong. "Expending too much time" on demonstrations
is a good thing at any level; specially this one, because it doesn't
contain anything you don't know already.

On Nov 8, 3:41 pm, Andres Santana <andres.sant...@gmail.com> wrote:
> Carlos correct me if I'm wrong but I think at my level expending too much
> time on this demonstration won't help me much. I understand covering other
> topics is more crucial at this point. What do you think?
>
> Thanks.
>

[Carlitos]

You're definitely wrong. "Expending too much time" on demonstrations
is a good thing at any level; specially this one, because it doesn't
contain anything you don't know already.

On Nov 8, 3:41 pm, Andres Santana <andres.sant...@gmail.com> wrote:

> Carlos correct me if I'm wrong but I think at my level expending too much
> time on this demonstration won't help me much. I understand covering other
> topics is more crucial at this point. What do you think?
>
> Thanks.
>

[Andres Santana]

Ok, I believe you then.

--
arsh