Challenge Level

The triangle OMN has vertices M(0,m) and N(n,0) with whole number co-ordinates and we have to find how many lattice points there are on the hypotenuse MN.

The hint here was "First test what happens when m and n are
co-prime (have no common factor)", so this tells you that somehow
the problem involves common factors.

Absolutely the best way to learn is to make mistakes (generally if
you make none then the maths has not got enough challenge in it for
you).

A solution was sent in with a graph drawn for m=27 and n=20, and
the line looked as if it went through the point (3, 23) but it
actually goes through (3, 22.95). You have to check things like
this. One way is to draw the line yourself, decide what you think
about it, then check using a graphic calculator and using the trace
function which will give you readings of the co-ordinates of the
points on the line. ... When you go 20 squares in the x-direction
you have to go DOWN 27 squares in the y direction. You can't divide
this big step into smaller steps going across and down by whole
number changes. [If you use other numbers which have a common
factor, instead of 20 and 27, then there will be smaller steps
between points on the line which have whole number
co-ordinates].

Think about the line extended on and on in the example above. It
has equation:

27 x + 20 y = 540

and we are looking for whole number solutions to this equation (a
Diophantine equation).

We know that x = 0, y = 27 is a solution and if there is another
solution with a bigger x then it will go with a smaller y .

Looking at this equation we see that 20 divides exactly into 540 -
20y so x has to be a multiple of 20. Similarly y has to be a
multiple of 27. Solutions are given by points on the line with
integer co-ordinates and they are:

. . , (-20, 54), (0,27), (20, 0), (40, -27), . . .

When you go 20 squares in the x -direction you have to go DOWN 27
squares in the y direction. There are no solutions in the first
quadrant apart from the points on the axes.

The following is a short general proof of this result:

Theorem

If m and n are co-prime then there are no lattice points on the
line between M(0, m) and N(n, 0) in the first quadrant.

Proof

The line MN has equation mx + ny = mn

Suppose (p,q) is the lattice point on MN and we have

mp + nq = mn (1)

We see from (1) that n must divide nq so that, if m,n are co-prime,
then m must divide q so q = 0 or q = m

Similarly n divides mp so p = 0 or p = n. The only two lattice
points are the points M and N.

In the example given with m = 27 and n = 20. The only 2 lattice
points are the points M and N.

In the example given with m = 27 and n = 20 the general points with
whole number co-ordinates are given by:

x = 20t, y = 27 - 27t (where t is any integer).

Now you will need to do some work to check that when the greatest
common divisor of m and n is the number 2, so that m = 2r and n =
2s where r and s are co-prime, this introduces one lattice point
between M and N.

Next, if the greatest common divisor is 3, there will be two lattice points between M and N, and so on.

We use the notation gcd(m,n) for the greatest common divisor of m and n, so for example gcd(30, 70) = 10.

The general answer is that the number of lattice points (including M and N on the axes) is 1 + gcd(m,n).