Prove that $N - lfloor{N/p}rfloor = lfloor{frac{p-1}{p}left({N + 1}right)}rfloor$ for positive $N$ and prime...
$begingroup$
I am counting the number of positive integers less than or equal to some positive integer $N$ and not divisible by some prime $p$. This gets generalized for $k$ primes where I use the principle of inclusion-exclusion for this result. The simple result for a single prime is $N - lfloor{frac{N}{p}}rfloor$. However, I have noticed by experiment that this is also equal to $lfloor{frac{p-1}{p} left({N + 1}right)}rfloor$. I am looking for a proof of this relation if true.
elementary-number-theory floor-function
edited Jan 9 at 4:24
David Holden
14.7k21224
asked Jan 9 at 3:39
Lorenz H MenkeLorenz H Menke
8911
$endgroup$
add a comment |
$begingroup$
I am counting the number of positive integers less than or equal to some positive integer $N$ and not divisible by some prime $p$. This gets generalized for $k$ primes where I use the principle of inclusion-exclusion for this result. The simple result for a single prime is $N - lfloor{frac{N}{p}}rfloor$. However, I have noticed by experiment that this is also equal to $lfloor{frac{p-1}{p} left({N + 1}right)}rfloor$. I am looking for a proof of this relation if true.
elementary-number-theory floor-function
edited Jan 9 at 4:24
David Holden
14.7k21224
asked Jan 9 at 3:39
Lorenz H MenkeLorenz H Menke
8911
$endgroup$
add a comment |
$begingroup$
I am counting the number of positive integers less than or equal to some positive integer $N$ and not divisible by some prime $p$. This gets generalized for $k$ primes where I use the principle of inclusion-exclusion for this result. The simple result for a single prime is $N - lfloor{frac{N}{p}}rfloor$. However, I have noticed by experiment that this is also equal to $lfloor{frac{p-1}{p} left({N + 1}right)}rfloor$. I am looking for a proof of this relation if true.
elementary-number-theory floor-function
edited Jan 9 at 4:24
David Holden
14.7k21224
asked Jan 9 at 3:39
Lorenz H MenkeLorenz H Menke
8911
$endgroup$
I am counting the number of positive integers less than or equal to some positive integer $N$ and not divisible by some prime $p$. This gets generalized for $k$ primes where I use the principle of inclusion-exclusion for this result. The simple result for a single prime is $N - lfloor{frac{N}{p}}rfloor$. However, I have noticed by experiment that this is also equal to $lfloor{frac{p-1}{p} left({N + 1}right)}rfloor$. I am looking for a proof of this relation if true.
elementary-number-theory floor-function
elementary-number-theory floor-function
edited Jan 9 at 4:24
David Holden
14.7k21224
asked Jan 9 at 3:39
Lorenz H MenkeLorenz H Menke
8911
edited Jan 9 at 4:24
David Holden
14.7k21224
asked Jan 9 at 3:39
Lorenz H MenkeLorenz H Menke
8911
edited Jan 9 at 4:24
David Holden
14.7k21224
edited Jan 9 at 4:24
David Holden
14.7k21224
edited Jan 9 at 4:24
David Holden
14.7k21224
14.7k21224
asked Jan 9 at 3:39
Lorenz H MenkeLorenz H Menke
8911
asked Jan 9 at 3:39
Lorenz H MenkeLorenz H Menke
8911
asked Jan 9 at 3:39
Lorenz H MenkeLorenz H Menke
8911
8911
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Consider that $N$ may be expressed as $N = ap + b$ for an integer $a$ and integer $0 le b le p - 1$. Using this, the left side of your equation becomes
$$N - lfloor N/p rfloor = ap + b - a tag{1}label{eq1} $$
Consider the numerator of the right side of your equation, i.e.,
$$left(p - 1right)left(N + 1right) = left(p - 1right)left(ap + b + 1right) = ap^2 + left(b + 1 - aright)p - left(b + 1right) tag{2}label{eq2}$$
Since $0 leq b leq p - 1$, then $1 leq b + 1 leq p$. As such, for any integer $M$, including $M = 0$, we have that
$$lfloor frac{Mp - left(b + 1right)}{p} rfloor = M - 1 tag{3}label{eq3}$$
Using $eqref{eq2}$ and $eqref{eq3}$ in the right side of your equation gives
$$lfloor frac{left(p - 1right)left(N + 1right)}{p} rfloor = ap + left(b + 1 - aright) + lfloor frac{-left(b + 1right)}{p} rfloor = ap + b - a tag{4}label{eq4} $$
As such, the LHS (from eqref{eq1}) is always equal to the RHS (from eqref{eq4} above), so your equation always holds. Note, this is true not only for primes $p$, but for all positive integers $p$, as I didn't use any particular properties of primes anywhere in the proof above.
answered Jan 9 at 4:27
John OmielanJohn Omielan
1,29629
$endgroup$
add a comment |
$begingroup$
let
$$
f(N) = N - lfloor frac{N}{p} rfloor
$$
then
$$
f(N+1) - f(N) = 1 - bigg(lfloor frac{N+1}{p} rfloor - lfloor frac{N}{p} rfloor bigg)
$$
thus when $N$ is incremented by 1, $f(N)$ is also incremented by 1 except when $N equiv_p -1$. in this case $f(N+1) = f(N)$
if now we let
$$
g(N) = lfloor{frac{p-1}{p} left({N + 1}right)}rfloor
$$
a little rearrangement gives
$$
g(N) = lfloor N+1 - frac{N+1}p rfloor= N+1 + lfloor -frac{N+1}p rfloor
$$
and
$$
g(N+1) - g(N) = 1 + bigg(lfloor -frac{N+2}{p} rfloor - lfloor -frac{N+1}{p} rfloor bigg)
$$
since $N$ is positive we again find that when $N$ increases by 1 the increment of $g$ is 1 except when $N equiv_p -1$.
since $f(1)=g(1)=1$ the result is demonstrated
answered Jan 9 at 4:52
David HoldenDavid Holden
14.7k21224
$endgroup$
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%2f3067045%2fprove-that-n-lfloorn-p-rfloor-lfloor-fracp-1p-leftn-1-right%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Consider that $N$ may be expressed as $N = ap + b$ for an integer $a$ and integer $0 le b le p - 1$. Using this, the left side of your equation becomes
$$N - lfloor N/p rfloor = ap + b - a tag{1}label{eq1} $$
Consider the numerator of the right side of your equation, i.e.,
$$left(p - 1right)left(N + 1right) = left(p - 1right)left(ap + b + 1right) = ap^2 + left(b + 1 - aright)p - left(b + 1right) tag{2}label{eq2}$$
Since $0 leq b leq p - 1$, then $1 leq b + 1 leq p$. As such, for any integer $M$, including $M = 0$, we have that
$$lfloor frac{Mp - left(b + 1right)}{p} rfloor = M - 1 tag{3}label{eq3}$$
Using $eqref{eq2}$ and $eqref{eq3}$ in the right side of your equation gives
$$lfloor frac{left(p - 1right)left(N + 1right)}{p} rfloor = ap + left(b + 1 - aright) + lfloor frac{-left(b + 1right)}{p} rfloor = ap + b - a tag{4}label{eq4} $$
As such, the LHS (from eqref{eq1}) is always equal to the RHS (from eqref{eq4} above), so your equation always holds. Note, this is true not only for primes $p$, but for all positive integers $p$, as I didn't use any particular properties of primes anywhere in the proof above.
answered Jan 9 at 4:27
John OmielanJohn Omielan
1,29629
$endgroup$
add a comment |
$begingroup$
Consider that $N$ may be expressed as $N = ap + b$ for an integer $a$ and integer $0 le b le p - 1$. Using this, the left side of your equation becomes
$$N - lfloor N/p rfloor = ap + b - a tag{1}label{eq1} $$
Consider the numerator of the right side of your equation, i.e.,
$$left(p - 1right)left(N + 1right) = left(p - 1right)left(ap + b + 1right) = ap^2 + left(b + 1 - aright)p - left(b + 1right) tag{2}label{eq2}$$
Since $0 leq b leq p - 1$, then $1 leq b + 1 leq p$. As such, for any integer $M$, including $M = 0$, we have that
$$lfloor frac{Mp - left(b + 1right)}{p} rfloor = M - 1 tag{3}label{eq3}$$
Using $eqref{eq2}$ and $eqref{eq3}$ in the right side of your equation gives
$$lfloor frac{left(p - 1right)left(N + 1right)}{p} rfloor = ap + left(b + 1 - aright) + lfloor frac{-left(b + 1right)}{p} rfloor = ap + b - a tag{4}label{eq4} $$
As such, the LHS (from eqref{eq1}) is always equal to the RHS (from eqref{eq4} above), so your equation always holds. Note, this is true not only for primes $p$, but for all positive integers $p$, as I didn't use any particular properties of primes anywhere in the proof above.
answered Jan 9 at 4:27
John OmielanJohn Omielan
1,29629
$endgroup$
add a comment |
$begingroup$
Consider that $N$ may be expressed as $N = ap + b$ for an integer $a$ and integer $0 le b le p - 1$. Using this, the left side of your equation becomes
$$N - lfloor N/p rfloor = ap + b - a tag{1}label{eq1} $$
Consider the numerator of the right side of your equation, i.e.,
$$left(p - 1right)left(N + 1right) = left(p - 1right)left(ap + b + 1right) = ap^2 + left(b + 1 - aright)p - left(b + 1right) tag{2}label{eq2}$$
Since $0 leq b leq p - 1$, then $1 leq b + 1 leq p$. As such, for any integer $M$, including $M = 0$, we have that
$$lfloor frac{Mp - left(b + 1right)}{p} rfloor = M - 1 tag{3}label{eq3}$$
Using $eqref{eq2}$ and $eqref{eq3}$ in the right side of your equation gives
$$lfloor frac{left(p - 1right)left(N + 1right)}{p} rfloor = ap + left(b + 1 - aright) + lfloor frac{-left(b + 1right)}{p} rfloor = ap + b - a tag{4}label{eq4} $$
As such, the LHS (from eqref{eq1}) is always equal to the RHS (from eqref{eq4} above), so your equation always holds. Note, this is true not only for primes $p$, but for all positive integers $p$, as I didn't use any particular properties of primes anywhere in the proof above.
answered Jan 9 at 4:27
John OmielanJohn Omielan
1,29629
$endgroup$
Consider that $N$ may be expressed as $N = ap + b$ for an integer $a$ and integer $0 le b le p - 1$. Using this, the left side of your equation becomes
$$N - lfloor N/p rfloor = ap + b - a tag{1}label{eq1} $$
Consider the numerator of the right side of your equation, i.e.,
$$left(p - 1right)left(N + 1right) = left(p - 1right)left(ap + b + 1right) = ap^2 + left(b + 1 - aright)p - left(b + 1right) tag{2}label{eq2}$$
Since $0 leq b leq p - 1$, then $1 leq b + 1 leq p$. As such, for any integer $M$, including $M = 0$, we have that
$$lfloor frac{Mp - left(b + 1right)}{p} rfloor = M - 1 tag{3}label{eq3}$$
Using $eqref{eq2}$ and $eqref{eq3}$ in the right side of your equation gives
$$lfloor frac{left(p - 1right)left(N + 1right)}{p} rfloor = ap + left(b + 1 - aright) + lfloor frac{-left(b + 1right)}{p} rfloor = ap + b - a tag{4}label{eq4} $$
As such, the LHS (from eqref{eq1}) is always equal to the RHS (from eqref{eq4} above), so your equation always holds. Note, this is true not only for primes $p$, but for all positive integers $p$, as I didn't use any particular properties of primes anywhere in the proof above.
answered Jan 9 at 4:27
John OmielanJohn Omielan
1,29629
edited Jan 9 at 4:44
answered Jan 9 at 4:27
John OmielanJohn Omielan
1,29629
answered Jan 9 at 4:27
John OmielanJohn Omielan
1,29629
answered Jan 9 at 4:27
John OmielanJohn Omielan
1,29629
1,29629
add a comment |
add a comment |
$begingroup$
let
$$
f(N) = N - lfloor frac{N}{p} rfloor
$$
then
$$
f(N+1) - f(N) = 1 - bigg(lfloor frac{N+1}{p} rfloor - lfloor frac{N}{p} rfloor bigg)
$$
thus when $N$ is incremented by 1, $f(N)$ is also incremented by 1 except when $N equiv_p -1$. in this case $f(N+1) = f(N)$
if now we let
$$
g(N) = lfloor{frac{p-1}{p} left({N + 1}right)}rfloor
$$
a little rearrangement gives
$$
g(N) = lfloor N+1 - frac{N+1}p rfloor= N+1 + lfloor -frac{N+1}p rfloor
$$
and
$$
g(N+1) - g(N) = 1 + bigg(lfloor -frac{N+2}{p} rfloor - lfloor -frac{N+1}{p} rfloor bigg)
$$
since $N$ is positive we again find that when $N$ increases by 1 the increment of $g$ is 1 except when $N equiv_p -1$.
since $f(1)=g(1)=1$ the result is demonstrated
answered Jan 9 at 4:52
David HoldenDavid Holden
14.7k21224
$endgroup$
add a comment |
$begingroup$
let
$$
f(N) = N - lfloor frac{N}{p} rfloor
$$
then
$$
f(N+1) - f(N) = 1 - bigg(lfloor frac{N+1}{p} rfloor - lfloor frac{N}{p} rfloor bigg)
$$
thus when $N$ is incremented by 1, $f(N)$ is also incremented by 1 except when $N equiv_p -1$. in this case $f(N+1) = f(N)$
if now we let
$$
g(N) = lfloor{frac{p-1}{p} left({N + 1}right)}rfloor
$$
a little rearrangement gives
$$
g(N) = lfloor N+1 - frac{N+1}p rfloor= N+1 + lfloor -frac{N+1}p rfloor
$$
and
$$
g(N+1) - g(N) = 1 + bigg(lfloor -frac{N+2}{p} rfloor - lfloor -frac{N+1}{p} rfloor bigg)
$$
since $N$ is positive we again find that when $N$ increases by 1 the increment of $g$ is 1 except when $N equiv_p -1$.
since $f(1)=g(1)=1$ the result is demonstrated
answered Jan 9 at 4:52
David HoldenDavid Holden
14.7k21224
$endgroup$
add a comment |
$begingroup$
let
$$
f(N) = N - lfloor frac{N}{p} rfloor
$$
then
$$
f(N+1) - f(N) = 1 - bigg(lfloor frac{N+1}{p} rfloor - lfloor frac{N}{p} rfloor bigg)
$$
thus when $N$ is incremented by 1, $f(N)$ is also incremented by 1 except when $N equiv_p -1$. in this case $f(N+1) = f(N)$
if now we let
$$
g(N) = lfloor{frac{p-1}{p} left({N + 1}right)}rfloor
$$
a little rearrangement gives
$$
g(N) = lfloor N+1 - frac{N+1}p rfloor= N+1 + lfloor -frac{N+1}p rfloor
$$
and
$$
g(N+1) - g(N) = 1 + bigg(lfloor -frac{N+2}{p} rfloor - lfloor -frac{N+1}{p} rfloor bigg)
$$
since $N$ is positive we again find that when $N$ increases by 1 the increment of $g$ is 1 except when $N equiv_p -1$.
since $f(1)=g(1)=1$ the result is demonstrated
answered Jan 9 at 4:52
David HoldenDavid Holden
14.7k21224
$endgroup$
let
$$
f(N) = N - lfloor frac{N}{p} rfloor
$$
then
$$
f(N+1) - f(N) = 1 - bigg(lfloor frac{N+1}{p} rfloor - lfloor frac{N}{p} rfloor bigg)
$$
thus when $N$ is incremented by 1, $f(N)$ is also incremented by 1 except when $N equiv_p -1$. in this case $f(N+1) = f(N)$
if now we let
$$
g(N) = lfloor{frac{p-1}{p} left({N + 1}right)}rfloor
$$
a little rearrangement gives
$$
g(N) = lfloor N+1 - frac{N+1}p rfloor= N+1 + lfloor -frac{N+1}p rfloor
$$
and
$$
g(N+1) - g(N) = 1 + bigg(lfloor -frac{N+2}{p} rfloor - lfloor -frac{N+1}{p} rfloor bigg)
$$
since $N$ is positive we again find that when $N$ increases by 1 the increment of $g$ is 1 except when $N equiv_p -1$.
since $f(1)=g(1)=1$ the result is demonstrated
answered Jan 9 at 4:52
David HoldenDavid Holden
14.7k21224
answered Jan 9 at 4:52
David HoldenDavid Holden
14.7k21224
answered Jan 9 at 4:52
David HoldenDavid Holden
14.7k21224
answered Jan 9 at 4:52
David HoldenDavid Holden
14.7k21224
14.7k21224
add a comment |
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%2f3067045%2fprove-that-n-lfloorn-p-rfloor-lfloor-fracp-1p-leftn-1-right%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
