What are the Legendre symbols $left(frac{10}{31}right)$ and $left(frac{-15}{43}right)$?
$begingroup$
I have the following two Legendre symbols that need calculated:
$left(frac{10}{31}right)$ $=$ $-left(frac{31}{10}right)$ $=$ $-left(frac{1}{10}right)$ $=$ $-(-1)$ $=$ $-1$
$left(frac{-15}{43}right)$ $=$ $left(frac{43}{15}right)$ $=$ $left(frac{13}{15}right)$ $=$ $-1$
is that correct?
I just want to make sure I am understanding this concept.
number-theory elementary-number-theory proof-verification legendre-symbol quadratic-reciprocity
$endgroup$
add a comment |
$begingroup$
I have the following two Legendre symbols that need calculated:
$left(frac{10}{31}right)$ $=$ $-left(frac{31}{10}right)$ $=$ $-left(frac{1}{10}right)$ $=$ $-(-1)$ $=$ $-1$
$left(frac{-15}{43}right)$ $=$ $left(frac{43}{15}right)$ $=$ $left(frac{13}{15}right)$ $=$ $-1$
is that correct?
I just want to make sure I am understanding this concept.
number-theory elementary-number-theory proof-verification legendre-symbol quadratic-reciprocity
$endgroup$
3
$begingroup$
If you are using the Legendre symbol (and not the Jacobi symbol), then the denominators are supposed to be prime. Clearly, $10$ and $15$ are not prime, and the quadratic reciprocity law you are using is highly dubious since it works only with odd integers.
$endgroup$
– Batominovski
Dec 6 '18 at 22:35
$begingroup$
@Batominovski ohh I did not know! Thank you so much for the comment
$endgroup$
– Hidaw
Dec 6 '18 at 22:37
$begingroup$
And please use a more descriptive title the next time.
$endgroup$
– Batominovski
Dec 6 '18 at 22:37
2
$begingroup$
Even with Jacobi symbols (as an intermediate step in the calculation) you need to treat factors of 2 on the top specially.
$endgroup$
– Daniel Schepler
Dec 6 '18 at 22:45
add a comment |
$begingroup$
I have the following two Legendre symbols that need calculated:
$left(frac{10}{31}right)$ $=$ $-left(frac{31}{10}right)$ $=$ $-left(frac{1}{10}right)$ $=$ $-(-1)$ $=$ $-1$
$left(frac{-15}{43}right)$ $=$ $left(frac{43}{15}right)$ $=$ $left(frac{13}{15}right)$ $=$ $-1$
is that correct?
I just want to make sure I am understanding this concept.
number-theory elementary-number-theory proof-verification legendre-symbol quadratic-reciprocity
$endgroup$
I have the following two Legendre symbols that need calculated:
$left(frac{10}{31}right)$ $=$ $-left(frac{31}{10}right)$ $=$ $-left(frac{1}{10}right)$ $=$ $-(-1)$ $=$ $-1$
$left(frac{-15}{43}right)$ $=$ $left(frac{43}{15}right)$ $=$ $left(frac{13}{15}right)$ $=$ $-1$
is that correct?
I just want to make sure I am understanding this concept.
number-theory elementary-number-theory proof-verification legendre-symbol quadratic-reciprocity
number-theory elementary-number-theory proof-verification legendre-symbol quadratic-reciprocity
edited Dec 7 '18 at 7:56
Batominovski
33k33293
33k33293
asked Dec 6 '18 at 22:32
HidawHidaw
509624
509624
3
$begingroup$
If you are using the Legendre symbol (and not the Jacobi symbol), then the denominators are supposed to be prime. Clearly, $10$ and $15$ are not prime, and the quadratic reciprocity law you are using is highly dubious since it works only with odd integers.
$endgroup$
– Batominovski
Dec 6 '18 at 22:35
$begingroup$
@Batominovski ohh I did not know! Thank you so much for the comment
$endgroup$
– Hidaw
Dec 6 '18 at 22:37
$begingroup$
And please use a more descriptive title the next time.
$endgroup$
– Batominovski
Dec 6 '18 at 22:37
2
$begingroup$
Even with Jacobi symbols (as an intermediate step in the calculation) you need to treat factors of 2 on the top specially.
$endgroup$
– Daniel Schepler
Dec 6 '18 at 22:45
add a comment |
3
$begingroup$
If you are using the Legendre symbol (and not the Jacobi symbol), then the denominators are supposed to be prime. Clearly, $10$ and $15$ are not prime, and the quadratic reciprocity law you are using is highly dubious since it works only with odd integers.
$endgroup$
– Batominovski
Dec 6 '18 at 22:35
$begingroup$
@Batominovski ohh I did not know! Thank you so much for the comment
$endgroup$
– Hidaw
Dec 6 '18 at 22:37
$begingroup$
And please use a more descriptive title the next time.
$endgroup$
– Batominovski
Dec 6 '18 at 22:37
2
$begingroup$
Even with Jacobi symbols (as an intermediate step in the calculation) you need to treat factors of 2 on the top specially.
$endgroup$
– Daniel Schepler
Dec 6 '18 at 22:45
3
3
$begingroup$
If you are using the Legendre symbol (and not the Jacobi symbol), then the denominators are supposed to be prime. Clearly, $10$ and $15$ are not prime, and the quadratic reciprocity law you are using is highly dubious since it works only with odd integers.
$endgroup$
– Batominovski
Dec 6 '18 at 22:35
$begingroup$
If you are using the Legendre symbol (and not the Jacobi symbol), then the denominators are supposed to be prime. Clearly, $10$ and $15$ are not prime, and the quadratic reciprocity law you are using is highly dubious since it works only with odd integers.
$endgroup$
– Batominovski
Dec 6 '18 at 22:35
$begingroup$
@Batominovski ohh I did not know! Thank you so much for the comment
$endgroup$
– Hidaw
Dec 6 '18 at 22:37
$begingroup$
@Batominovski ohh I did not know! Thank you so much for the comment
$endgroup$
– Hidaw
Dec 6 '18 at 22:37
$begingroup$
And please use a more descriptive title the next time.
$endgroup$
– Batominovski
Dec 6 '18 at 22:37
$begingroup$
And please use a more descriptive title the next time.
$endgroup$
– Batominovski
Dec 6 '18 at 22:37
2
2
$begingroup$
Even with Jacobi symbols (as an intermediate step in the calculation) you need to treat factors of 2 on the top specially.
$endgroup$
– Daniel Schepler
Dec 6 '18 at 22:45
$begingroup$
Even with Jacobi symbols (as an intermediate step in the calculation) you need to treat factors of 2 on the top specially.
$endgroup$
– Daniel Schepler
Dec 6 '18 at 22:45
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Here is an approach I would take. Note that
$$left(frac{10}{31}right)=left(frac{-21}{31}right)=left(frac{-1}{31}right)left(frac{3}{31}right)left(frac{7}{31}right)=(-1)Biggl(-left(frac{31}{3}right)Biggr)Biggl(-left(frac{31}{7}right)Biggr),.$$
That is, $$left(frac{10}{31}right)=-left(frac{1}{3}right)left(frac{3}{7}right)=-(+1)Biggl(-left(frac{7}{3}right)Biggr)=left(frac{1}{3}right)=+1,.$$ This can be verified by noting that $6^2equiv 5pmod{31}$ and $8^2equiv 2pmod{31}$, so $$17^2equiv (6cdot 8)^2equiv 5cdot2=10pmod{31},.$$
For the second part, note that
$$left(frac{-15}{43}right)=left(frac{-1}{43}right)left(frac{3}{43}right)left(frac{5}{43}right)=(-1)Biggl(-left(frac{43}{3}right)Biggr)left(frac{43}{5}right),.$$
Therefore, $$left(frac{-15}{43}right)=left(frac{1}{3}right)left(frac{3}{5}right)=left(frac{3}{5}right),.$$ It is easy to verify that $left(dfrac{3}{5}right)=-1$, whence $$left(frac{-15}{43}right)=-1,.$$ You can check that $12^2equiv 15pmod{43}$, so $left(dfrac{15}{43}right)=+1$, whereas $left(dfrac{-1}{43}right)=-1$, confirming the calculations.
$endgroup$
add a comment |
$begingroup$
As remarked in comments, to use quadratic reciprocity we need to work with Legendre Symbols
$$ left(frac{p}{q}right)$$
for $p,q$ prime.
You should repeatedly use the property
$$ left(frac{ab}{p}right)=left(frac{a}{p}right)left(frac{b}{p}right)$$
to make sure that you are calculating with both parts of the symbol being prime. That is, write
$$ left(frac{10}{31}right)=left(frac{2}{31}right)left(frac{5}{31}right)$$
then iteratively apply quadratic reciprocity as you intended to.
$endgroup$
$begingroup$
But not to $2$ if I recall correctly. You can render $(2|31)=1$ from $8^2=64$, but that is not QR.
$endgroup$
– Oscar Lanzi
Dec 6 '18 at 23:23
$begingroup$
If you don't mind could you please expand on that. I am trying solve it but I missing something and I cannot figure out what
$endgroup$
– Hidaw
Dec 7 '18 at 20:28
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%2f3029147%2fwhat-are-the-legendre-symbols-left-frac1031-right-and-left-frac-15%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 an approach I would take. Note that
$$left(frac{10}{31}right)=left(frac{-21}{31}right)=left(frac{-1}{31}right)left(frac{3}{31}right)left(frac{7}{31}right)=(-1)Biggl(-left(frac{31}{3}right)Biggr)Biggl(-left(frac{31}{7}right)Biggr),.$$
That is, $$left(frac{10}{31}right)=-left(frac{1}{3}right)left(frac{3}{7}right)=-(+1)Biggl(-left(frac{7}{3}right)Biggr)=left(frac{1}{3}right)=+1,.$$ This can be verified by noting that $6^2equiv 5pmod{31}$ and $8^2equiv 2pmod{31}$, so $$17^2equiv (6cdot 8)^2equiv 5cdot2=10pmod{31},.$$
For the second part, note that
$$left(frac{-15}{43}right)=left(frac{-1}{43}right)left(frac{3}{43}right)left(frac{5}{43}right)=(-1)Biggl(-left(frac{43}{3}right)Biggr)left(frac{43}{5}right),.$$
Therefore, $$left(frac{-15}{43}right)=left(frac{1}{3}right)left(frac{3}{5}right)=left(frac{3}{5}right),.$$ It is easy to verify that $left(dfrac{3}{5}right)=-1$, whence $$left(frac{-15}{43}right)=-1,.$$ You can check that $12^2equiv 15pmod{43}$, so $left(dfrac{15}{43}right)=+1$, whereas $left(dfrac{-1}{43}right)=-1$, confirming the calculations.
$endgroup$
add a comment |
$begingroup$
Here is an approach I would take. Note that
$$left(frac{10}{31}right)=left(frac{-21}{31}right)=left(frac{-1}{31}right)left(frac{3}{31}right)left(frac{7}{31}right)=(-1)Biggl(-left(frac{31}{3}right)Biggr)Biggl(-left(frac{31}{7}right)Biggr),.$$
That is, $$left(frac{10}{31}right)=-left(frac{1}{3}right)left(frac{3}{7}right)=-(+1)Biggl(-left(frac{7}{3}right)Biggr)=left(frac{1}{3}right)=+1,.$$ This can be verified by noting that $6^2equiv 5pmod{31}$ and $8^2equiv 2pmod{31}$, so $$17^2equiv (6cdot 8)^2equiv 5cdot2=10pmod{31},.$$
For the second part, note that
$$left(frac{-15}{43}right)=left(frac{-1}{43}right)left(frac{3}{43}right)left(frac{5}{43}right)=(-1)Biggl(-left(frac{43}{3}right)Biggr)left(frac{43}{5}right),.$$
Therefore, $$left(frac{-15}{43}right)=left(frac{1}{3}right)left(frac{3}{5}right)=left(frac{3}{5}right),.$$ It is easy to verify that $left(dfrac{3}{5}right)=-1$, whence $$left(frac{-15}{43}right)=-1,.$$ You can check that $12^2equiv 15pmod{43}$, so $left(dfrac{15}{43}right)=+1$, whereas $left(dfrac{-1}{43}right)=-1$, confirming the calculations.
$endgroup$
add a comment |
$begingroup$
Here is an approach I would take. Note that
$$left(frac{10}{31}right)=left(frac{-21}{31}right)=left(frac{-1}{31}right)left(frac{3}{31}right)left(frac{7}{31}right)=(-1)Biggl(-left(frac{31}{3}right)Biggr)Biggl(-left(frac{31}{7}right)Biggr),.$$
That is, $$left(frac{10}{31}right)=-left(frac{1}{3}right)left(frac{3}{7}right)=-(+1)Biggl(-left(frac{7}{3}right)Biggr)=left(frac{1}{3}right)=+1,.$$ This can be verified by noting that $6^2equiv 5pmod{31}$ and $8^2equiv 2pmod{31}$, so $$17^2equiv (6cdot 8)^2equiv 5cdot2=10pmod{31},.$$
For the second part, note that
$$left(frac{-15}{43}right)=left(frac{-1}{43}right)left(frac{3}{43}right)left(frac{5}{43}right)=(-1)Biggl(-left(frac{43}{3}right)Biggr)left(frac{43}{5}right),.$$
Therefore, $$left(frac{-15}{43}right)=left(frac{1}{3}right)left(frac{3}{5}right)=left(frac{3}{5}right),.$$ It is easy to verify that $left(dfrac{3}{5}right)=-1$, whence $$left(frac{-15}{43}right)=-1,.$$ You can check that $12^2equiv 15pmod{43}$, so $left(dfrac{15}{43}right)=+1$, whereas $left(dfrac{-1}{43}right)=-1$, confirming the calculations.
$endgroup$
Here is an approach I would take. Note that
$$left(frac{10}{31}right)=left(frac{-21}{31}right)=left(frac{-1}{31}right)left(frac{3}{31}right)left(frac{7}{31}right)=(-1)Biggl(-left(frac{31}{3}right)Biggr)Biggl(-left(frac{31}{7}right)Biggr),.$$
That is, $$left(frac{10}{31}right)=-left(frac{1}{3}right)left(frac{3}{7}right)=-(+1)Biggl(-left(frac{7}{3}right)Biggr)=left(frac{1}{3}right)=+1,.$$ This can be verified by noting that $6^2equiv 5pmod{31}$ and $8^2equiv 2pmod{31}$, so $$17^2equiv (6cdot 8)^2equiv 5cdot2=10pmod{31},.$$
For the second part, note that
$$left(frac{-15}{43}right)=left(frac{-1}{43}right)left(frac{3}{43}right)left(frac{5}{43}right)=(-1)Biggl(-left(frac{43}{3}right)Biggr)left(frac{43}{5}right),.$$
Therefore, $$left(frac{-15}{43}right)=left(frac{1}{3}right)left(frac{3}{5}right)=left(frac{3}{5}right),.$$ It is easy to verify that $left(dfrac{3}{5}right)=-1$, whence $$left(frac{-15}{43}right)=-1,.$$ You can check that $12^2equiv 15pmod{43}$, so $left(dfrac{15}{43}right)=+1$, whereas $left(dfrac{-1}{43}right)=-1$, confirming the calculations.
answered Dec 6 '18 at 22:53
BatominovskiBatominovski
33k33293
33k33293
add a comment |
add a comment |
$begingroup$
As remarked in comments, to use quadratic reciprocity we need to work with Legendre Symbols
$$ left(frac{p}{q}right)$$
for $p,q$ prime.
You should repeatedly use the property
$$ left(frac{ab}{p}right)=left(frac{a}{p}right)left(frac{b}{p}right)$$
to make sure that you are calculating with both parts of the symbol being prime. That is, write
$$ left(frac{10}{31}right)=left(frac{2}{31}right)left(frac{5}{31}right)$$
then iteratively apply quadratic reciprocity as you intended to.
$endgroup$
$begingroup$
But not to $2$ if I recall correctly. You can render $(2|31)=1$ from $8^2=64$, but that is not QR.
$endgroup$
– Oscar Lanzi
Dec 6 '18 at 23:23
$begingroup$
If you don't mind could you please expand on that. I am trying solve it but I missing something and I cannot figure out what
$endgroup$
– Hidaw
Dec 7 '18 at 20:28
add a comment |
$begingroup$
As remarked in comments, to use quadratic reciprocity we need to work with Legendre Symbols
$$ left(frac{p}{q}right)$$
for $p,q$ prime.
You should repeatedly use the property
$$ left(frac{ab}{p}right)=left(frac{a}{p}right)left(frac{b}{p}right)$$
to make sure that you are calculating with both parts of the symbol being prime. That is, write
$$ left(frac{10}{31}right)=left(frac{2}{31}right)left(frac{5}{31}right)$$
then iteratively apply quadratic reciprocity as you intended to.
$endgroup$
$begingroup$
But not to $2$ if I recall correctly. You can render $(2|31)=1$ from $8^2=64$, but that is not QR.
$endgroup$
– Oscar Lanzi
Dec 6 '18 at 23:23
$begingroup$
If you don't mind could you please expand on that. I am trying solve it but I missing something and I cannot figure out what
$endgroup$
– Hidaw
Dec 7 '18 at 20:28
add a comment |
$begingroup$
As remarked in comments, to use quadratic reciprocity we need to work with Legendre Symbols
$$ left(frac{p}{q}right)$$
for $p,q$ prime.
You should repeatedly use the property
$$ left(frac{ab}{p}right)=left(frac{a}{p}right)left(frac{b}{p}right)$$
to make sure that you are calculating with both parts of the symbol being prime. That is, write
$$ left(frac{10}{31}right)=left(frac{2}{31}right)left(frac{5}{31}right)$$
then iteratively apply quadratic reciprocity as you intended to.
$endgroup$
As remarked in comments, to use quadratic reciprocity we need to work with Legendre Symbols
$$ left(frac{p}{q}right)$$
for $p,q$ prime.
You should repeatedly use the property
$$ left(frac{ab}{p}right)=left(frac{a}{p}right)left(frac{b}{p}right)$$
to make sure that you are calculating with both parts of the symbol being prime. That is, write
$$ left(frac{10}{31}right)=left(frac{2}{31}right)left(frac{5}{31}right)$$
then iteratively apply quadratic reciprocity as you intended to.
answered Dec 6 '18 at 22:53
Antonios-Alexandros RobotisAntonios-Alexandros Robotis
10.2k41641
10.2k41641
$begingroup$
But not to $2$ if I recall correctly. You can render $(2|31)=1$ from $8^2=64$, but that is not QR.
$endgroup$
– Oscar Lanzi
Dec 6 '18 at 23:23
$begingroup$
If you don't mind could you please expand on that. I am trying solve it but I missing something and I cannot figure out what
$endgroup$
– Hidaw
Dec 7 '18 at 20:28
add a comment |
$begingroup$
But not to $2$ if I recall correctly. You can render $(2|31)=1$ from $8^2=64$, but that is not QR.
$endgroup$
– Oscar Lanzi
Dec 6 '18 at 23:23
$begingroup$
If you don't mind could you please expand on that. I am trying solve it but I missing something and I cannot figure out what
$endgroup$
– Hidaw
Dec 7 '18 at 20:28
$begingroup$
But not to $2$ if I recall correctly. You can render $(2|31)=1$ from $8^2=64$, but that is not QR.
$endgroup$
– Oscar Lanzi
Dec 6 '18 at 23:23
$begingroup$
But not to $2$ if I recall correctly. You can render $(2|31)=1$ from $8^2=64$, but that is not QR.
$endgroup$
– Oscar Lanzi
Dec 6 '18 at 23:23
$begingroup$
If you don't mind could you please expand on that. I am trying solve it but I missing something and I cannot figure out what
$endgroup$
– Hidaw
Dec 7 '18 at 20:28
$begingroup$
If you don't mind could you please expand on that. I am trying solve it but I missing something and I cannot figure out what
$endgroup$
– Hidaw
Dec 7 '18 at 20:28
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%2f3029147%2fwhat-are-the-legendre-symbols-left-frac1031-right-and-left-frac-15%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
3
$begingroup$
If you are using the Legendre symbol (and not the Jacobi symbol), then the denominators are supposed to be prime. Clearly, $10$ and $15$ are not prime, and the quadratic reciprocity law you are using is highly dubious since it works only with odd integers.
$endgroup$
– Batominovski
Dec 6 '18 at 22:35
$begingroup$
@Batominovski ohh I did not know! Thank you so much for the comment
$endgroup$
– Hidaw
Dec 6 '18 at 22:37
$begingroup$
And please use a more descriptive title the next time.
$endgroup$
– Batominovski
Dec 6 '18 at 22:37
2
$begingroup$
Even with Jacobi symbols (as an intermediate step in the calculation) you need to treat factors of 2 on the top specially.
$endgroup$
– Daniel Schepler
Dec 6 '18 at 22:45