What primes $p$ give solutions to $x^{2} equiv 7 ($mod $ p)$
$begingroup$
I'm trying to understand how to solve this using the Legendre symbol but am having a hard time figuring out exactly what to do.
There are many different cases to consider but I do not know how to approach this problem.
number-theory quadratic-residues
edited Nov 28 '18 at 1:08
Henning Makholm
239k17304541
asked Nov 28 '18 at 0:38
WallaceWallace
1297
$endgroup$
add a comment |
$begingroup$
I'm trying to understand how to solve this using the Legendre symbol but am having a hard time figuring out exactly what to do.
There are many different cases to consider but I do not know how to approach this problem.
number-theory quadratic-residues
edited Nov 28 '18 at 1:08
Henning Makholm
239k17304541
asked Nov 28 '18 at 0:38
WallaceWallace
1297
$endgroup$
$begingroup$
What are you stuck on? Do you know what the Legendre symbol actually is?
$endgroup$
– anomaly
Nov 28 '18 at 0:58
$begingroup$
It tells us whether we have a quadratic or non quadratic residue. I'm just not too familiar with computing it
$endgroup$
– Wallace
Nov 28 '18 at 1:01
add a comment |
$begingroup$
I'm trying to understand how to solve this using the Legendre symbol but am having a hard time figuring out exactly what to do.
There are many different cases to consider but I do not know how to approach this problem.
number-theory quadratic-residues
edited Nov 28 '18 at 1:08
Henning Makholm
239k17304541
asked Nov 28 '18 at 0:38
WallaceWallace
1297
$endgroup$
I'm trying to understand how to solve this using the Legendre symbol but am having a hard time figuring out exactly what to do.
There are many different cases to consider but I do not know how to approach this problem.
number-theory quadratic-residues
number-theory quadratic-residues
edited Nov 28 '18 at 1:08
Henning Makholm
239k17304541
asked Nov 28 '18 at 0:38
WallaceWallace
1297
edited Nov 28 '18 at 1:08
Henning Makholm
239k17304541
asked Nov 28 '18 at 0:38
WallaceWallace
1297
edited Nov 28 '18 at 1:08
Henning Makholm
239k17304541
edited Nov 28 '18 at 1:08
Henning Makholm
239k17304541
edited Nov 28 '18 at 1:08
Henning Makholm
239k17304541
239k17304541
asked Nov 28 '18 at 0:38
WallaceWallace
1297
asked Nov 28 '18 at 0:38
WallaceWallace
1297
asked Nov 28 '18 at 0:38
WallaceWallace
1297
1297
$begingroup$
What are you stuck on? Do you know what the Legendre symbol actually is?
$endgroup$
– anomaly
Nov 28 '18 at 0:58
$begingroup$
It tells us whether we have a quadratic or non quadratic residue. I'm just not too familiar with computing it
$endgroup$
– Wallace
Nov 28 '18 at 1:01
add a comment |
$begingroup$
What are you stuck on? Do you know what the Legendre symbol actually is?
$endgroup$
– anomaly
Nov 28 '18 at 0:58
$begingroup$
It tells us whether we have a quadratic or non quadratic residue. I'm just not too familiar with computing it
$endgroup$
– Wallace
Nov 28 '18 at 1:01
$begingroup$
What are you stuck on? Do you know what the Legendre symbol actually is?
$endgroup$
– anomaly
Nov 28 '18 at 0:58
$begingroup$
What are you stuck on? Do you know what the Legendre symbol actually is?
$endgroup$
– anomaly
Nov 28 '18 at 0:58
$begingroup$
It tells us whether we have a quadratic or non quadratic residue. I'm just not too familiar with computing it
$endgroup$
– Wallace
Nov 28 '18 at 1:01
$begingroup$
It tells us whether we have a quadratic or non quadratic residue. I'm just not too familiar with computing it
$endgroup$
– Wallace
Nov 28 '18 at 1:01
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Another hint:
An odd prime is congruent to $1$ or $3mod 4$. Also, the non-zero squares modulo $7$ are $;1,,2$ and $4$. So
- If $pequiv 1mod 4$, $(-1)^{tfrac{p-1}2}=1$, and $p$ has to be a square modulo $7$, i.e. $pequiv 1,2,4$.
- If $pequiv 3mod 4$, $p$ has to be a non-square modulo $7$, i.e. $pequiv3,5,6$
Now use the Chinese remainder theorem:
$$mathbf Z/4mathbf Ztimes mathbf Z/7mathbf Zsimeqmathbf Z/28mathbf Z$$
to find the images of the pairs ${(1,1),,(1,2),,(1,4),,(3,3),,(3,5),,(3,6)}$ modulo $28$.
answered Nov 28 '18 at 1:06
BernardBernard
119k740113
$endgroup$
add a comment |
$begingroup$
Hint: If $p$ is an odd prime not equal to $7$ ($p=2$ works, $p=7$ does not), we have by quadratic reciprocity that
$$left(frac{p}{7}right)left(frac{7}{p}right)=(-1)^{frac{6(p-1)}{4}}=(-1)^{frac{p-1}{2}},$$
so we need
$$left(frac{p}{7}right)=(-1)^{frac{p-1}{2}}.$$
Now look at each residue for $pbmod 7$ and determine what residue $pbmod 4$ must be.
answered Nov 28 '18 at 0:51
Carl SchildkrautCarl Schildkraut
11.3k11441
$endgroup$
add a comment |
$begingroup$
If either $p$ or $-p$ has an integer expression as $u^2 - 7 v^2,$ it follows that there is a solution to $$ u^2 equiv 7 v^2 pmod p ; . ; $$
Which, you know, means something.
2 29 37 53 109 113 137 149 193 197
233 277 281 317 337 373 389 401 421 449
457 541 557 569 613 617 641 653 673 701
709 757 809 821 877 953 977 1009 1033 1061
3 7 19 31 47 59 83 103 131 139
167 199 223 227 251 271 283 307 311 367
383 419 439 467 479 503 523 563 587 607
619 643 647 691 719 727 787 811 839 859
887 971 983 1039 1063 1091 1123 1151 1223 1231
answered Nov 28 '18 at 2:28
Will JagyWill Jagy
103k5101200
$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%2f3016533%2fwhat-primes-p-give-solutions-to-x2-equiv-7-mod-p%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Another hint:
An odd prime is congruent to $1$ or $3mod 4$. Also, the non-zero squares modulo $7$ are $;1,,2$ and $4$. So
- If $pequiv 1mod 4$, $(-1)^{tfrac{p-1}2}=1$, and $p$ has to be a square modulo $7$, i.e. $pequiv 1,2,4$.
- If $pequiv 3mod 4$, $p$ has to be a non-square modulo $7$, i.e. $pequiv3,5,6$
Now use the Chinese remainder theorem:
$$mathbf Z/4mathbf Ztimes mathbf Z/7mathbf Zsimeqmathbf Z/28mathbf Z$$
to find the images of the pairs ${(1,1),,(1,2),,(1,4),,(3,3),,(3,5),,(3,6)}$ modulo $28$.
answered Nov 28 '18 at 1:06
BernardBernard
119k740113
$endgroup$
add a comment |
$begingroup$
Another hint:
An odd prime is congruent to $1$ or $3mod 4$. Also, the non-zero squares modulo $7$ are $;1,,2$ and $4$. So
- If $pequiv 1mod 4$, $(-1)^{tfrac{p-1}2}=1$, and $p$ has to be a square modulo $7$, i.e. $pequiv 1,2,4$.
- If $pequiv 3mod 4$, $p$ has to be a non-square modulo $7$, i.e. $pequiv3,5,6$
Now use the Chinese remainder theorem:
$$mathbf Z/4mathbf Ztimes mathbf Z/7mathbf Zsimeqmathbf Z/28mathbf Z$$
to find the images of the pairs ${(1,1),,(1,2),,(1,4),,(3,3),,(3,5),,(3,6)}$ modulo $28$.
answered Nov 28 '18 at 1:06
BernardBernard
119k740113
$endgroup$
add a comment |
$begingroup$
Another hint:
An odd prime is congruent to $1$ or $3mod 4$. Also, the non-zero squares modulo $7$ are $;1,,2$ and $4$. So
- If $pequiv 1mod 4$, $(-1)^{tfrac{p-1}2}=1$, and $p$ has to be a square modulo $7$, i.e. $pequiv 1,2,4$.
- If $pequiv 3mod 4$, $p$ has to be a non-square modulo $7$, i.e. $pequiv3,5,6$
Now use the Chinese remainder theorem:
$$mathbf Z/4mathbf Ztimes mathbf Z/7mathbf Zsimeqmathbf Z/28mathbf Z$$
to find the images of the pairs ${(1,1),,(1,2),,(1,4),,(3,3),,(3,5),,(3,6)}$ modulo $28$.
answered Nov 28 '18 at 1:06
BernardBernard
119k740113
$endgroup$
Another hint:
An odd prime is congruent to $1$ or $3mod 4$. Also, the non-zero squares modulo $7$ are $;1,,2$ and $4$. So
- If $pequiv 1mod 4$, $(-1)^{tfrac{p-1}2}=1$, and $p$ has to be a square modulo $7$, i.e. $pequiv 1,2,4$.
- If $pequiv 3mod 4$, $p$ has to be a non-square modulo $7$, i.e. $pequiv3,5,6$
Now use the Chinese remainder theorem:
$$mathbf Z/4mathbf Ztimes mathbf Z/7mathbf Zsimeqmathbf Z/28mathbf Z$$
to find the images of the pairs ${(1,1),,(1,2),,(1,4),,(3,3),,(3,5),,(3,6)}$ modulo $28$.
answered Nov 28 '18 at 1:06
BernardBernard
119k740113
edited Nov 28 '18 at 9:25
answered Nov 28 '18 at 1:06
BernardBernard
119k740113
answered Nov 28 '18 at 1:06
BernardBernard
119k740113
answered Nov 28 '18 at 1:06
BernardBernard
119k740113
119k740113
add a comment |
add a comment |
$begingroup$
Hint: If $p$ is an odd prime not equal to $7$ ($p=2$ works, $p=7$ does not), we have by quadratic reciprocity that
$$left(frac{p}{7}right)left(frac{7}{p}right)=(-1)^{frac{6(p-1)}{4}}=(-1)^{frac{p-1}{2}},$$
so we need
$$left(frac{p}{7}right)=(-1)^{frac{p-1}{2}}.$$
Now look at each residue for $pbmod 7$ and determine what residue $pbmod 4$ must be.
answered Nov 28 '18 at 0:51
Carl SchildkrautCarl Schildkraut
11.3k11441
$endgroup$
add a comment |
$begingroup$
Hint: If $p$ is an odd prime not equal to $7$ ($p=2$ works, $p=7$ does not), we have by quadratic reciprocity that
$$left(frac{p}{7}right)left(frac{7}{p}right)=(-1)^{frac{6(p-1)}{4}}=(-1)^{frac{p-1}{2}},$$
so we need
$$left(frac{p}{7}right)=(-1)^{frac{p-1}{2}}.$$
Now look at each residue for $pbmod 7$ and determine what residue $pbmod 4$ must be.
answered Nov 28 '18 at 0:51
Carl SchildkrautCarl Schildkraut
11.3k11441
$endgroup$
add a comment |
$begingroup$
Hint: If $p$ is an odd prime not equal to $7$ ($p=2$ works, $p=7$ does not), we have by quadratic reciprocity that
$$left(frac{p}{7}right)left(frac{7}{p}right)=(-1)^{frac{6(p-1)}{4}}=(-1)^{frac{p-1}{2}},$$
so we need
$$left(frac{p}{7}right)=(-1)^{frac{p-1}{2}}.$$
Now look at each residue for $pbmod 7$ and determine what residue $pbmod 4$ must be.
answered Nov 28 '18 at 0:51
Carl SchildkrautCarl Schildkraut
11.3k11441
$endgroup$
Hint: If $p$ is an odd prime not equal to $7$ ($p=2$ works, $p=7$ does not), we have by quadratic reciprocity that
$$left(frac{p}{7}right)left(frac{7}{p}right)=(-1)^{frac{6(p-1)}{4}}=(-1)^{frac{p-1}{2}},$$
so we need
$$left(frac{p}{7}right)=(-1)^{frac{p-1}{2}}.$$
Now look at each residue for $pbmod 7$ and determine what residue $pbmod 4$ must be.
answered Nov 28 '18 at 0:51
Carl SchildkrautCarl Schildkraut
11.3k11441
answered Nov 28 '18 at 0:51
Carl SchildkrautCarl Schildkraut
11.3k11441
answered Nov 28 '18 at 0:51
Carl SchildkrautCarl Schildkraut
11.3k11441
answered Nov 28 '18 at 0:51
Carl SchildkrautCarl Schildkraut
11.3k11441
11.3k11441
add a comment |
add a comment |
$begingroup$
If either $p$ or $-p$ has an integer expression as $u^2 - 7 v^2,$ it follows that there is a solution to $$ u^2 equiv 7 v^2 pmod p ; . ; $$
Which, you know, means something.
2 29 37 53 109 113 137 149 193 197
233 277 281 317 337 373 389 401 421 449
457 541 557 569 613 617 641 653 673 701
709 757 809 821 877 953 977 1009 1033 1061
3 7 19 31 47 59 83 103 131 139
167 199 223 227 251 271 283 307 311 367
383 419 439 467 479 503 523 563 587 607
619 643 647 691 719 727 787 811 839 859
887 971 983 1039 1063 1091 1123 1151 1223 1231
answered Nov 28 '18 at 2:28
Will JagyWill Jagy
103k5101200
$endgroup$
add a comment |
$begingroup$
If either $p$ or $-p$ has an integer expression as $u^2 - 7 v^2,$ it follows that there is a solution to $$ u^2 equiv 7 v^2 pmod p ; . ; $$
Which, you know, means something.
2 29 37 53 109 113 137 149 193 197
233 277 281 317 337 373 389 401 421 449
457 541 557 569 613 617 641 653 673 701
709 757 809 821 877 953 977 1009 1033 1061
3 7 19 31 47 59 83 103 131 139
167 199 223 227 251 271 283 307 311 367
383 419 439 467 479 503 523 563 587 607
619 643 647 691 719 727 787 811 839 859
887 971 983 1039 1063 1091 1123 1151 1223 1231
answered Nov 28 '18 at 2:28
Will JagyWill Jagy
103k5101200
$endgroup$
add a comment |
$begingroup$
If either $p$ or $-p$ has an integer expression as $u^2 - 7 v^2,$ it follows that there is a solution to $$ u^2 equiv 7 v^2 pmod p ; . ; $$
Which, you know, means something.
2 29 37 53 109 113 137 149 193 197
233 277 281 317 337 373 389 401 421 449
457 541 557 569 613 617 641 653 673 701
709 757 809 821 877 953 977 1009 1033 1061
3 7 19 31 47 59 83 103 131 139
167 199 223 227 251 271 283 307 311 367
383 419 439 467 479 503 523 563 587 607
619 643 647 691 719 727 787 811 839 859
887 971 983 1039 1063 1091 1123 1151 1223 1231
answered Nov 28 '18 at 2:28
Will JagyWill Jagy
103k5101200
$endgroup$
If either $p$ or $-p$ has an integer expression as $u^2 - 7 v^2,$ it follows that there is a solution to $$ u^2 equiv 7 v^2 pmod p ; . ; $$
Which, you know, means something.
2 29 37 53 109 113 137 149 193 197
233 277 281 317 337 373 389 401 421 449
457 541 557 569 613 617 641 653 673 701
709 757 809 821 877 953 977 1009 1033 1061
3 7 19 31 47 59 83 103 131 139
167 199 223 227 251 271 283 307 311 367
383 419 439 467 479 503 523 563 587 607
619 643 647 691 719 727 787 811 839 859
887 971 983 1039 1063 1091 1123 1151 1223 1231
answered Nov 28 '18 at 2:28
Will JagyWill Jagy
103k5101200
answered Nov 28 '18 at 2:28
Will JagyWill Jagy
103k5101200
answered Nov 28 '18 at 2:28
Will JagyWill Jagy
103k5101200
answered Nov 28 '18 at 2:28
Will JagyWill Jagy
103k5101200
103k5101200
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%2f3016533%2fwhat-primes-p-give-solutions-to-x2-equiv-7-mod-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
$begingroup$
What are you stuck on? Do you know what the Legendre symbol actually is?
$endgroup$
– anomaly
Nov 28 '18 at 0:58
$begingroup$
It tells us whether we have a quadratic or non quadratic residue. I'm just not too familiar with computing it
$endgroup$
– Wallace
Nov 28 '18 at 1:01