Mixing
Let $p$ an odd prime, $s$ the smallest integer quadratic non residue modulo $p$. Prove that $p > 2s^2-s$...
$begingroup$
I'm suffering with a number theory question.
Let $p$ an odd prime, $s$ the smallest integer quadratic non-residue modulo $p$. Suppose $p > 5$ and $-1$ is a quadratic residue modulo $p$; then
$p > 2s^2-s$.
I already proved that for any $p$ odd $p > s^2-s$. (proof sketch: Let $q$ be the smallest positive integer such that $sq > p$ , and $r= sq-p$. Since $p$ is prime, $1<r<s$. Using Legendre symbols I could find that $q$ is a quadratic non-residue, so $q ge s$ and then $p > s^2-s$).
Following the extra information, using Euler's criterion, $p = 4n+1$. Unfortunately I have no clue how to use this piece of information.
elementary-number-theory quadratic-residues
asked Jan 28 at 23:41
user1553045user1553045
133
$endgroup$
add a comment |
$begingroup$
I'm suffering with a number theory question.
Let $p$ an odd prime, $s$ the smallest integer quadratic non-residue modulo $p$. Suppose $p > 5$ and $-1$ is a quadratic residue modulo $p$; then
$p > 2s^2-s$.
I already proved that for any $p$ odd $p > s^2-s$. (proof sketch: Let $q$ be the smallest positive integer such that $sq > p$ , and $r= sq-p$. Since $p$ is prime, $1<r<s$. Using Legendre symbols I could find that $q$ is a quadratic non-residue, so $q ge s$ and then $p > s^2-s$).
Following the extra information, using Euler's criterion, $p = 4n+1$. Unfortunately I have no clue how to use this piece of information.
elementary-number-theory quadratic-residues
asked Jan 28 at 23:41
user1553045user1553045
133
$endgroup$
1
$begingroup$
printing just primes 1 mod 4 when the smallest nonresidue increases: 5 2 2 s^2 - s: 6 \ 17 3 2 s^2 - s: 15 \ 73 5 2 s^2 - s: 45 \ 241 7 2 s^2 - s: 91 \ 1009 11 2 s^2 - s: 231 \ 2689 13 2 s^2 - s: 325 \ 8089 17 2 s^2 - s: 561 \ 33049 19 2 s^2 - s: 703 \ 53881 23 2 s^2 - s: 1035 \ 87481 29 2 s^2 - s: 1653 \
$endgroup$
– Will Jagy
Jan 29 at 1:15
$begingroup$
Out of curiosity, as this seems like a potentially quite difficult problem to solve, where does it come from?
$endgroup$
– John Omielan
Jan 29 at 3:50
$begingroup$
Note using that $-1$ is a quadratic residue, the largest non-quadratic residue is $p - s$. Thus, using what you've proven so far, i.e., $p gt s^2 - s$, since $s^2 - s = sleft(s - 1right)$ is a non-quadratic residue, then $sleft(s - 1right) le p - s$ which gives that $p ge s^2$, but as $p$ is prime, then $p gt s^2$. This is the best I can do so far.
$endgroup$
– John Omielan
Jan 29 at 6:20
2
$begingroup$
It come from BROCHERO, F., MOREIRA, C.G., SALDANHA, N., TENGAN, E. – Teoria dos números – um passeio pelo mundo inteiro com primos e outros números familiares, Projeto Euclides, IMPA, 2010, chapter 2, section 2.2. In this section we should learn second degree congruences, gauss lemma, law of quadratic reciprocity e legendre/jacobi symbols.
$endgroup$
– user1553045
Jan 29 at 10:11
$begingroup$
Thanks for providing the reference. I hope somebody can help you more than Will Jagy and I have so far.
$endgroup$
– John Omielan
Jan 29 at 11:28
add a comment |
$begingroup$
I'm suffering with a number theory question.
Let $p$ an odd prime, $s$ the smallest integer quadratic non-residue modulo $p$. Suppose $p > 5$ and $-1$ is a quadratic residue modulo $p$; then
$p > 2s^2-s$.
I already proved that for any $p$ odd $p > s^2-s$. (proof sketch: Let $q$ be the smallest positive integer such that $sq > p$ , and $r= sq-p$. Since $p$ is prime, $1<r<s$. Using Legendre symbols I could find that $q$ is a quadratic non-residue, so $q ge s$ and then $p > s^2-s$).
Following the extra information, using Euler's criterion, $p = 4n+1$. Unfortunately I have no clue how to use this piece of information.
elementary-number-theory quadratic-residues
asked Jan 28 at 23:41
user1553045user1553045
133
$endgroup$
I'm suffering with a number theory question.
Let $p$ an odd prime, $s$ the smallest integer quadratic non-residue modulo $p$. Suppose $p > 5$ and $-1$ is a quadratic residue modulo $p$; then
$p > 2s^2-s$.
I already proved that for any $p$ odd $p > s^2-s$. (proof sketch: Let $q$ be the smallest positive integer such that $sq > p$ , and $r= sq-p$. Since $p$ is prime, $1<r<s$. Using Legendre symbols I could find that $q$ is a quadratic non-residue, so $q ge s$ and then $p > s^2-s$).
Following the extra information, using Euler's criterion, $p = 4n+1$. Unfortunately I have no clue how to use this piece of information.
elementary-number-theory quadratic-residues
elementary-number-theory quadratic-residues
asked Jan 28 at 23:41
user1553045user1553045
133
asked Jan 28 at 23:41
user1553045user1553045
133
edited Jan 29 at 10:13
user1553045
asked Jan 28 at 23:41
user1553045user1553045
133
asked Jan 28 at 23:41
user1553045user1553045
133
asked Jan 28 at 23:41
user1553045user1553045
133
133
1
$begingroup$
printing just primes 1 mod 4 when the smallest nonresidue increases: 5 2 2 s^2 - s: 6 \ 17 3 2 s^2 - s: 15 \ 73 5 2 s^2 - s: 45 \ 241 7 2 s^2 - s: 91 \ 1009 11 2 s^2 - s: 231 \ 2689 13 2 s^2 - s: 325 \ 8089 17 2 s^2 - s: 561 \ 33049 19 2 s^2 - s: 703 \ 53881 23 2 s^2 - s: 1035 \ 87481 29 2 s^2 - s: 1653 \
$endgroup$
– Will Jagy
Jan 29 at 1:15
$begingroup$
Out of curiosity, as this seems like a potentially quite difficult problem to solve, where does it come from?
$endgroup$
– John Omielan
Jan 29 at 3:50
$begingroup$
Note using that $-1$ is a quadratic residue, the largest non-quadratic residue is $p - s$. Thus, using what you've proven so far, i.e., $p gt s^2 - s$, since $s^2 - s = sleft(s - 1right)$ is a non-quadratic residue, then $sleft(s - 1right) le p - s$ which gives that $p ge s^2$, but as $p$ is prime, then $p gt s^2$. This is the best I can do so far.
$endgroup$
– John Omielan
Jan 29 at 6:20
2
$begingroup$
It come from BROCHERO, F., MOREIRA, C.G., SALDANHA, N., TENGAN, E. – Teoria dos números – um passeio pelo mundo inteiro com primos e outros números familiares, Projeto Euclides, IMPA, 2010, chapter 2, section 2.2. In this section we should learn second degree congruences, gauss lemma, law of quadratic reciprocity e legendre/jacobi symbols.
$endgroup$
– user1553045
Jan 29 at 10:11
$begingroup$
Thanks for providing the reference. I hope somebody can help you more than Will Jagy and I have so far.
$endgroup$
– John Omielan
Jan 29 at 11:28
add a comment |
1
$begingroup$
printing just primes 1 mod 4 when the smallest nonresidue increases: 5 2 2 s^2 - s: 6 \ 17 3 2 s^2 - s: 15 \ 73 5 2 s^2 - s: 45 \ 241 7 2 s^2 - s: 91 \ 1009 11 2 s^2 - s: 231 \ 2689 13 2 s^2 - s: 325 \ 8089 17 2 s^2 - s: 561 \ 33049 19 2 s^2 - s: 703 \ 53881 23 2 s^2 - s: 1035 \ 87481 29 2 s^2 - s: 1653 \
$endgroup$
– Will Jagy
Jan 29 at 1:15
$begingroup$
Out of curiosity, as this seems like a potentially quite difficult problem to solve, where does it come from?
$endgroup$
– John Omielan
Jan 29 at 3:50
$begingroup$
Note using that $-1$ is a quadratic residue, the largest non-quadratic residue is $p - s$. Thus, using what you've proven so far, i.e., $p gt s^2 - s$, since $s^2 - s = sleft(s - 1right)$ is a non-quadratic residue, then $sleft(s - 1right) le p - s$ which gives that $p ge s^2$, but as $p$ is prime, then $p gt s^2$. This is the best I can do so far.
$endgroup$
– John Omielan
Jan 29 at 6:20
2
$begingroup$
It come from BROCHERO, F., MOREIRA, C.G., SALDANHA, N., TENGAN, E. – Teoria dos números – um passeio pelo mundo inteiro com primos e outros números familiares, Projeto Euclides, IMPA, 2010, chapter 2, section 2.2. In this section we should learn second degree congruences, gauss lemma, law of quadratic reciprocity e legendre/jacobi symbols.
$endgroup$
– user1553045
Jan 29 at 10:11
$begingroup$
Thanks for providing the reference. I hope somebody can help you more than Will Jagy and I have so far.
$endgroup$
– John Omielan
Jan 29 at 11:28
1
1
$begingroup$
printing just primes 1 mod 4 when the smallest nonresidue increases: 5 2 2 s^2 - s: 6 \ 17 3 2 s^2 - s: 15 \ 73 5 2 s^2 - s: 45 \ 241 7 2 s^2 - s: 91 \ 1009 11 2 s^2 - s: 231 \ 2689 13 2 s^2 - s: 325 \ 8089 17 2 s^2 - s: 561 \ 33049 19 2 s^2 - s: 703 \ 53881 23 2 s^2 - s: 1035 \ 87481 29 2 s^2 - s: 1653 \
$endgroup$
– Will Jagy
Jan 29 at 1:15
$begingroup$
printing just primes 1 mod 4 when the smallest nonresidue increases: 5 2 2 s^2 - s: 6 \ 17 3 2 s^2 - s: 15 \ 73 5 2 s^2 - s: 45 \ 241 7 2 s^2 - s: 91 \ 1009 11 2 s^2 - s: 231 \ 2689 13 2 s^2 - s: 325 \ 8089 17 2 s^2 - s: 561 \ 33049 19 2 s^2 - s: 703 \ 53881 23 2 s^2 - s: 1035 \ 87481 29 2 s^2 - s: 1653 \
$endgroup$
– Will Jagy
Jan 29 at 1:15
$begingroup$
Out of curiosity, as this seems like a potentially quite difficult problem to solve, where does it come from?
$endgroup$
– John Omielan
Jan 29 at 3:50
$begingroup$
Out of curiosity, as this seems like a potentially quite difficult problem to solve, where does it come from?
$endgroup$
– John Omielan
Jan 29 at 3:50
$begingroup$
Note using that $-1$ is a quadratic residue, the largest non-quadratic residue is $p - s$. Thus, using what you've proven so far, i.e., $p gt s^2 - s$, since $s^2 - s = sleft(s - 1right)$ is a non-quadratic residue, then $sleft(s - 1right) le p - s$ which gives that $p ge s^2$, but as $p$ is prime, then $p gt s^2$. This is the best I can do so far.
$endgroup$
– John Omielan
Jan 29 at 6:20
$begingroup$
Note using that $-1$ is a quadratic residue, the largest non-quadratic residue is $p - s$. Thus, using what you've proven so far, i.e., $p gt s^2 - s$, since $s^2 - s = sleft(s - 1right)$ is a non-quadratic residue, then $sleft(s - 1right) le p - s$ which gives that $p ge s^2$, but as $p$ is prime, then $p gt s^2$. This is the best I can do so far.
$endgroup$
– John Omielan
Jan 29 at 6:20
2
2
$begingroup$
It come from BROCHERO, F., MOREIRA, C.G., SALDANHA, N., TENGAN, E. – Teoria dos números – um passeio pelo mundo inteiro com primos e outros números familiares, Projeto Euclides, IMPA, 2010, chapter 2, section 2.2. In this section we should learn second degree congruences, gauss lemma, law of quadratic reciprocity e legendre/jacobi symbols.
$endgroup$
– user1553045
Jan 29 at 10:11
$begingroup$
It come from BROCHERO, F., MOREIRA, C.G., SALDANHA, N., TENGAN, E. – Teoria dos números – um passeio pelo mundo inteiro com primos e outros números familiares, Projeto Euclides, IMPA, 2010, chapter 2, section 2.2. In this section we should learn second degree congruences, gauss lemma, law of quadratic reciprocity e legendre/jacobi symbols.
$endgroup$
– user1553045
Jan 29 at 10:11
$begingroup$
Thanks for providing the reference. I hope somebody can help you more than Will Jagy and I have so far.
$endgroup$
– John Omielan
Jan 29 at 11:28
$begingroup$
Thanks for providing the reference. I hope somebody can help you more than Will Jagy and I have so far.
$endgroup$
– John Omielan
Jan 29 at 11:28
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The problem asks to prove that
$$p gt 2s^2 - s tag{1}label{eq1}$$
where $p$ is a prime $gt 5$, $-1$ is a quadratic residue and $s$ is the smallest non-quadratic residue.
Consider the case where $2$ is not a quadratic residue. Thus, $s = 2$ so $2s^2 - s = 6$, giving that all primes $p gt 5$ satisfy eqref{eq1}.
Next, consider $2$ is a quadratic residue, so $s ge 3$. Also, since $-1$ is also a quadratic residue, this means that so is any $0 lt n lt s$ times $p - 1$ as it's the product of $2$ quadratic residues. As such, apart from $p$ itself, all integers from $p - s - 1$ to $p + s - 1$, inclusive, are quadratic residues. This forms a contiguous range of $2s - 1$. Including $p + s$, this forms a range of $2s$. Similar to what the question suggests, this means there exists an integer $q$ such that $2qs$ is within this range. Note that $2qs = p$ can't be true. Also, if $2qs = p + s$, then $sleft(2q - 1right) = p$, which can't be the case. As such, we get that
$$p - s lt 2qs lt p + s tag{2}label{eq2}$$
Since all of the values in this range, apart from $p$, are quadratic residues, then so is $2qs$. Since $2$ is a quadratic residue, but $s$ is not, then $q$ can't be as well. Thus, $q ge s$. Using this in the right-hand part of eqref{eq2}, we get
$$p + s gt 2qs ge 2s^2 Rightarrow p gt 2s^2 - s tag{3}label{eq3}$$
As such, eqref{eq1} is also true in this case.
answered Jan 29 at 18:40
John OmielanJohn Omielan
4,4062215
$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%2f3091557%2flet-p-an-odd-prime-s-the-smallest-integer-quadratic-non-residue-modulo-p%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$
The problem asks to prove that
$$p gt 2s^2 - s tag{1}label{eq1}$$
where $p$ is a prime $gt 5$, $-1$ is a quadratic residue and $s$ is the smallest non-quadratic residue.
Consider the case where $2$ is not a quadratic residue. Thus, $s = 2$ so $2s^2 - s = 6$, giving that all primes $p gt 5$ satisfy eqref{eq1}.
Next, consider $2$ is a quadratic residue, so $s ge 3$. Also, since $-1$ is also a quadratic residue, this means that so is any $0 lt n lt s$ times $p - 1$ as it's the product of $2$ quadratic residues. As such, apart from $p$ itself, all integers from $p - s - 1$ to $p + s - 1$, inclusive, are quadratic residues. This forms a contiguous range of $2s - 1$. Including $p + s$, this forms a range of $2s$. Similar to what the question suggests, this means there exists an integer $q$ such that $2qs$ is within this range. Note that $2qs = p$ can't be true. Also, if $2qs = p + s$, then $sleft(2q - 1right) = p$, which can't be the case. As such, we get that
$$p - s lt 2qs lt p + s tag{2}label{eq2}$$
Since all of the values in this range, apart from $p$, are quadratic residues, then so is $2qs$. Since $2$ is a quadratic residue, but $s$ is not, then $q$ can't be as well. Thus, $q ge s$. Using this in the right-hand part of eqref{eq2}, we get
$$p + s gt 2qs ge 2s^2 Rightarrow p gt 2s^2 - s tag{3}label{eq3}$$
As such, eqref{eq1} is also true in this case.
answered Jan 29 at 18:40
John OmielanJohn Omielan
4,4062215
$endgroup$
add a comment |
$begingroup$
The problem asks to prove that
$$p gt 2s^2 - s tag{1}label{eq1}$$
where $p$ is a prime $gt 5$, $-1$ is a quadratic residue and $s$ is the smallest non-quadratic residue.
Consider the case where $2$ is not a quadratic residue. Thus, $s = 2$ so $2s^2 - s = 6$, giving that all primes $p gt 5$ satisfy eqref{eq1}.
Next, consider $2$ is a quadratic residue, so $s ge 3$. Also, since $-1$ is also a quadratic residue, this means that so is any $0 lt n lt s$ times $p - 1$ as it's the product of $2$ quadratic residues. As such, apart from $p$ itself, all integers from $p - s - 1$ to $p + s - 1$, inclusive, are quadratic residues. This forms a contiguous range of $2s - 1$. Including $p + s$, this forms a range of $2s$. Similar to what the question suggests, this means there exists an integer $q$ such that $2qs$ is within this range. Note that $2qs = p$ can't be true. Also, if $2qs = p + s$, then $sleft(2q - 1right) = p$, which can't be the case. As such, we get that
$$p - s lt 2qs lt p + s tag{2}label{eq2}$$
Since all of the values in this range, apart from $p$, are quadratic residues, then so is $2qs$. Since $2$ is a quadratic residue, but $s$ is not, then $q$ can't be as well. Thus, $q ge s$. Using this in the right-hand part of eqref{eq2}, we get
$$p + s gt 2qs ge 2s^2 Rightarrow p gt 2s^2 - s tag{3}label{eq3}$$
As such, eqref{eq1} is also true in this case.
answered Jan 29 at 18:40
John OmielanJohn Omielan
4,4062215
$endgroup$
add a comment |
$begingroup$
The problem asks to prove that
$$p gt 2s^2 - s tag{1}label{eq1}$$
where $p$ is a prime $gt 5$, $-1$ is a quadratic residue and $s$ is the smallest non-quadratic residue.
Consider the case where $2$ is not a quadratic residue. Thus, $s = 2$ so $2s^2 - s = 6$, giving that all primes $p gt 5$ satisfy eqref{eq1}.
Next, consider $2$ is a quadratic residue, so $s ge 3$. Also, since $-1$ is also a quadratic residue, this means that so is any $0 lt n lt s$ times $p - 1$ as it's the product of $2$ quadratic residues. As such, apart from $p$ itself, all integers from $p - s - 1$ to $p + s - 1$, inclusive, are quadratic residues. This forms a contiguous range of $2s - 1$. Including $p + s$, this forms a range of $2s$. Similar to what the question suggests, this means there exists an integer $q$ such that $2qs$ is within this range. Note that $2qs = p$ can't be true. Also, if $2qs = p + s$, then $sleft(2q - 1right) = p$, which can't be the case. As such, we get that
$$p - s lt 2qs lt p + s tag{2}label{eq2}$$
Since all of the values in this range, apart from $p$, are quadratic residues, then so is $2qs$. Since $2$ is a quadratic residue, but $s$ is not, then $q$ can't be as well. Thus, $q ge s$. Using this in the right-hand part of eqref{eq2}, we get
$$p + s gt 2qs ge 2s^2 Rightarrow p gt 2s^2 - s tag{3}label{eq3}$$
As such, eqref{eq1} is also true in this case.
answered Jan 29 at 18:40
John OmielanJohn Omielan
4,4062215
$endgroup$
The problem asks to prove that
$$p gt 2s^2 - s tag{1}label{eq1}$$
where $p$ is a prime $gt 5$, $-1$ is a quadratic residue and $s$ is the smallest non-quadratic residue.
Consider the case where $2$ is not a quadratic residue. Thus, $s = 2$ so $2s^2 - s = 6$, giving that all primes $p gt 5$ satisfy eqref{eq1}.
Next, consider $2$ is a quadratic residue, so $s ge 3$. Also, since $-1$ is also a quadratic residue, this means that so is any $0 lt n lt s$ times $p - 1$ as it's the product of $2$ quadratic residues. As such, apart from $p$ itself, all integers from $p - s - 1$ to $p + s - 1$, inclusive, are quadratic residues. This forms a contiguous range of $2s - 1$. Including $p + s$, this forms a range of $2s$. Similar to what the question suggests, this means there exists an integer $q$ such that $2qs$ is within this range. Note that $2qs = p$ can't be true. Also, if $2qs = p + s$, then $sleft(2q - 1right) = p$, which can't be the case. As such, we get that
$$p - s lt 2qs lt p + s tag{2}label{eq2}$$
Since all of the values in this range, apart from $p$, are quadratic residues, then so is $2qs$. Since $2$ is a quadratic residue, but $s$ is not, then $q$ can't be as well. Thus, $q ge s$. Using this in the right-hand part of eqref{eq2}, we get
$$p + s gt 2qs ge 2s^2 Rightarrow p gt 2s^2 - s tag{3}label{eq3}$$
As such, eqref{eq1} is also true in this case.
answered Jan 29 at 18:40
John OmielanJohn Omielan
4,4062215
edited Jan 29 at 19:17
answered Jan 29 at 18:40
John OmielanJohn Omielan
4,4062215
answered Jan 29 at 18:40
John OmielanJohn Omielan
4,4062215
answered Jan 29 at 18:40
John OmielanJohn Omielan
4,4062215
4,4062215
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%2f3091557%2flet-p-an-odd-prime-s-the-smallest-integer-quadratic-non-residue-modulo-p%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
1
$begingroup$
printing just primes 1 mod 4 when the smallest nonresidue increases: 5 2 2 s^2 - s: 6 \ 17 3 2 s^2 - s: 15 \ 73 5 2 s^2 - s: 45 \ 241 7 2 s^2 - s: 91 \ 1009 11 2 s^2 - s: 231 \ 2689 13 2 s^2 - s: 325 \ 8089 17 2 s^2 - s: 561 \ 33049 19 2 s^2 - s: 703 \ 53881 23 2 s^2 - s: 1035 \ 87481 29 2 s^2 - s: 1653 \
$endgroup$
– Will Jagy
Jan 29 at 1:15
$begingroup$
Out of curiosity, as this seems like a potentially quite difficult problem to solve, where does it come from?
$endgroup$
– John Omielan
Jan 29 at 3:50
$begingroup$
Note using that $-1$ is a quadratic residue, the largest non-quadratic residue is $p - s$. Thus, using what you've proven so far, i.e., $p gt s^2 - s$, since $s^2 - s = sleft(s - 1right)$ is a non-quadratic residue, then $sleft(s - 1right) le p - s$ which gives that $p ge s^2$, but as $p$ is prime, then $p gt s^2$. This is the best I can do so far.
$endgroup$
– John Omielan
Jan 29 at 6:20
2
$begingroup$
It come from BROCHERO, F., MOREIRA, C.G., SALDANHA, N., TENGAN, E. – Teoria dos números – um passeio pelo mundo inteiro com primos e outros números familiares, Projeto Euclides, IMPA, 2010, chapter 2, section 2.2. In this section we should learn second degree congruences, gauss lemma, law of quadratic reciprocity e legendre/jacobi symbols.
$endgroup$
– user1553045
Jan 29 at 10:11
$begingroup$
Thanks for providing the reference. I hope somebody can help you more than Will Jagy and I have so far.
$endgroup$
– John Omielan
Jan 29 at 11:28