Lattice points on a line y = -x + p visible from the origin

157 Views Asked by At

Given a lattice point grid, for a line y = -x + p, where p is a prime, why is it true that each point on the line is visible from the origin? Another way of representing this problem is to ask why the gcd(p - n, n) = 1 for some prime p and integer n? Through my research, I know that the totient function will say how many points there will be on the line, but I don't see how to show that these coordinates have to be relatively prime, and thus visible from the origin.

Edit: I meant to include that the x and y intercepts on the line are not to be included in this. Also, I did not realize that two numbers that sum to a prime must be coprime, I believe that is what I needed, thanks!

2

There are 2 best solutions below

0
On

It is not true. $(p,0)$ is on the line, which is hidden by $(1,0)$. So is $(2p,-p)$ which is hidden by $(2,-1)$

2
On

The only lattice points which are visible from the origin are those for which, when represented as (x/y) rather than (x, y), are a fully reduced fraction. The equation y=p-x implies that x+y=p, and it is a fact that any two numbers which sum to a prime number are co-prime. Therefore, gcd(x,y)=1, i.e.(x/y) is fully reduced, i.e. (x,y) is visible from the origin.