Is there always a positive integer $a$ such that both $a^2-4$ and $a^2+4$ are quadratic non-residues $bmod...
$begingroup$
I would like to prove (disprove if wrong) the following statement:
For all odd prime numbers except for $p=3,5$ or $13$, there exists an
integer $a>0$ such that both $a^2-4$ and $a^2+4$ are quadratic
non-residue $bmod p$.
Here is what I have done: suppose that $p notin {3,5,13}$ and consider different cases:
Case I: $p equiv 3 bmod 4$. We have $q$ is quadratic residue (QR) iff $-q$ is quadratic non-residue (QNR).
Since $p neq 5$, then either $5$ is QNR (case I-i) or $5$ is QR (case I-ii).
In case (I-i) there exists $b$ such that $b^2 equiv -5 bmod p$ and obviously $-b^2+4 equiv 3^2 bmod p$ and $-b^2-4 equiv 1 bmod p$, then both $b^2-4$ and $b^2+4$ are QNR. It suffices to take $a=b$.
Consider now case (I-ii). Since $p neq 13$, then either
(I-ii-1) $13$ is quadratic non-residue (QNR) mod $p$
(I-ii-2) $13$ is quadratic residue (QR) mod $p$
In case (I-ii-1), $65=5cdot 13$ is QNR and there exists $c$ such that $c^2 equiv -65 bmod p$ and obviously $-c^2-16 equiv 7^2 bmod p$ and $-c^2+16 equiv 9^2 bmod p$.
Let $d=frac{c}{2}$, $e=frac{7}{2}$ and $f=frac{9}{2}$ in $ mathbb{Z}/pmathbb{Z}$.
Then $-d^2-4 equiv e^2 bmod p$ and $-d^2+4 equiv f^2 bmod p$ and both $d^2+4$ and $d^2-4$ are QNR. It suffices to take $a=d$.
In the case (I-ii-2) where both $5$ and $13$ are QR, I don't see how to proceed.
In the case (II) where $p equiv 1 bmod 4$, we have $q$ is quadratic residue (QR) iff $-q$ is quadratic residue (QNR) and here again the above method does not seem to work.
I am also interested in any sharp upper bound for the smallest $a$, in terms of $p$.
Thanks for help.
number-theory elementary-number-theory quadratic-residues
asked Jan 13 at 1:12
René GyRené Gy
1,230713
$endgroup$
add a comment |
$begingroup$
I would like to prove (disprove if wrong) the following statement:
For all odd prime numbers except for $p=3,5$ or $13$, there exists an
integer $a>0$ such that both $a^2-4$ and $a^2+4$ are quadratic
non-residue $bmod p$.
Here is what I have done: suppose that $p notin {3,5,13}$ and consider different cases:
Case I: $p equiv 3 bmod 4$. We have $q$ is quadratic residue (QR) iff $-q$ is quadratic non-residue (QNR).
Since $p neq 5$, then either $5$ is QNR (case I-i) or $5$ is QR (case I-ii).
In case (I-i) there exists $b$ such that $b^2 equiv -5 bmod p$ and obviously $-b^2+4 equiv 3^2 bmod p$ and $-b^2-4 equiv 1 bmod p$, then both $b^2-4$ and $b^2+4$ are QNR. It suffices to take $a=b$.
Consider now case (I-ii). Since $p neq 13$, then either
(I-ii-1) $13$ is quadratic non-residue (QNR) mod $p$
(I-ii-2) $13$ is quadratic residue (QR) mod $p$
In case (I-ii-1), $65=5cdot 13$ is QNR and there exists $c$ such that $c^2 equiv -65 bmod p$ and obviously $-c^2-16 equiv 7^2 bmod p$ and $-c^2+16 equiv 9^2 bmod p$.
Let $d=frac{c}{2}$, $e=frac{7}{2}$ and $f=frac{9}{2}$ in $ mathbb{Z}/pmathbb{Z}$.
Then $-d^2-4 equiv e^2 bmod p$ and $-d^2+4 equiv f^2 bmod p$ and both $d^2+4$ and $d^2-4$ are QNR. It suffices to take $a=d$.
In the case (I-ii-2) where both $5$ and $13$ are QR, I don't see how to proceed.
In the case (II) where $p equiv 1 bmod 4$, we have $q$ is quadratic residue (QR) iff $-q$ is quadratic residue (QNR) and here again the above method does not seem to work.
I am also interested in any sharp upper bound for the smallest $a$, in terms of $p$.
Thanks for help.
number-theory elementary-number-theory quadratic-residues
asked Jan 13 at 1:12
René GyRené Gy
1,230713
$endgroup$
4
$begingroup$
If you have three consecutive numbers that are non-residue, residue, non-residue, then multiplying by four gives you $a^2pm4$ both nonresidues. The standard way to tackle this sort ofmproblem is via exponential sums.
$endgroup$
– Gerry Myerson
Jan 13 at 1:54
$begingroup$
@Gerry Myerson Thanks, this comment is key in Misha Lavrov's solution.
$endgroup$
– René Gy
Jan 13 at 9:20
add a comment |
$begingroup$
I would like to prove (disprove if wrong) the following statement:
For all odd prime numbers except for $p=3,5$ or $13$, there exists an
integer $a>0$ such that both $a^2-4$ and $a^2+4$ are quadratic
non-residue $bmod p$.
Here is what I have done: suppose that $p notin {3,5,13}$ and consider different cases:
Case I: $p equiv 3 bmod 4$. We have $q$ is quadratic residue (QR) iff $-q$ is quadratic non-residue (QNR).
Since $p neq 5$, then either $5$ is QNR (case I-i) or $5$ is QR (case I-ii).
In case (I-i) there exists $b$ such that $b^2 equiv -5 bmod p$ and obviously $-b^2+4 equiv 3^2 bmod p$ and $-b^2-4 equiv 1 bmod p$, then both $b^2-4$ and $b^2+4$ are QNR. It suffices to take $a=b$.
Consider now case (I-ii). Since $p neq 13$, then either
(I-ii-1) $13$ is quadratic non-residue (QNR) mod $p$
(I-ii-2) $13$ is quadratic residue (QR) mod $p$
In case (I-ii-1), $65=5cdot 13$ is QNR and there exists $c$ such that $c^2 equiv -65 bmod p$ and obviously $-c^2-16 equiv 7^2 bmod p$ and $-c^2+16 equiv 9^2 bmod p$.
Let $d=frac{c}{2}$, $e=frac{7}{2}$ and $f=frac{9}{2}$ in $ mathbb{Z}/pmathbb{Z}$.
Then $-d^2-4 equiv e^2 bmod p$ and $-d^2+4 equiv f^2 bmod p$ and both $d^2+4$ and $d^2-4$ are QNR. It suffices to take $a=d$.
In the case (I-ii-2) where both $5$ and $13$ are QR, I don't see how to proceed.
In the case (II) where $p equiv 1 bmod 4$, we have $q$ is quadratic residue (QR) iff $-q$ is quadratic residue (QNR) and here again the above method does not seem to work.
I am also interested in any sharp upper bound for the smallest $a$, in terms of $p$.
Thanks for help.
number-theory elementary-number-theory quadratic-residues
asked Jan 13 at 1:12
René GyRené Gy
1,230713
$endgroup$
I would like to prove (disprove if wrong) the following statement:
For all odd prime numbers except for $p=3,5$ or $13$, there exists an
integer $a>0$ such that both $a^2-4$ and $a^2+4$ are quadratic
non-residue $bmod p$.
Here is what I have done: suppose that $p notin {3,5,13}$ and consider different cases:
Case I: $p equiv 3 bmod 4$. We have $q$ is quadratic residue (QR) iff $-q$ is quadratic non-residue (QNR).
Since $p neq 5$, then either $5$ is QNR (case I-i) or $5$ is QR (case I-ii).
In case (I-i) there exists $b$ such that $b^2 equiv -5 bmod p$ and obviously $-b^2+4 equiv 3^2 bmod p$ and $-b^2-4 equiv 1 bmod p$, then both $b^2-4$ and $b^2+4$ are QNR. It suffices to take $a=b$.
Consider now case (I-ii). Since $p neq 13$, then either
(I-ii-1) $13$ is quadratic non-residue (QNR) mod $p$
(I-ii-2) $13$ is quadratic residue (QR) mod $p$
In case (I-ii-1), $65=5cdot 13$ is QNR and there exists $c$ such that $c^2 equiv -65 bmod p$ and obviously $-c^2-16 equiv 7^2 bmod p$ and $-c^2+16 equiv 9^2 bmod p$.
Let $d=frac{c}{2}$, $e=frac{7}{2}$ and $f=frac{9}{2}$ in $ mathbb{Z}/pmathbb{Z}$.
Then $-d^2-4 equiv e^2 bmod p$ and $-d^2+4 equiv f^2 bmod p$ and both $d^2+4$ and $d^2-4$ are QNR. It suffices to take $a=d$.
In the case (I-ii-2) where both $5$ and $13$ are QR, I don't see how to proceed.
In the case (II) where $p equiv 1 bmod 4$, we have $q$ is quadratic residue (QR) iff $-q$ is quadratic residue (QNR) and here again the above method does not seem to work.
I am also interested in any sharp upper bound for the smallest $a$, in terms of $p$.
Thanks for help.
number-theory elementary-number-theory quadratic-residues
number-theory elementary-number-theory quadratic-residues
asked Jan 13 at 1:12
René GyRené Gy
1,230713
asked Jan 13 at 1:12
René GyRené Gy
1,230713
asked Jan 13 at 1:12
René GyRené Gy
1,230713
asked Jan 13 at 1:12
René GyRené Gy
1,230713
asked Jan 13 at 1:12
René GyRené Gy
1,230713
1,230713
4
$begingroup$
If you have three consecutive numbers that are non-residue, residue, non-residue, then multiplying by four gives you $a^2pm4$ both nonresidues. The standard way to tackle this sort ofmproblem is via exponential sums.
$endgroup$
– Gerry Myerson
Jan 13 at 1:54
$begingroup$
@Gerry Myerson Thanks, this comment is key in Misha Lavrov's solution.
$endgroup$
– René Gy
Jan 13 at 9:20
add a comment |
4
$begingroup$
If you have three consecutive numbers that are non-residue, residue, non-residue, then multiplying by four gives you $a^2pm4$ both nonresidues. The standard way to tackle this sort ofmproblem is via exponential sums.
$endgroup$
– Gerry Myerson
Jan 13 at 1:54
$begingroup$
@Gerry Myerson Thanks, this comment is key in Misha Lavrov's solution.
$endgroup$
– René Gy
Jan 13 at 9:20
4
4
$begingroup$
If you have three consecutive numbers that are non-residue, residue, non-residue, then multiplying by four gives you $a^2pm4$ both nonresidues. The standard way to tackle this sort ofmproblem is via exponential sums.
$endgroup$
– Gerry Myerson
Jan 13 at 1:54
$begingroup$
If you have three consecutive numbers that are non-residue, residue, non-residue, then multiplying by four gives you $a^2pm4$ both nonresidues. The standard way to tackle this sort ofmproblem is via exponential sums.
$endgroup$
– Gerry Myerson
Jan 13 at 1:54
$begingroup$
@Gerry Myerson Thanks, this comment is key in Misha Lavrov's solution.
$endgroup$
– René Gy
Jan 13 at 9:20
$begingroup$
@Gerry Myerson Thanks, this comment is key in Misha Lavrov's solution.
$endgroup$
– René Gy
Jan 13 at 9:20
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Here is a solution in two steps.
First, we prove that when there is no such $a$, 2 is a QR. This is a bunch of casework, and doesn't work for some small primes. (Specifically for $p=2, 3, 5, 7, 11, 13$.) We can check those separately, and find all three counterexamples that way.
Suppose that 2 is a QNR. Therefore 8 is a QNR, 32 is a QNR, 18 is a QNR.
40 must be a QR or else we find the sequence 32, 36, 40. Therefore 20 is a QNR.
12 must be a QR or else we find the sequence 12, 16, 20. Therefore 24 is a QNR, 48 is a QR, 96 is a QNR.
104 must be a QR or else we find the sequence 96, 100, 104. Therefore 52 is a QNR.
28 must be a QNR or else we find the sequence 24, 28, 32. Therefore 14 is a QR.
22 must be a QR or else we find the sequence 14, 18, 22. Therefore 44 is a QNR.
Now we find the sequence 44, 48, 52.
Second, assuming that $2$ is a QR and there are no cases of $a$ such that $a^2-4$, $a^2+4$ are QNR, we arrive at a contradiction.
If any three consecutive integers $k, k+1, k+2$ follow the pattern QNR, QR, QNR, then the same is true for $4k, 4k+4, 4k+8$ and we are done. So adjacent to any QR is another QR.
If this is true, but no two consecutive integers are ever QNR, then we're also in trouble, because then at least approximately $frac23$ of the residues mod $p$ are QR.
Suppose that $k, k+1$ are both QNR for some $k$. Then $8k, 8k+8$ are both QNR, so $8k+4$ must be QNR or else $8k, 8k+4, 8k+8$ is the sequence we want. (Note that $8k+4 notequiv 0 pmod p$ because then $8k+8$ could not be QNR.) Therefore $2k, 2k+1, 2k+2$ is a sequence of three consecutive QNRs.
Applying this argument again, we see that $4k, 4k+1, 4k+2, 4k+3, 4k+4$ is a sequence of five consecutive QNRs. Then we get ever-longer sequences like this by iterating the argument. But once we get a sequence longer than $p$, we get a contradiction.
answered Jan 13 at 3:21
Misha LavrovMisha Lavrov
49.6k759109
$endgroup$
$begingroup$
This is quite complex argumentation, but I like it because all steps are elementary.
$endgroup$
– René Gy
Jan 13 at 9:15
add a comment |
$begingroup$
seems believable
jagy@phobeusjunior:~$ ./mse
p 3 fails p 5 fails p 7 a: 3 p 11 a: 5 p 13 fails
p 17 a: 1 p 19 a: 5 p 23 a: 1 p 29 a: 6 p 31 a: 5
p 37 a: 3 p 41 a: 8 p 43 a: 4 p 47 a: 1 p 53 a: 1
p 59 a: 6 p 61 a: 5 p 67 a: 3 p 71 a: 13 p 73 a: 3
p 79 a: 8 p 83 a: 1 p 89 a: 10 p 97 a: 3 p 101 a: 6
p 103 a: 4 p 107 a: 1 p 109 a: 6 p 113 a: 1 p 127 a: 4
p 131 a: 6 p 137 a: 1 p 139 a: 6 p 149 a: 6 p 151 a: 10
p 157 a: 5 p 163 a: 3 p 167 a: 1 p 173 a: 1 p 179 a: 6
p 181 a: 6 p 191 a: 5 p 193 a: 3 p 197 a: 1 p 199 a: 8
p 211 a: 6 p 223 a: 3 p 227 a: 1 p 229 a: 5 p 233 a: 1
p 239 a: 12 p 241 a: 12 p 251 a: 6 p 257 a: 1 p 263 a: 1
p 269 a: 6 p 271 a: 5 p 277 a: 7 p 281 a: 10 p 283 a: 4
p 293 a: 1 p 307 a: 3 p 311 a: 9 p 313 a: 7 p 317 a: 1
p 331 a: 6 p 337 a: 7 p 347 a: 1 p 349 a: 6 p 353 a: 1
p 359 a: 5 p 367 a: 4 p 373 a: 7 p 379 a: 6 p 383 a: 1
p 389 a: 5 p 397 a: 3 p 401 a: 8 p 409 a: 5 p 419 a: 6
p 421 a: 6 p 431 a: 9 p 433 a: 5 p 439 a: 8 p 443 a: 1
p 449 a: 5 p 457 a: 3 p 461 a: 6 p 463 a: 3 p 467 a: 1
p 479 a: 24 p 487 a: 3 p 491 a: 5 p 499 a: 6 p 503 a: 1
p 509 a: 6 p 521 a: 8 p 523 a: 4 p 541 a: 6 p 547 a: 4
p 557 a: 1 p 563 a: 1 p 569 a: 5 p 571 a: 6 p 577 a: 3
p 587 a: 1 p 593 a: 1 p 599 a: 5 p 601 a: 5 p 607 a: 4
p 613 a: 3 p 617 a: 1 p 619 a: 5 p 631 a: 10 p 641 a: 5
p 643 a: 3 p 647 a: 1 p 653 a: 1 p 659 a: 5 p 661 a: 6
p 673 a: 8 p 677 a: 1 p 683 a: 1 p 691 a: 6 p 701 a: 6
p 709 a: 6 p 719 a: 9 p 727 a: 4 p 733 a: 3 p 739 a: 6
p 743 a: 1 p 751 a: 8 p 757 a: 10 p 761 a: 10 p 769 a: 5
p 773 a: 1 p 787 a: 3 p 797 a: 1 p 809 a: 5 p 811 a: 6
p 821 a: 6 p 823 a: 4 p 827 a: 1 p 829 a: 5 p 839 a: 9
p 853 a: 3 p 857 a: 1 p 859 a: 5 p 863 a: 1 p 877 a: 3
p 881 a: 8 p 883 a: 4 p 887 a: 1 p 907 a: 4 p 911 a: 5
p 919 a: 12 p 929 a: 8 p 937 a: 16 p 941 a: 6 p 947 a: 1
p 953 a: 1 p 967 a: 3 p 971 a: 6 p 977 a: 1 p 983 a: 1
p 991 a: 8 p 997 a: 5 p 1009 a: 9 p 1013 a: 1 p 1019 a: 6
p 1021 a: 6 p 1031 a: 9 p 1033 a: 3 p 1039 a: 19 p 1049 a: 8
answered Jan 13 at 1:54
Will JagyWill Jagy
104k5103202
$endgroup$
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
});
}
});
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%2f3071602%2fis-there-always-a-positive-integer-a-such-that-both-a2-4-and-a24-are-qu%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$
Here is a solution in two steps.
First, we prove that when there is no such $a$, 2 is a QR. This is a bunch of casework, and doesn't work for some small primes. (Specifically for $p=2, 3, 5, 7, 11, 13$.) We can check those separately, and find all three counterexamples that way.
Suppose that 2 is a QNR. Therefore 8 is a QNR, 32 is a QNR, 18 is a QNR.
40 must be a QR or else we find the sequence 32, 36, 40. Therefore 20 is a QNR.
12 must be a QR or else we find the sequence 12, 16, 20. Therefore 24 is a QNR, 48 is a QR, 96 is a QNR.
104 must be a QR or else we find the sequence 96, 100, 104. Therefore 52 is a QNR.
28 must be a QNR or else we find the sequence 24, 28, 32. Therefore 14 is a QR.
22 must be a QR or else we find the sequence 14, 18, 22. Therefore 44 is a QNR.
Now we find the sequence 44, 48, 52.
Second, assuming that $2$ is a QR and there are no cases of $a$ such that $a^2-4$, $a^2+4$ are QNR, we arrive at a contradiction.
If any three consecutive integers $k, k+1, k+2$ follow the pattern QNR, QR, QNR, then the same is true for $4k, 4k+4, 4k+8$ and we are done. So adjacent to any QR is another QR.
If this is true, but no two consecutive integers are ever QNR, then we're also in trouble, because then at least approximately $frac23$ of the residues mod $p$ are QR.
Suppose that $k, k+1$ are both QNR for some $k$. Then $8k, 8k+8$ are both QNR, so $8k+4$ must be QNR or else $8k, 8k+4, 8k+8$ is the sequence we want. (Note that $8k+4 notequiv 0 pmod p$ because then $8k+8$ could not be QNR.) Therefore $2k, 2k+1, 2k+2$ is a sequence of three consecutive QNRs.
Applying this argument again, we see that $4k, 4k+1, 4k+2, 4k+3, 4k+4$ is a sequence of five consecutive QNRs. Then we get ever-longer sequences like this by iterating the argument. But once we get a sequence longer than $p$, we get a contradiction.
answered Jan 13 at 3:21
Misha LavrovMisha Lavrov
49.6k759109
$endgroup$
$begingroup$
This is quite complex argumentation, but I like it because all steps are elementary.
$endgroup$
– René Gy
Jan 13 at 9:15
add a comment |
$begingroup$
Here is a solution in two steps.
First, we prove that when there is no such $a$, 2 is a QR. This is a bunch of casework, and doesn't work for some small primes. (Specifically for $p=2, 3, 5, 7, 11, 13$.) We can check those separately, and find all three counterexamples that way.
Suppose that 2 is a QNR. Therefore 8 is a QNR, 32 is a QNR, 18 is a QNR.
40 must be a QR or else we find the sequence 32, 36, 40. Therefore 20 is a QNR.
12 must be a QR or else we find the sequence 12, 16, 20. Therefore 24 is a QNR, 48 is a QR, 96 is a QNR.
104 must be a QR or else we find the sequence 96, 100, 104. Therefore 52 is a QNR.
28 must be a QNR or else we find the sequence 24, 28, 32. Therefore 14 is a QR.
22 must be a QR or else we find the sequence 14, 18, 22. Therefore 44 is a QNR.
Now we find the sequence 44, 48, 52.
Second, assuming that $2$ is a QR and there are no cases of $a$ such that $a^2-4$, $a^2+4$ are QNR, we arrive at a contradiction.
If any three consecutive integers $k, k+1, k+2$ follow the pattern QNR, QR, QNR, then the same is true for $4k, 4k+4, 4k+8$ and we are done. So adjacent to any QR is another QR.
If this is true, but no two consecutive integers are ever QNR, then we're also in trouble, because then at least approximately $frac23$ of the residues mod $p$ are QR.
Suppose that $k, k+1$ are both QNR for some $k$. Then $8k, 8k+8$ are both QNR, so $8k+4$ must be QNR or else $8k, 8k+4, 8k+8$ is the sequence we want. (Note that $8k+4 notequiv 0 pmod p$ because then $8k+8$ could not be QNR.) Therefore $2k, 2k+1, 2k+2$ is a sequence of three consecutive QNRs.
Applying this argument again, we see that $4k, 4k+1, 4k+2, 4k+3, 4k+4$ is a sequence of five consecutive QNRs. Then we get ever-longer sequences like this by iterating the argument. But once we get a sequence longer than $p$, we get a contradiction.
answered Jan 13 at 3:21
Misha LavrovMisha Lavrov
49.6k759109
$endgroup$
$begingroup$
This is quite complex argumentation, but I like it because all steps are elementary.
$endgroup$
– René Gy
Jan 13 at 9:15
add a comment |
$begingroup$
Here is a solution in two steps.
First, we prove that when there is no such $a$, 2 is a QR. This is a bunch of casework, and doesn't work for some small primes. (Specifically for $p=2, 3, 5, 7, 11, 13$.) We can check those separately, and find all three counterexamples that way.
Suppose that 2 is a QNR. Therefore 8 is a QNR, 32 is a QNR, 18 is a QNR.
40 must be a QR or else we find the sequence 32, 36, 40. Therefore 20 is a QNR.
12 must be a QR or else we find the sequence 12, 16, 20. Therefore 24 is a QNR, 48 is a QR, 96 is a QNR.
104 must be a QR or else we find the sequence 96, 100, 104. Therefore 52 is a QNR.
28 must be a QNR or else we find the sequence 24, 28, 32. Therefore 14 is a QR.
22 must be a QR or else we find the sequence 14, 18, 22. Therefore 44 is a QNR.
Now we find the sequence 44, 48, 52.
Second, assuming that $2$ is a QR and there are no cases of $a$ such that $a^2-4$, $a^2+4$ are QNR, we arrive at a contradiction.
If any three consecutive integers $k, k+1, k+2$ follow the pattern QNR, QR, QNR, then the same is true for $4k, 4k+4, 4k+8$ and we are done. So adjacent to any QR is another QR.
If this is true, but no two consecutive integers are ever QNR, then we're also in trouble, because then at least approximately $frac23$ of the residues mod $p$ are QR.
Suppose that $k, k+1$ are both QNR for some $k$. Then $8k, 8k+8$ are both QNR, so $8k+4$ must be QNR or else $8k, 8k+4, 8k+8$ is the sequence we want. (Note that $8k+4 notequiv 0 pmod p$ because then $8k+8$ could not be QNR.) Therefore $2k, 2k+1, 2k+2$ is a sequence of three consecutive QNRs.
Applying this argument again, we see that $4k, 4k+1, 4k+2, 4k+3, 4k+4$ is a sequence of five consecutive QNRs. Then we get ever-longer sequences like this by iterating the argument. But once we get a sequence longer than $p$, we get a contradiction.
answered Jan 13 at 3:21
Misha LavrovMisha Lavrov
49.6k759109
$endgroup$
Here is a solution in two steps.
First, we prove that when there is no such $a$, 2 is a QR. This is a bunch of casework, and doesn't work for some small primes. (Specifically for $p=2, 3, 5, 7, 11, 13$.) We can check those separately, and find all three counterexamples that way.
Suppose that 2 is a QNR. Therefore 8 is a QNR, 32 is a QNR, 18 is a QNR.
40 must be a QR or else we find the sequence 32, 36, 40. Therefore 20 is a QNR.
12 must be a QR or else we find the sequence 12, 16, 20. Therefore 24 is a QNR, 48 is a QR, 96 is a QNR.
104 must be a QR or else we find the sequence 96, 100, 104. Therefore 52 is a QNR.
28 must be a QNR or else we find the sequence 24, 28, 32. Therefore 14 is a QR.
22 must be a QR or else we find the sequence 14, 18, 22. Therefore 44 is a QNR.
Now we find the sequence 44, 48, 52.
Second, assuming that $2$ is a QR and there are no cases of $a$ such that $a^2-4$, $a^2+4$ are QNR, we arrive at a contradiction.
If any three consecutive integers $k, k+1, k+2$ follow the pattern QNR, QR, QNR, then the same is true for $4k, 4k+4, 4k+8$ and we are done. So adjacent to any QR is another QR.
If this is true, but no two consecutive integers are ever QNR, then we're also in trouble, because then at least approximately $frac23$ of the residues mod $p$ are QR.
Suppose that $k, k+1$ are both QNR for some $k$. Then $8k, 8k+8$ are both QNR, so $8k+4$ must be QNR or else $8k, 8k+4, 8k+8$ is the sequence we want. (Note that $8k+4 notequiv 0 pmod p$ because then $8k+8$ could not be QNR.) Therefore $2k, 2k+1, 2k+2$ is a sequence of three consecutive QNRs.
Applying this argument again, we see that $4k, 4k+1, 4k+2, 4k+3, 4k+4$ is a sequence of five consecutive QNRs. Then we get ever-longer sequences like this by iterating the argument. But once we get a sequence longer than $p$, we get a contradiction.
answered Jan 13 at 3:21
Misha LavrovMisha Lavrov
49.6k759109
edited Jan 13 at 3:39
answered Jan 13 at 3:21
Misha LavrovMisha Lavrov
49.6k759109
answered Jan 13 at 3:21
Misha LavrovMisha Lavrov
49.6k759109
answered Jan 13 at 3:21
Misha LavrovMisha Lavrov
49.6k759109
49.6k759109
$begingroup$
This is quite complex argumentation, but I like it because all steps are elementary.
$endgroup$
– René Gy
Jan 13 at 9:15
add a comment |
$begingroup$
This is quite complex argumentation, but I like it because all steps are elementary.
$endgroup$
– René Gy
Jan 13 at 9:15
$begingroup$
This is quite complex argumentation, but I like it because all steps are elementary.
$endgroup$
– René Gy
Jan 13 at 9:15
$begingroup$
This is quite complex argumentation, but I like it because all steps are elementary.
$endgroup$
– René Gy
Jan 13 at 9:15
add a comment |
$begingroup$
seems believable
jagy@phobeusjunior:~$ ./mse
p 3 fails p 5 fails p 7 a: 3 p 11 a: 5 p 13 fails
p 17 a: 1 p 19 a: 5 p 23 a: 1 p 29 a: 6 p 31 a: 5
p 37 a: 3 p 41 a: 8 p 43 a: 4 p 47 a: 1 p 53 a: 1
p 59 a: 6 p 61 a: 5 p 67 a: 3 p 71 a: 13 p 73 a: 3
p 79 a: 8 p 83 a: 1 p 89 a: 10 p 97 a: 3 p 101 a: 6
p 103 a: 4 p 107 a: 1 p 109 a: 6 p 113 a: 1 p 127 a: 4
p 131 a: 6 p 137 a: 1 p 139 a: 6 p 149 a: 6 p 151 a: 10
p 157 a: 5 p 163 a: 3 p 167 a: 1 p 173 a: 1 p 179 a: 6
p 181 a: 6 p 191 a: 5 p 193 a: 3 p 197 a: 1 p 199 a: 8
p 211 a: 6 p 223 a: 3 p 227 a: 1 p 229 a: 5 p 233 a: 1
p 239 a: 12 p 241 a: 12 p 251 a: 6 p 257 a: 1 p 263 a: 1
p 269 a: 6 p 271 a: 5 p 277 a: 7 p 281 a: 10 p 283 a: 4
p 293 a: 1 p 307 a: 3 p 311 a: 9 p 313 a: 7 p 317 a: 1
p 331 a: 6 p 337 a: 7 p 347 a: 1 p 349 a: 6 p 353 a: 1
p 359 a: 5 p 367 a: 4 p 373 a: 7 p 379 a: 6 p 383 a: 1
p 389 a: 5 p 397 a: 3 p 401 a: 8 p 409 a: 5 p 419 a: 6
p 421 a: 6 p 431 a: 9 p 433 a: 5 p 439 a: 8 p 443 a: 1
p 449 a: 5 p 457 a: 3 p 461 a: 6 p 463 a: 3 p 467 a: 1
p 479 a: 24 p 487 a: 3 p 491 a: 5 p 499 a: 6 p 503 a: 1
p 509 a: 6 p 521 a: 8 p 523 a: 4 p 541 a: 6 p 547 a: 4
p 557 a: 1 p 563 a: 1 p 569 a: 5 p 571 a: 6 p 577 a: 3
p 587 a: 1 p 593 a: 1 p 599 a: 5 p 601 a: 5 p 607 a: 4
p 613 a: 3 p 617 a: 1 p 619 a: 5 p 631 a: 10 p 641 a: 5
p 643 a: 3 p 647 a: 1 p 653 a: 1 p 659 a: 5 p 661 a: 6
p 673 a: 8 p 677 a: 1 p 683 a: 1 p 691 a: 6 p 701 a: 6
p 709 a: 6 p 719 a: 9 p 727 a: 4 p 733 a: 3 p 739 a: 6
p 743 a: 1 p 751 a: 8 p 757 a: 10 p 761 a: 10 p 769 a: 5
p 773 a: 1 p 787 a: 3 p 797 a: 1 p 809 a: 5 p 811 a: 6
p 821 a: 6 p 823 a: 4 p 827 a: 1 p 829 a: 5 p 839 a: 9
p 853 a: 3 p 857 a: 1 p 859 a: 5 p 863 a: 1 p 877 a: 3
p 881 a: 8 p 883 a: 4 p 887 a: 1 p 907 a: 4 p 911 a: 5
p 919 a: 12 p 929 a: 8 p 937 a: 16 p 941 a: 6 p 947 a: 1
p 953 a: 1 p 967 a: 3 p 971 a: 6 p 977 a: 1 p 983 a: 1
p 991 a: 8 p 997 a: 5 p 1009 a: 9 p 1013 a: 1 p 1019 a: 6
p 1021 a: 6 p 1031 a: 9 p 1033 a: 3 p 1039 a: 19 p 1049 a: 8
answered Jan 13 at 1:54
Will JagyWill Jagy
104k5103202
$endgroup$
add a comment |
$begingroup$
seems believable
jagy@phobeusjunior:~$ ./mse
p 3 fails p 5 fails p 7 a: 3 p 11 a: 5 p 13 fails
p 17 a: 1 p 19 a: 5 p 23 a: 1 p 29 a: 6 p 31 a: 5
p 37 a: 3 p 41 a: 8 p 43 a: 4 p 47 a: 1 p 53 a: 1
p 59 a: 6 p 61 a: 5 p 67 a: 3 p 71 a: 13 p 73 a: 3
p 79 a: 8 p 83 a: 1 p 89 a: 10 p 97 a: 3 p 101 a: 6
p 103 a: 4 p 107 a: 1 p 109 a: 6 p 113 a: 1 p 127 a: 4
p 131 a: 6 p 137 a: 1 p 139 a: 6 p 149 a: 6 p 151 a: 10
p 157 a: 5 p 163 a: 3 p 167 a: 1 p 173 a: 1 p 179 a: 6
p 181 a: 6 p 191 a: 5 p 193 a: 3 p 197 a: 1 p 199 a: 8
p 211 a: 6 p 223 a: 3 p 227 a: 1 p 229 a: 5 p 233 a: 1
p 239 a: 12 p 241 a: 12 p 251 a: 6 p 257 a: 1 p 263 a: 1
p 269 a: 6 p 271 a: 5 p 277 a: 7 p 281 a: 10 p 283 a: 4
p 293 a: 1 p 307 a: 3 p 311 a: 9 p 313 a: 7 p 317 a: 1
p 331 a: 6 p 337 a: 7 p 347 a: 1 p 349 a: 6 p 353 a: 1
p 359 a: 5 p 367 a: 4 p 373 a: 7 p 379 a: 6 p 383 a: 1
p 389 a: 5 p 397 a: 3 p 401 a: 8 p 409 a: 5 p 419 a: 6
p 421 a: 6 p 431 a: 9 p 433 a: 5 p 439 a: 8 p 443 a: 1
p 449 a: 5 p 457 a: 3 p 461 a: 6 p 463 a: 3 p 467 a: 1
p 479 a: 24 p 487 a: 3 p 491 a: 5 p 499 a: 6 p 503 a: 1
p 509 a: 6 p 521 a: 8 p 523 a: 4 p 541 a: 6 p 547 a: 4
p 557 a: 1 p 563 a: 1 p 569 a: 5 p 571 a: 6 p 577 a: 3
p 587 a: 1 p 593 a: 1 p 599 a: 5 p 601 a: 5 p 607 a: 4
p 613 a: 3 p 617 a: 1 p 619 a: 5 p 631 a: 10 p 641 a: 5
p 643 a: 3 p 647 a: 1 p 653 a: 1 p 659 a: 5 p 661 a: 6
p 673 a: 8 p 677 a: 1 p 683 a: 1 p 691 a: 6 p 701 a: 6
p 709 a: 6 p 719 a: 9 p 727 a: 4 p 733 a: 3 p 739 a: 6
p 743 a: 1 p 751 a: 8 p 757 a: 10 p 761 a: 10 p 769 a: 5
p 773 a: 1 p 787 a: 3 p 797 a: 1 p 809 a: 5 p 811 a: 6
p 821 a: 6 p 823 a: 4 p 827 a: 1 p 829 a: 5 p 839 a: 9
p 853 a: 3 p 857 a: 1 p 859 a: 5 p 863 a: 1 p 877 a: 3
p 881 a: 8 p 883 a: 4 p 887 a: 1 p 907 a: 4 p 911 a: 5
p 919 a: 12 p 929 a: 8 p 937 a: 16 p 941 a: 6 p 947 a: 1
p 953 a: 1 p 967 a: 3 p 971 a: 6 p 977 a: 1 p 983 a: 1
p 991 a: 8 p 997 a: 5 p 1009 a: 9 p 1013 a: 1 p 1019 a: 6
p 1021 a: 6 p 1031 a: 9 p 1033 a: 3 p 1039 a: 19 p 1049 a: 8
answered Jan 13 at 1:54
Will JagyWill Jagy
104k5103202
$endgroup$
add a comment |
$begingroup$
seems believable
jagy@phobeusjunior:~$ ./mse
p 3 fails p 5 fails p 7 a: 3 p 11 a: 5 p 13 fails
p 17 a: 1 p 19 a: 5 p 23 a: 1 p 29 a: 6 p 31 a: 5
p 37 a: 3 p 41 a: 8 p 43 a: 4 p 47 a: 1 p 53 a: 1
p 59 a: 6 p 61 a: 5 p 67 a: 3 p 71 a: 13 p 73 a: 3
p 79 a: 8 p 83 a: 1 p 89 a: 10 p 97 a: 3 p 101 a: 6
p 103 a: 4 p 107 a: 1 p 109 a: 6 p 113 a: 1 p 127 a: 4
p 131 a: 6 p 137 a: 1 p 139 a: 6 p 149 a: 6 p 151 a: 10
p 157 a: 5 p 163 a: 3 p 167 a: 1 p 173 a: 1 p 179 a: 6
p 181 a: 6 p 191 a: 5 p 193 a: 3 p 197 a: 1 p 199 a: 8
p 211 a: 6 p 223 a: 3 p 227 a: 1 p 229 a: 5 p 233 a: 1
p 239 a: 12 p 241 a: 12 p 251 a: 6 p 257 a: 1 p 263 a: 1
p 269 a: 6 p 271 a: 5 p 277 a: 7 p 281 a: 10 p 283 a: 4
p 293 a: 1 p 307 a: 3 p 311 a: 9 p 313 a: 7 p 317 a: 1
p 331 a: 6 p 337 a: 7 p 347 a: 1 p 349 a: 6 p 353 a: 1
p 359 a: 5 p 367 a: 4 p 373 a: 7 p 379 a: 6 p 383 a: 1
p 389 a: 5 p 397 a: 3 p 401 a: 8 p 409 a: 5 p 419 a: 6
p 421 a: 6 p 431 a: 9 p 433 a: 5 p 439 a: 8 p 443 a: 1
p 449 a: 5 p 457 a: 3 p 461 a: 6 p 463 a: 3 p 467 a: 1
p 479 a: 24 p 487 a: 3 p 491 a: 5 p 499 a: 6 p 503 a: 1
p 509 a: 6 p 521 a: 8 p 523 a: 4 p 541 a: 6 p 547 a: 4
p 557 a: 1 p 563 a: 1 p 569 a: 5 p 571 a: 6 p 577 a: 3
p 587 a: 1 p 593 a: 1 p 599 a: 5 p 601 a: 5 p 607 a: 4
p 613 a: 3 p 617 a: 1 p 619 a: 5 p 631 a: 10 p 641 a: 5
p 643 a: 3 p 647 a: 1 p 653 a: 1 p 659 a: 5 p 661 a: 6
p 673 a: 8 p 677 a: 1 p 683 a: 1 p 691 a: 6 p 701 a: 6
p 709 a: 6 p 719 a: 9 p 727 a: 4 p 733 a: 3 p 739 a: 6
p 743 a: 1 p 751 a: 8 p 757 a: 10 p 761 a: 10 p 769 a: 5
p 773 a: 1 p 787 a: 3 p 797 a: 1 p 809 a: 5 p 811 a: 6
p 821 a: 6 p 823 a: 4 p 827 a: 1 p 829 a: 5 p 839 a: 9
p 853 a: 3 p 857 a: 1 p 859 a: 5 p 863 a: 1 p 877 a: 3
p 881 a: 8 p 883 a: 4 p 887 a: 1 p 907 a: 4 p 911 a: 5
p 919 a: 12 p 929 a: 8 p 937 a: 16 p 941 a: 6 p 947 a: 1
p 953 a: 1 p 967 a: 3 p 971 a: 6 p 977 a: 1 p 983 a: 1
p 991 a: 8 p 997 a: 5 p 1009 a: 9 p 1013 a: 1 p 1019 a: 6
p 1021 a: 6 p 1031 a: 9 p 1033 a: 3 p 1039 a: 19 p 1049 a: 8
answered Jan 13 at 1:54
Will JagyWill Jagy
104k5103202
$endgroup$
seems believable
jagy@phobeusjunior:~$ ./mse
p 3 fails p 5 fails p 7 a: 3 p 11 a: 5 p 13 fails
p 17 a: 1 p 19 a: 5 p 23 a: 1 p 29 a: 6 p 31 a: 5
p 37 a: 3 p 41 a: 8 p 43 a: 4 p 47 a: 1 p 53 a: 1
p 59 a: 6 p 61 a: 5 p 67 a: 3 p 71 a: 13 p 73 a: 3
p 79 a: 8 p 83 a: 1 p 89 a: 10 p 97 a: 3 p 101 a: 6
p 103 a: 4 p 107 a: 1 p 109 a: 6 p 113 a: 1 p 127 a: 4
p 131 a: 6 p 137 a: 1 p 139 a: 6 p 149 a: 6 p 151 a: 10
p 157 a: 5 p 163 a: 3 p 167 a: 1 p 173 a: 1 p 179 a: 6
p 181 a: 6 p 191 a: 5 p 193 a: 3 p 197 a: 1 p 199 a: 8
p 211 a: 6 p 223 a: 3 p 227 a: 1 p 229 a: 5 p 233 a: 1
p 239 a: 12 p 241 a: 12 p 251 a: 6 p 257 a: 1 p 263 a: 1
p 269 a: 6 p 271 a: 5 p 277 a: 7 p 281 a: 10 p 283 a: 4
p 293 a: 1 p 307 a: 3 p 311 a: 9 p 313 a: 7 p 317 a: 1
p 331 a: 6 p 337 a: 7 p 347 a: 1 p 349 a: 6 p 353 a: 1
p 359 a: 5 p 367 a: 4 p 373 a: 7 p 379 a: 6 p 383 a: 1
p 389 a: 5 p 397 a: 3 p 401 a: 8 p 409 a: 5 p 419 a: 6
p 421 a: 6 p 431 a: 9 p 433 a: 5 p 439 a: 8 p 443 a: 1
p 449 a: 5 p 457 a: 3 p 461 a: 6 p 463 a: 3 p 467 a: 1
p 479 a: 24 p 487 a: 3 p 491 a: 5 p 499 a: 6 p 503 a: 1
p 509 a: 6 p 521 a: 8 p 523 a: 4 p 541 a: 6 p 547 a: 4
p 557 a: 1 p 563 a: 1 p 569 a: 5 p 571 a: 6 p 577 a: 3
p 587 a: 1 p 593 a: 1 p 599 a: 5 p 601 a: 5 p 607 a: 4
p 613 a: 3 p 617 a: 1 p 619 a: 5 p 631 a: 10 p 641 a: 5
p 643 a: 3 p 647 a: 1 p 653 a: 1 p 659 a: 5 p 661 a: 6
p 673 a: 8 p 677 a: 1 p 683 a: 1 p 691 a: 6 p 701 a: 6
p 709 a: 6 p 719 a: 9 p 727 a: 4 p 733 a: 3 p 739 a: 6
p 743 a: 1 p 751 a: 8 p 757 a: 10 p 761 a: 10 p 769 a: 5
p 773 a: 1 p 787 a: 3 p 797 a: 1 p 809 a: 5 p 811 a: 6
p 821 a: 6 p 823 a: 4 p 827 a: 1 p 829 a: 5 p 839 a: 9
p 853 a: 3 p 857 a: 1 p 859 a: 5 p 863 a: 1 p 877 a: 3
p 881 a: 8 p 883 a: 4 p 887 a: 1 p 907 a: 4 p 911 a: 5
p 919 a: 12 p 929 a: 8 p 937 a: 16 p 941 a: 6 p 947 a: 1
p 953 a: 1 p 967 a: 3 p 971 a: 6 p 977 a: 1 p 983 a: 1
p 991 a: 8 p 997 a: 5 p 1009 a: 9 p 1013 a: 1 p 1019 a: 6
p 1021 a: 6 p 1031 a: 9 p 1033 a: 3 p 1039 a: 19 p 1049 a: 8
answered Jan 13 at 1:54
Will JagyWill Jagy
104k5103202
answered Jan 13 at 1:54
Will JagyWill Jagy
104k5103202
answered Jan 13 at 1:54
Will JagyWill Jagy
104k5103202
answered Jan 13 at 1:54
Will JagyWill Jagy
104k5103202
104k5103202
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%2f3071602%2fis-there-always-a-positive-integer-a-such-that-both-a2-4-and-a24-are-qu%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
4
$begingroup$
If you have three consecutive numbers that are non-residue, residue, non-residue, then multiplying by four gives you $a^2pm4$ both nonresidues. The standard way to tackle this sort ofmproblem is via exponential sums.
$endgroup$
– Gerry Myerson
Jan 13 at 1:54
$begingroup$
@Gerry Myerson Thanks, this comment is key in Misha Lavrov's solution.
$endgroup$
– René Gy
Jan 13 at 9:20