1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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)$

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The statement that any two numbers that sum to a prime are coprime is correct in the positive integers, but not in the integers. You could look at my answer for counterexamples. $\endgroup$ – Ross Millikan May 9 '17 at 4:26
  • 1
    $\begingroup$ I gave two specific examples. Do you claim either one is not on the line $y=p-x$? Do you dispute the hiding points I cited? Both have common factors of $p$. The statement that two numbers that sum to a prime are coprime is true in the naturals, but $-4+6=2$ and $-4$ and $6$ are not coprime. $\endgroup$ – Ross Millikan May 9 '17 at 5:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.