Dgdrxrt

Has negative voting ever been officially implemented in elections, or seriously proposed, or even studied?

Is "Reachable Object" really an NP-complete problem?

Can anything be seen from the center of the Boötes void? How dark would it be?

Would "destroying" Wurmcoil Engine prevent its tokens from being created?

Is it ethical to give a final exam after the professor has quit before teaching the remaining chapters of the course?

Trademark violation for app?

What is the meaning of the simile “quick as silk”?

Do jazz musicians improvise on the parent scale in addition to the chord-scales?

Why are there no cargo aircraft with "flying wing" design?

What do you call the main part of a joke?

2001: A Space Odyssey's use of the song "Daisy Bell" (Bicycle Built for Two); life imitates art or vice-versa?

When the Haste spell ends on a creature, do attackers have advantage against that creature?

また usage in a dictionary

What is the escape velocity of a neutron particle (not neutron star)

Most bit efficient text communication method?

Can an alien society believe that their star system is the universe?

How can I use the Python library networkx from Mathematica?

Should I use a zero-interest credit card for a large one-time purchase?

Closed form of recurrent arithmetic series summation

Do I really need to have a message in a novel to appeal to readers?

Fantasy story; one type of magic grows in power with use, but the more powerful they are, they more they are drawn to travel to their source

Do I really need recursive chmod to restrict access to a folder?

Is it a good idea to use CNN to classify 1D signal?

Does classifying an integer as a discrete log require it be part of a multiplicative group?

show that the set $M, M+1, cdots, M+ 2lfloor sqrtp rfloor +2$ contains a quadratic non-residue to modulus $p$

4

1

$begingroup$

Let $M$ be an integer, and let $p$ be a odd prime . Show that the set $$ M+1,M+2,M+3,cdots,M+ 2lfloor sqrtp rfloor+2$$ contains a quadratic non-residue to modulus $ p$ for all primes $ p$

maybe can use this well know:
Smallest quadratic nonresidue is less than square root plus one An odd prime $p$, $a$ is the smallest positive integer that is a quadratic nonresidue modulo $p$,then $a<1+sqrtp$.

maybe can sove this problem?

number-theory

share|cite|improve this question

edited Apr 1 at 13:04

function sug

asked Apr 1 at 3:44

function sugfunction sug

2731439

$endgroup$

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  What is the point of placing a bounty on a solved problem? Is anything unclear / to be explained in my solution?
  $endgroup$
  – W-t-P
  Apr 3 at 13:27
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  sorry, I don't think you're going to be able to read this. Could you be more specific?and I bounty this problem hope can see clear solution or other methods to solve it,But Thank you
  $endgroup$
  – function sug
  Apr 6 at 14:59
  
  

  
  
  
  

add a comment | 

4

1

$begingroup$

Let $M$ be an integer, and let $p$ be a odd prime . Show that the set $$ M+1,M+2,M+3,cdots,M+ 2lfloor sqrtp rfloor+2$$ contains a quadratic non-residue to modulus $ p$ for all primes $ p$

maybe can use this well know:
Smallest quadratic nonresidue is less than square root plus one An odd prime $p$, $a$ is the smallest positive integer that is a quadratic nonresidue modulo $p$,then $a<1+sqrtp$.

maybe can sove this problem?

number-theory

share|cite|improve this question

edited Apr 1 at 13:04

function sug

asked Apr 1 at 3:44

function sugfunction sug

2731439

$endgroup$

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  What is the point of placing a bounty on a solved problem? Is anything unclear / to be explained in my solution?
  $endgroup$
  – W-t-P
  Apr 3 at 13:27
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  sorry, I don't think you're going to be able to read this. Could you be more specific?and I bounty this problem hope can see clear solution or other methods to solve it,But Thank you
  $endgroup$
  – function sug
  Apr 6 at 14:59
  
  

  
  
  
  

add a comment | 

$begingroup$

Let $M$ be an integer, and let $p$ be a odd prime . Show that the set $$ M+1,M+2,M+3,cdots,M+ 2lfloor sqrtp rfloor+2$$ contains a quadratic non-residue to modulus $ p$ for all primes $ p$

maybe can use this well know:
Smallest quadratic nonresidue is less than square root plus one An odd prime $p$, $a$ is the smallest positive integer that is a quadratic nonresidue modulo $p$,then $a<1+sqrtp$.

maybe can sove this problem?

number-theory

share|cite|improve this question

edited Apr 1 at 13:04

function sug

asked Apr 1 at 3:44

function sugfunction sug

2731439

$endgroup$

share|cite|improve this question

edited Apr 1 at 13:04

function sug

asked Apr 1 at 3:44

function sugfunction sug

2731439

share|cite|improve this question

edited Apr 1 at 13:04

function sug

asked Apr 1 at 3:44

function sugfunction sug

2731439

asked Apr 1 at 3:44

function sugfunction sug

2731439

asked Apr 1 at 3:44

function sugfunction sug

2731439

1 Answer
1

active

oldest

votes

3

+50

$begingroup$

We know that there is a quadratic non-residue $n$ with $2le n<sqrt p+1$. Multiplying $n$ by the appropriate power of $4$, we can find a quadratic non-resdiue, say $n'$, in the range $frac12sqrt p<n'<2sqrt p$.

Consider the set
$$ S = Mn',(M+1)n',dotsc,(M+2lfloorsqrt prfloor+2)n'pmod p. $$
The "distance" in $mathbb Z_p$ between any two consecutive elements of this set is $n'<2lfloorsqrt prfloor+2$, and there is no gap between the largest and the the smallest elements of the set since
$$ (M+2lfloorsqrt prfloor+2)n' > Mn' + p. $$
It follows that every interval in $mathbb Z_p$ of length $2lfloorsqrt prfloor+2$ contains at least one element of $S$. In particular, there is an element of $S$ contained in $M,M+1,dotsc,M+2lfloorsqrt prfloor+2$. In other words, there are $x,yinM,M+1,ldots,M+2lfloorsqrt prfloor+2$ such that $yequiv n'xpmod p$. Since $n'$ is a non-residue, so is (exactly) one of $x$ and $y$.

share|cite|improve this answer

edited Apr 3 at 17:16

answered Apr 1 at 17:36

W-t-PW-t-P

1,847612

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Hello, Multiplying n by the appropriate power of 4,we can find a quadratic non-resdiue, say $n'?$, it means there exist $delta$,such $4^delta n=n'?$,such $frac12sqrtp<4^delta n<2sqrtp$.if so,How to sure there exist this $delta?$
  $endgroup$
  – function sug
  Apr 6 at 14:57
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @functionsug: Let $delta$ be the largest integer with $4^delta n<2sqrt p$. Then $4^delta+1 n>2sqrt p$; that is, $4cdot 4^delta n>2sqrt p$, showing that $4^delta n>frac12sqrt p$. Thus, $frac12sqrt p< 4^delta n<2sqrt p$, and we let $n'=4^delta n$.
  $endgroup$
  – W-t-P
  Apr 6 at 16:09
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @functionsug: informally, you just keep multiplying $n$ by $4$ till the resulting product hits the interval $(frac12sqrt p,2sqrt p)$. You cannot jump over this interval since the right endpoint of the interval is 4 times larger than its left endpoint.
  $endgroup$
  – W-t-P
  Apr 6 at 20:21
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I can't understand why demand $n'<2sqrtp$What's the point of this restriction? Thanks,
  $endgroup$
  – function sug
  Apr 7 at 14:13
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  For the argument to go through, we want to ensure that there is a non-residue $n'$ in the interval $(frac12sqrt p,2sqrt p)$. To this end, we multiply $n$ by $4$ till the resulting product is less than $2sqrt p$. All these multiples of $n$ are quadratic non-residues, and the largest of them will land in the target interval $(frac12sqrt p,2sqrt p)$. Try to work out a numerical example, such as $p=5003$, $n=3$.
  $endgroup$
  – W-t-P
  Apr 7 at 16:24
  
  

  
  
  
  

add a comment | 

Your Answer

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



);

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3170182%2fshow-that-the-set-m-m1-cdots-m-2-lfloor-sqrtp-rfloor-2-contains%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

3

+50

$begingroup$

We know that there is a quadratic non-residue $n$ with $2le n<sqrt p+1$. Multiplying $n$ by the appropriate power of $4$, we can find a quadratic non-resdiue, say $n'$, in the range $frac12sqrt p<n'<2sqrt p$.

Consider the set
$$ S = Mn',(M+1)n',dotsc,(M+2lfloorsqrt prfloor+2)n'pmod p. $$
The "distance" in $mathbb Z_p$ between any two consecutive elements of this set is $n'<2lfloorsqrt prfloor+2$, and there is no gap between the largest and the the smallest elements of the set since
$$ (M+2lfloorsqrt prfloor+2)n' > Mn' + p. $$
It follows that every interval in $mathbb Z_p$ of length $2lfloorsqrt prfloor+2$ contains at least one element of $S$. In particular, there is an element of $S$ contained in $M,M+1,dotsc,M+2lfloorsqrt prfloor+2$. In other words, there are $x,yinM,M+1,ldots,M+2lfloorsqrt prfloor+2$ such that $yequiv n'xpmod p$. Since $n'$ is a non-residue, so is (exactly) one of $x$ and $y$.

share|cite|improve this answer

edited Apr 3 at 17:16

answered Apr 1 at 17:36

W-t-PW-t-P

1,847612

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Hello, Multiplying n by the appropriate power of 4,we can find a quadratic non-resdiue, say $n'?$, it means there exist $delta$,such $4^delta n=n'?$,such $frac12sqrtp<4^delta n<2sqrtp$.if so,How to sure there exist this $delta?$
  $endgroup$
  – function sug
  Apr 6 at 14:57
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @functionsug: Let $delta$ be the largest integer with $4^delta n<2sqrt p$. Then $4^delta+1 n>2sqrt p$; that is, $4cdot 4^delta n>2sqrt p$, showing that $4^delta n>frac12sqrt p$. Thus, $frac12sqrt p< 4^delta n<2sqrt p$, and we let $n'=4^delta n$.
  $endgroup$
  – W-t-P
  Apr 6 at 16:09
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @functionsug: informally, you just keep multiplying $n$ by $4$ till the resulting product hits the interval $(frac12sqrt p,2sqrt p)$. You cannot jump over this interval since the right endpoint of the interval is 4 times larger than its left endpoint.
  $endgroup$
  – W-t-P
  Apr 6 at 20:21
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I can't understand why demand $n'<2sqrtp$What's the point of this restriction? Thanks,
  $endgroup$
  – function sug
  Apr 7 at 14:13
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  For the argument to go through, we want to ensure that there is a non-residue $n'$ in the interval $(frac12sqrt p,2sqrt p)$. To this end, we multiply $n$ by $4$ till the resulting product is less than $2sqrt p$. All these multiples of $n$ are quadratic non-residues, and the largest of them will land in the target interval $(frac12sqrt p,2sqrt p)$. Try to work out a numerical example, such as $p=5003$, $n=3$.
  $endgroup$
  – W-t-P
  Apr 7 at 16:24
  
  

  
  
  
  

add a comment | 

3

+50

$begingroup$

We know that there is a quadratic non-residue $n$ with $2le n<sqrt p+1$. Multiplying $n$ by the appropriate power of $4$, we can find a quadratic non-resdiue, say $n'$, in the range $frac12sqrt p<n'<2sqrt p$.

Consider the set
$$ S = Mn',(M+1)n',dotsc,(M+2lfloorsqrt prfloor+2)n'pmod p. $$
The "distance" in $mathbb Z_p$ between any two consecutive elements of this set is $n'<2lfloorsqrt prfloor+2$, and there is no gap between the largest and the the smallest elements of the set since
$$ (M+2lfloorsqrt prfloor+2)n' > Mn' + p. $$
It follows that every interval in $mathbb Z_p$ of length $2lfloorsqrt prfloor+2$ contains at least one element of $S$. In particular, there is an element of $S$ contained in $M,M+1,dotsc,M+2lfloorsqrt prfloor+2$. In other words, there are $x,yinM,M+1,ldots,M+2lfloorsqrt prfloor+2$ such that $yequiv n'xpmod p$. Since $n'$ is a non-residue, so is (exactly) one of $x$ and $y$.

share|cite|improve this answer

edited Apr 3 at 17:16

answered Apr 1 at 17:36

W-t-PW-t-P

1,847612

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Hello, Multiplying n by the appropriate power of 4,we can find a quadratic non-resdiue, say $n'?$, it means there exist $delta$,such $4^delta n=n'?$,such $frac12sqrtp<4^delta n<2sqrtp$.if so,How to sure there exist this $delta?$
  $endgroup$
  – function sug
  Apr 6 at 14:57
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @functionsug: Let $delta$ be the largest integer with $4^delta n<2sqrt p$. Then $4^delta+1 n>2sqrt p$; that is, $4cdot 4^delta n>2sqrt p$, showing that $4^delta n>frac12sqrt p$. Thus, $frac12sqrt p< 4^delta n<2sqrt p$, and we let $n'=4^delta n$.
  $endgroup$
  – W-t-P
  Apr 6 at 16:09
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @functionsug: informally, you just keep multiplying $n$ by $4$ till the resulting product hits the interval $(frac12sqrt p,2sqrt p)$. You cannot jump over this interval since the right endpoint of the interval is 4 times larger than its left endpoint.
  $endgroup$
  – W-t-P
  Apr 6 at 20:21
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I can't understand why demand $n'<2sqrtp$What's the point of this restriction? Thanks,
  $endgroup$
  – function sug
  Apr 7 at 14:13
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  For the argument to go through, we want to ensure that there is a non-residue $n'$ in the interval $(frac12sqrt p,2sqrt p)$. To this end, we multiply $n$ by $4$ till the resulting product is less than $2sqrt p$. All these multiples of $n$ are quadratic non-residues, and the largest of them will land in the target interval $(frac12sqrt p,2sqrt p)$. Try to work out a numerical example, such as $p=5003$, $n=3$.
  $endgroup$
  – W-t-P
  Apr 7 at 16:24
  
  

  
  
  
  

add a comment | 

$begingroup$

We know that there is a quadratic non-residue $n$ with $2le n<sqrt p+1$. Multiplying $n$ by the appropriate power of $4$, we can find a quadratic non-resdiue, say $n'$, in the range $frac12sqrt p<n'<2sqrt p$.

Consider the set
$$ S = Mn',(M+1)n',dotsc,(M+2lfloorsqrt prfloor+2)n'pmod p. $$
The "distance" in $mathbb Z_p$ between any two consecutive elements of this set is $n'<2lfloorsqrt prfloor+2$, and there is no gap between the largest and the the smallest elements of the set since
$$ (M+2lfloorsqrt prfloor+2)n' > Mn' + p. $$
It follows that every interval in $mathbb Z_p$ of length $2lfloorsqrt prfloor+2$ contains at least one element of $S$. In particular, there is an element of $S$ contained in $M,M+1,dotsc,M+2lfloorsqrt prfloor+2$. In other words, there are $x,yinM,M+1,ldots,M+2lfloorsqrt prfloor+2$ such that $yequiv n'xpmod p$. Since $n'$ is a non-residue, so is (exactly) one of $x$ and $y$.

share|cite|improve this answer

edited Apr 3 at 17:16

answered Apr 1 at 17:36

W-t-PW-t-P

1,847612

$endgroup$

share|cite|improve this answer

edited Apr 3 at 17:16

answered Apr 1 at 17:36

W-t-PW-t-P

1,847612

answered Apr 1 at 17:36

W-t-PW-t-P

1,847612

answered Apr 1 at 17:36

W-t-PW-t-P

1,847612