How Many Points between two points?
$begingroup$
Given two points $A$ and $B$ on the $X-Y$-plane, I have to output the number of the lattice points on the segment $AB$. Note that $A$ and $B$ are also lattice point. Those who are confused with the definition of lattice point, lattice points are those points which have both $x$ and $y$ co-ordinate as an integer.
For example, for $A (3, 3)$ and $B (-1, -1)$ the output is $5$. The points are: $(-1, -1), (0, 0), (1, 1), (2, 2), (3, 3)$.
What is the procedure to solve this problem ?
number-theory
edited Jan 30 '15 at 18:08
Daniel W. Farlow
17.7k114488
asked Feb 13 '13 at 5:02
Way to infinityWay to infinity
1,07711128
$endgroup$
add a comment |
$begingroup$
Given two points $A$ and $B$ on the $X-Y$-plane, I have to output the number of the lattice points on the segment $AB$. Note that $A$ and $B$ are also lattice point. Those who are confused with the definition of lattice point, lattice points are those points which have both $x$ and $y$ co-ordinate as an integer.
For example, for $A (3, 3)$ and $B (-1, -1)$ the output is $5$. The points are: $(-1, -1), (0, 0), (1, 1), (2, 2), (3, 3)$.
What is the procedure to solve this problem ?
number-theory
edited Jan 30 '15 at 18:08
Daniel W. Farlow
17.7k114488
asked Feb 13 '13 at 5:02
Way to infinityWay to infinity
1,07711128
$endgroup$
add a comment |
$begingroup$
Given two points $A$ and $B$ on the $X-Y$-plane, I have to output the number of the lattice points on the segment $AB$. Note that $A$ and $B$ are also lattice point. Those who are confused with the definition of lattice point, lattice points are those points which have both $x$ and $y$ co-ordinate as an integer.
For example, for $A (3, 3)$ and $B (-1, -1)$ the output is $5$. The points are: $(-1, -1), (0, 0), (1, 1), (2, 2), (3, 3)$.
What is the procedure to solve this problem ?
number-theory
edited Jan 30 '15 at 18:08
Daniel W. Farlow
17.7k114488
asked Feb 13 '13 at 5:02
Way to infinityWay to infinity
1,07711128
$endgroup$
Given two points $A$ and $B$ on the $X-Y$-plane, I have to output the number of the lattice points on the segment $AB$. Note that $A$ and $B$ are also lattice point. Those who are confused with the definition of lattice point, lattice points are those points which have both $x$ and $y$ co-ordinate as an integer.
For example, for $A (3, 3)$ and $B (-1, -1)$ the output is $5$. The points are: $(-1, -1), (0, 0), (1, 1), (2, 2), (3, 3)$.
What is the procedure to solve this problem ?
number-theory
number-theory
edited Jan 30 '15 at 18:08
Daniel W. Farlow
17.7k114488
asked Feb 13 '13 at 5:02
Way to infinityWay to infinity
1,07711128
edited Jan 30 '15 at 18:08
Daniel W. Farlow
17.7k114488
asked Feb 13 '13 at 5:02
Way to infinityWay to infinity
1,07711128
edited Jan 30 '15 at 18:08
Daniel W. Farlow
17.7k114488
edited Jan 30 '15 at 18:08
Daniel W. Farlow
17.7k114488
edited Jan 30 '15 at 18:08
Daniel W. Farlow
17.7k114488
17.7k114488
asked Feb 13 '13 at 5:02
Way to infinityWay to infinity
1,07711128
asked Feb 13 '13 at 5:02
Way to infinityWay to infinity
1,07711128
asked Feb 13 '13 at 5:02
Way to infinityWay to infinity
1,07711128
1,07711128
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
HINT: Let one of the points be $langle a,brangle$ and the other $langle c,drangle$; then the number of lattice points on the line segment joining them is the same as the number on the line segment joining $langle 0,0rangle$ to $langle c-a,d-brangle$. Thus, you might as well focus on counting the number of lattice points on the segment joining the origin to $langle m,nrangle$ for integers $m$ and $n$. Look at the equation of the line containing this segment: it’s
$$y=frac{n}mx;.$$
Suppose that when you reduce $frac{n}m$ to lowest terms, you get $frac{q}r$. Then your equation is
$$y=frac{q}rx;,$$
and $y$ is an integer if and only if $rmid x$.
Added: Suppose that the points are $langle -2,55rangle$ and $langle 1011,1055rangle$. I’d look at the segment from the origin to $langle 1011-(-2),1055-55rangle=langle 1013,1000rangle$. It lies on the line
$$y=frac{1000}{1013}x;.$$
Any lattice point on that line must have both $x$ and $y$ integers, so suppose that $x$ is an integer. When is $frac{1000}{1013}x$ an integer? The fraction is in lowest terms, so this occurs only when $x$ is a multiple of $1013$. On the other hand, we’re looking only at the segment between $langle 0,0$ and $langle 1013,1000rangle$, so clearly we must have $0le xle 1013$. How many multiples of $1013$ are there in this range? Just two, $0$ and $1013$. Thus, the endpoints are the only lattice points on that segment. Translating it parallel to itself up and to the left by adding $langle 2,-55rangle$ to restore the original endpoints doesn’t change the number of lattice points, so $langle -2,55rangle$ and $langle 1011,1055rangle$ are the only lattice points on the original segment.
edited Oct 18 '15 at 8:46
Paul Tarjan
1034
answered Feb 13 '13 at 5:07
Brian M. ScottBrian M. Scott
458k38511913
$endgroup$
$begingroup$
Can you explain your answer for (a,b) = (-2,55) and (c,d)=(1011,1055) ?
$endgroup$
– Way to infinity
Feb 13 '13 at 5:22
$begingroup$
@SultanAhmedSagor: I’ve added a worked example based on those two points; it may help you to see what’s needed in the general case.
$endgroup$
– Brian M. Scott
Feb 13 '13 at 5:34
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f301890%2fhow-many-points-between-two-points%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
HINT: Let one of the points be $langle a,brangle$ and the other $langle c,drangle$; then the number of lattice points on the line segment joining them is the same as the number on the line segment joining $langle 0,0rangle$ to $langle c-a,d-brangle$. Thus, you might as well focus on counting the number of lattice points on the segment joining the origin to $langle m,nrangle$ for integers $m$ and $n$. Look at the equation of the line containing this segment: it’s
$$y=frac{n}mx;.$$
Suppose that when you reduce $frac{n}m$ to lowest terms, you get $frac{q}r$. Then your equation is
$$y=frac{q}rx;,$$
and $y$ is an integer if and only if $rmid x$.
Added: Suppose that the points are $langle -2,55rangle$ and $langle 1011,1055rangle$. I’d look at the segment from the origin to $langle 1011-(-2),1055-55rangle=langle 1013,1000rangle$. It lies on the line
$$y=frac{1000}{1013}x;.$$
Any lattice point on that line must have both $x$ and $y$ integers, so suppose that $x$ is an integer. When is $frac{1000}{1013}x$ an integer? The fraction is in lowest terms, so this occurs only when $x$ is a multiple of $1013$. On the other hand, we’re looking only at the segment between $langle 0,0$ and $langle 1013,1000rangle$, so clearly we must have $0le xle 1013$. How many multiples of $1013$ are there in this range? Just two, $0$ and $1013$. Thus, the endpoints are the only lattice points on that segment. Translating it parallel to itself up and to the left by adding $langle 2,-55rangle$ to restore the original endpoints doesn’t change the number of lattice points, so $langle -2,55rangle$ and $langle 1011,1055rangle$ are the only lattice points on the original segment.
edited Oct 18 '15 at 8:46
Paul Tarjan
1034
answered Feb 13 '13 at 5:07
Brian M. ScottBrian M. Scott
458k38511913
$endgroup$
$begingroup$
Can you explain your answer for (a,b) = (-2,55) and (c,d)=(1011,1055) ?
$endgroup$
– Way to infinity
Feb 13 '13 at 5:22
$begingroup$
@SultanAhmedSagor: I’ve added a worked example based on those two points; it may help you to see what’s needed in the general case.
$endgroup$
– Brian M. Scott
Feb 13 '13 at 5:34
add a comment |
$begingroup$
HINT: Let one of the points be $langle a,brangle$ and the other $langle c,drangle$; then the number of lattice points on the line segment joining them is the same as the number on the line segment joining $langle 0,0rangle$ to $langle c-a,d-brangle$. Thus, you might as well focus on counting the number of lattice points on the segment joining the origin to $langle m,nrangle$ for integers $m$ and $n$. Look at the equation of the line containing this segment: it’s
$$y=frac{n}mx;.$$
Suppose that when you reduce $frac{n}m$ to lowest terms, you get $frac{q}r$. Then your equation is
$$y=frac{q}rx;,$$
and $y$ is an integer if and only if $rmid x$.
Added: Suppose that the points are $langle -2,55rangle$ and $langle 1011,1055rangle$. I’d look at the segment from the origin to $langle 1011-(-2),1055-55rangle=langle 1013,1000rangle$. It lies on the line
$$y=frac{1000}{1013}x;.$$
Any lattice point on that line must have both $x$ and $y$ integers, so suppose that $x$ is an integer. When is $frac{1000}{1013}x$ an integer? The fraction is in lowest terms, so this occurs only when $x$ is a multiple of $1013$. On the other hand, we’re looking only at the segment between $langle 0,0$ and $langle 1013,1000rangle$, so clearly we must have $0le xle 1013$. How many multiples of $1013$ are there in this range? Just two, $0$ and $1013$. Thus, the endpoints are the only lattice points on that segment. Translating it parallel to itself up and to the left by adding $langle 2,-55rangle$ to restore the original endpoints doesn’t change the number of lattice points, so $langle -2,55rangle$ and $langle 1011,1055rangle$ are the only lattice points on the original segment.
edited Oct 18 '15 at 8:46
Paul Tarjan
1034
answered Feb 13 '13 at 5:07
Brian M. ScottBrian M. Scott
458k38511913
$endgroup$
$begingroup$
Can you explain your answer for (a,b) = (-2,55) and (c,d)=(1011,1055) ?
$endgroup$
– Way to infinity
Feb 13 '13 at 5:22
$begingroup$
@SultanAhmedSagor: I’ve added a worked example based on those two points; it may help you to see what’s needed in the general case.
$endgroup$
– Brian M. Scott
Feb 13 '13 at 5:34
add a comment |
$begingroup$
HINT: Let one of the points be $langle a,brangle$ and the other $langle c,drangle$; then the number of lattice points on the line segment joining them is the same as the number on the line segment joining $langle 0,0rangle$ to $langle c-a,d-brangle$. Thus, you might as well focus on counting the number of lattice points on the segment joining the origin to $langle m,nrangle$ for integers $m$ and $n$. Look at the equation of the line containing this segment: it’s
$$y=frac{n}mx;.$$
Suppose that when you reduce $frac{n}m$ to lowest terms, you get $frac{q}r$. Then your equation is
$$y=frac{q}rx;,$$
and $y$ is an integer if and only if $rmid x$.
Added: Suppose that the points are $langle -2,55rangle$ and $langle 1011,1055rangle$. I’d look at the segment from the origin to $langle 1011-(-2),1055-55rangle=langle 1013,1000rangle$. It lies on the line
$$y=frac{1000}{1013}x;.$$
Any lattice point on that line must have both $x$ and $y$ integers, so suppose that $x$ is an integer. When is $frac{1000}{1013}x$ an integer? The fraction is in lowest terms, so this occurs only when $x$ is a multiple of $1013$. On the other hand, we’re looking only at the segment between $langle 0,0$ and $langle 1013,1000rangle$, so clearly we must have $0le xle 1013$. How many multiples of $1013$ are there in this range? Just two, $0$ and $1013$. Thus, the endpoints are the only lattice points on that segment. Translating it parallel to itself up and to the left by adding $langle 2,-55rangle$ to restore the original endpoints doesn’t change the number of lattice points, so $langle -2,55rangle$ and $langle 1011,1055rangle$ are the only lattice points on the original segment.
edited Oct 18 '15 at 8:46
Paul Tarjan
1034
answered Feb 13 '13 at 5:07
Brian M. ScottBrian M. Scott
458k38511913
$endgroup$
HINT: Let one of the points be $langle a,brangle$ and the other $langle c,drangle$; then the number of lattice points on the line segment joining them is the same as the number on the line segment joining $langle 0,0rangle$ to $langle c-a,d-brangle$. Thus, you might as well focus on counting the number of lattice points on the segment joining the origin to $langle m,nrangle$ for integers $m$ and $n$. Look at the equation of the line containing this segment: it’s
$$y=frac{n}mx;.$$
Suppose that when you reduce $frac{n}m$ to lowest terms, you get $frac{q}r$. Then your equation is
$$y=frac{q}rx;,$$
and $y$ is an integer if and only if $rmid x$.
Added: Suppose that the points are $langle -2,55rangle$ and $langle 1011,1055rangle$. I’d look at the segment from the origin to $langle 1011-(-2),1055-55rangle=langle 1013,1000rangle$. It lies on the line
$$y=frac{1000}{1013}x;.$$
Any lattice point on that line must have both $x$ and $y$ integers, so suppose that $x$ is an integer. When is $frac{1000}{1013}x$ an integer? The fraction is in lowest terms, so this occurs only when $x$ is a multiple of $1013$. On the other hand, we’re looking only at the segment between $langle 0,0$ and $langle 1013,1000rangle$, so clearly we must have $0le xle 1013$. How many multiples of $1013$ are there in this range? Just two, $0$ and $1013$. Thus, the endpoints are the only lattice points on that segment. Translating it parallel to itself up and to the left by adding $langle 2,-55rangle$ to restore the original endpoints doesn’t change the number of lattice points, so $langle -2,55rangle$ and $langle 1011,1055rangle$ are the only lattice points on the original segment.
edited Oct 18 '15 at 8:46
Paul Tarjan
1034
answered Feb 13 '13 at 5:07
Brian M. ScottBrian M. Scott
458k38511913
edited Oct 18 '15 at 8:46
Paul Tarjan
1034
edited Oct 18 '15 at 8:46
Paul Tarjan
1034
edited Oct 18 '15 at 8:46
Paul Tarjan
1034
1034
answered Feb 13 '13 at 5:07
Brian M. ScottBrian M. Scott
458k38511913
answered Feb 13 '13 at 5:07
Brian M. ScottBrian M. Scott
458k38511913
answered Feb 13 '13 at 5:07
Brian M. ScottBrian M. Scott
458k38511913
458k38511913
$begingroup$
Can you explain your answer for (a,b) = (-2,55) and (c,d)=(1011,1055) ?
$endgroup$
– Way to infinity
Feb 13 '13 at 5:22
$begingroup$
@SultanAhmedSagor: I’ve added a worked example based on those two points; it may help you to see what’s needed in the general case.
$endgroup$
– Brian M. Scott
Feb 13 '13 at 5:34
add a comment |
$begingroup$
Can you explain your answer for (a,b) = (-2,55) and (c,d)=(1011,1055) ?
$endgroup$
– Way to infinity
Feb 13 '13 at 5:22
$begingroup$
@SultanAhmedSagor: I’ve added a worked example based on those two points; it may help you to see what’s needed in the general case.
$endgroup$
– Brian M. Scott
Feb 13 '13 at 5:34
$begingroup$
Can you explain your answer for (a,b) = (-2,55) and (c,d)=(1011,1055) ?
$endgroup$
– Way to infinity
Feb 13 '13 at 5:22
$begingroup$
Can you explain your answer for (a,b) = (-2,55) and (c,d)=(1011,1055) ?
$endgroup$
– Way to infinity
Feb 13 '13 at 5:22
$begingroup$
@SultanAhmedSagor: I’ve added a worked example based on those two points; it may help you to see what’s needed in the general case.
$endgroup$
– Brian M. Scott
Feb 13 '13 at 5:34
$begingroup$
@SultanAhmedSagor: I’ve added a worked example based on those two points; it may help you to see what’s needed in the general case.
$endgroup$
– Brian M. Scott
Feb 13 '13 at 5:34
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f301890%2fhow-many-points-between-two-points%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
