Legendre symbol, what is it?
$begingroup$
I am reading wiki article about Legendre symbol and I don't understand the power meaning. Can you please explain the next expression.
$$left(frac apright)equiv a^{frac{p-1}{2}}pmod p$$
elementary-number-theory quadratic-residues legendre-symbol
edited Feb 1 '16 at 15:15
paul garrett
32k362118
asked Feb 1 '16 at 14:58
Ilya GazmanIlya Gazman
470927
$endgroup$
add a comment |
$begingroup$
I am reading wiki article about Legendre symbol and I don't understand the power meaning. Can you please explain the next expression.
$$left(frac apright)equiv a^{frac{p-1}{2}}pmod p$$
elementary-number-theory quadratic-residues legendre-symbol
edited Feb 1 '16 at 15:15
paul garrett
32k362118
asked Feb 1 '16 at 14:58
Ilya GazmanIlya Gazman
470927
$endgroup$
$begingroup$
@ThomasAndrews tnx, first covered.
$endgroup$
– Ilya Gazman
Feb 1 '16 at 15:07
1
$begingroup$
It's the usual definition of exponentiation; $frac{p-1}{2}$ will always be an integer because $p$ is odd.
$endgroup$
– DylanSp
Feb 1 '16 at 15:07
2
$begingroup$
It would really help if you were specific about what you are asking. Do you know what $aequiv bpmod p$ means, for example? What is confusing you? Are you really asking us to explain what the expression means, or are you asking us to explain why the expression is true?
$endgroup$
– Thomas Andrews
Feb 1 '16 at 15:08
$begingroup$
@ThomasAndrews I am asking what the expression means. This is a definition of new symbols and I am just trying to make sure that I am reading it right and it's the same power that I know and not new definition with the new Legendre symbol. I just trying to understand what is Legendre symbol and how to use it. Sorry if my question may sims to trivial.
$endgroup$
– Ilya Gazman
Feb 1 '16 at 15:12
add a comment |
$begingroup$
I am reading wiki article about Legendre symbol and I don't understand the power meaning. Can you please explain the next expression.
$$left(frac apright)equiv a^{frac{p-1}{2}}pmod p$$
elementary-number-theory quadratic-residues legendre-symbol
edited Feb 1 '16 at 15:15
paul garrett
32k362118
asked Feb 1 '16 at 14:58
Ilya GazmanIlya Gazman
470927
$endgroup$
I am reading wiki article about Legendre symbol and I don't understand the power meaning. Can you please explain the next expression.
$$left(frac apright)equiv a^{frac{p-1}{2}}pmod p$$
elementary-number-theory quadratic-residues legendre-symbol
elementary-number-theory quadratic-residues legendre-symbol
edited Feb 1 '16 at 15:15
paul garrett
32k362118
asked Feb 1 '16 at 14:58
Ilya GazmanIlya Gazman
470927
edited Feb 1 '16 at 15:15
paul garrett
32k362118
asked Feb 1 '16 at 14:58
Ilya GazmanIlya Gazman
470927
edited Feb 1 '16 at 15:15
paul garrett
32k362118
edited Feb 1 '16 at 15:15
paul garrett
32k362118
edited Feb 1 '16 at 15:15
paul garrett
32k362118
32k362118
asked Feb 1 '16 at 14:58
Ilya GazmanIlya Gazman
470927
asked Feb 1 '16 at 14:58
Ilya GazmanIlya Gazman
470927
asked Feb 1 '16 at 14:58
Ilya GazmanIlya Gazman
470927
470927
$begingroup$
@ThomasAndrews tnx, first covered.
$endgroup$
– Ilya Gazman
Feb 1 '16 at 15:07
1
$begingroup$
It's the usual definition of exponentiation; $frac{p-1}{2}$ will always be an integer because $p$ is odd.
$endgroup$
– DylanSp
Feb 1 '16 at 15:07
2
$begingroup$
It would really help if you were specific about what you are asking. Do you know what $aequiv bpmod p$ means, for example? What is confusing you? Are you really asking us to explain what the expression means, or are you asking us to explain why the expression is true?
$endgroup$
– Thomas Andrews
Feb 1 '16 at 15:08
$begingroup$
@ThomasAndrews I am asking what the expression means. This is a definition of new symbols and I am just trying to make sure that I am reading it right and it's the same power that I know and not new definition with the new Legendre symbol. I just trying to understand what is Legendre symbol and how to use it. Sorry if my question may sims to trivial.
$endgroup$
– Ilya Gazman
Feb 1 '16 at 15:12
add a comment |
$begingroup$
@ThomasAndrews tnx, first covered.
$endgroup$
– Ilya Gazman
Feb 1 '16 at 15:07
1
$begingroup$
It's the usual definition of exponentiation; $frac{p-1}{2}$ will always be an integer because $p$ is odd.
$endgroup$
– DylanSp
Feb 1 '16 at 15:07
2
$begingroup$
It would really help if you were specific about what you are asking. Do you know what $aequiv bpmod p$ means, for example? What is confusing you? Are you really asking us to explain what the expression means, or are you asking us to explain why the expression is true?
$endgroup$
– Thomas Andrews
Feb 1 '16 at 15:08
$begingroup$
@ThomasAndrews I am asking what the expression means. This is a definition of new symbols and I am just trying to make sure that I am reading it right and it's the same power that I know and not new definition with the new Legendre symbol. I just trying to understand what is Legendre symbol and how to use it. Sorry if my question may sims to trivial.
$endgroup$
– Ilya Gazman
Feb 1 '16 at 15:12
$begingroup$
@ThomasAndrews tnx, first covered.
$endgroup$
– Ilya Gazman
Feb 1 '16 at 15:07
$begingroup$
@ThomasAndrews tnx, first covered.
$endgroup$
– Ilya Gazman
Feb 1 '16 at 15:07
1
1
$begingroup$
It's the usual definition of exponentiation; $frac{p-1}{2}$ will always be an integer because $p$ is odd.
$endgroup$
– DylanSp
Feb 1 '16 at 15:07
$begingroup$
It's the usual definition of exponentiation; $frac{p-1}{2}$ will always be an integer because $p$ is odd.
$endgroup$
– DylanSp
Feb 1 '16 at 15:07
2
2
$begingroup$
It would really help if you were specific about what you are asking. Do you know what $aequiv bpmod p$ means, for example? What is confusing you? Are you really asking us to explain what the expression means, or are you asking us to explain why the expression is true?
$endgroup$
– Thomas Andrews
Feb 1 '16 at 15:08
$begingroup$
It would really help if you were specific about what you are asking. Do you know what $aequiv bpmod p$ means, for example? What is confusing you? Are you really asking us to explain what the expression means, or are you asking us to explain why the expression is true?
$endgroup$
– Thomas Andrews
Feb 1 '16 at 15:08
$begingroup$
@ThomasAndrews I am asking what the expression means. This is a definition of new symbols and I am just trying to make sure that I am reading it right and it's the same power that I know and not new definition with the new Legendre symbol. I just trying to understand what is Legendre symbol and how to use it. Sorry if my question may sims to trivial.
$endgroup$
– Ilya Gazman
Feb 1 '16 at 15:12
$begingroup$
@ThomasAndrews I am asking what the expression means. This is a definition of new symbols and I am just trying to make sure that I am reading it right and it's the same power that I know and not new definition with the new Legendre symbol. I just trying to understand what is Legendre symbol and how to use it. Sorry if my question may sims to trivial.
$endgroup$
– Ilya Gazman
Feb 1 '16 at 15:12
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Since you say you have read about Legendre symbol on Wikipedia, you should already know that $left(frac{a}{p}right)$ is defined as $0$ if $pmid a$ and as $pm1$ for $pnmid a$, depending on whether $a$ is a quadratic residue modulo $p$ or not.
According to Euler's criterion, the congruence
$$left(frac{a}{p}right) equiv a^{(p-1)/2}$$
holds for any odd prime $p$.
There is nothing mysterious about the expression $a^{(p-1)/2}$, it is just a usual exponentiation. (It is useful to notice that $(p-1)/2$ is a positive integer if $p$ is an odd prime.)
Let us have a look on specific examples. For $p=5$ we have $(p-1)/2=2$ and we get
$$begin{array}{|c|c|c|}
hline
a & a^2 & left(frac{a}{5}right) \hline
0 & 0 & 0 \hline
1 & 1 & 1 \hline
2 & 4 &-1 \hline
3 & 9 &-1 \hline
4 &16 & 1 \hline
end{array}
$$
If you look at the second and third column, they are indeed congruent modulo $5$.
For $p=7$ we get the following table:
$$begin{array}{|c|c|c|}
hline
a & a^3 & left(frac{a}{7}right) \hline
0 & 0 & 0 \hline
1 & 1 & 1 \hline
2 & 8 & 1 \hline
3 &27 &-1 \hline
4 &64 & 1 \hline
5 &125&-1 \hline
6 &216&-1 \hline
end{array}
$$
(We know that quadratic residues modulo $7$ are $(pm1)^2equiv1pmod 7$, $(pm2)^2equiv4pmod 7$ and $(pm3)^2equiv2pmod 7$.)
You may notice that instead of calculating $a^3$ we might calculate $a^3bmod 7$, which would is a bit easier. For example $5^3=5^2cdot 5 equiv 25 cdot 5 equiv 4cdot 5 equiv 20 equiv -1 pmod 7$.
This is more about the the basic properties of congruences rather than about the Legendre symbol, but I will try to explain the previous computation, per request in a comment by the OP.
The only thing we are using here is the fact that if $a_1equiv b_1pmod n$ and $a_2equiv b_2pmod n$, then also $a_1b_1equiv a_2b_2pmod n$.
Using this rule we know that
$$25cdot 5equiv 4cdot 5pmod 7$$
since $25equiv 4pmod 7$.
In fact, we have even easier way to calculate $5^3 bmod 7$. If we notice that $5equiv -2 pmod 7$ then
$$5^3 equiv (-2)^3 equiv -8 equiv -1 pmod 7.$$
For more about similar computations, have a look at How do I compute $a^b,bmod c$ by hand? and other related posts.
answered Feb 1 '16 at 15:12
Martin SleziakMartin Sleziak
44.8k10119272
$endgroup$
$begingroup$
I don't understand the last part of your answer. And this actually what I been searching at the first place. I asked about it here
$endgroup$
– Ilya Gazman
Feb 1 '16 at 15:43
$begingroup$
By the last part, you mean the one starting: "You may notice that instead..."? (BTW I think that if, for some reason, the answer is not sufficient for you, you probably should not have accepted it. The green tick sends a message to other potential answerers: "The OP is already satisfied with the existing answers." There is no reason to be hasty with accepting one of the answers.)
$endgroup$
– Martin Sleziak
Feb 1 '16 at 15:44
$begingroup$
Yeah, how do you make the calculation of the big power easier.
$endgroup$
– Ilya Gazman
Feb 1 '16 at 15:45
$begingroup$
@Ilya_Gazman I have tried to add some explanation and also a link to other post(s) which might help you with this.
$endgroup$
– Martin Sleziak
Feb 1 '16 at 15:54
$begingroup$
Big big big tnx I am reading it now.
$endgroup$
– Ilya Gazman
Feb 1 '16 at 16:01
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%2f1635987%2flegendre-symbol-what-is-it%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$
Since you say you have read about Legendre symbol on Wikipedia, you should already know that $left(frac{a}{p}right)$ is defined as $0$ if $pmid a$ and as $pm1$ for $pnmid a$, depending on whether $a$ is a quadratic residue modulo $p$ or not.
According to Euler's criterion, the congruence
$$left(frac{a}{p}right) equiv a^{(p-1)/2}$$
holds for any odd prime $p$.
There is nothing mysterious about the expression $a^{(p-1)/2}$, it is just a usual exponentiation. (It is useful to notice that $(p-1)/2$ is a positive integer if $p$ is an odd prime.)
Let us have a look on specific examples. For $p=5$ we have $(p-1)/2=2$ and we get
$$begin{array}{|c|c|c|}
hline
a & a^2 & left(frac{a}{5}right) \hline
0 & 0 & 0 \hline
1 & 1 & 1 \hline
2 & 4 &-1 \hline
3 & 9 &-1 \hline
4 &16 & 1 \hline
end{array}
$$
If you look at the second and third column, they are indeed congruent modulo $5$.
For $p=7$ we get the following table:
$$begin{array}{|c|c|c|}
hline
a & a^3 & left(frac{a}{7}right) \hline
0 & 0 & 0 \hline
1 & 1 & 1 \hline
2 & 8 & 1 \hline
3 &27 &-1 \hline
4 &64 & 1 \hline
5 &125&-1 \hline
6 &216&-1 \hline
end{array}
$$
(We know that quadratic residues modulo $7$ are $(pm1)^2equiv1pmod 7$, $(pm2)^2equiv4pmod 7$ and $(pm3)^2equiv2pmod 7$.)
You may notice that instead of calculating $a^3$ we might calculate $a^3bmod 7$, which would is a bit easier. For example $5^3=5^2cdot 5 equiv 25 cdot 5 equiv 4cdot 5 equiv 20 equiv -1 pmod 7$.
This is more about the the basic properties of congruences rather than about the Legendre symbol, but I will try to explain the previous computation, per request in a comment by the OP.
The only thing we are using here is the fact that if $a_1equiv b_1pmod n$ and $a_2equiv b_2pmod n$, then also $a_1b_1equiv a_2b_2pmod n$.
Using this rule we know that
$$25cdot 5equiv 4cdot 5pmod 7$$
since $25equiv 4pmod 7$.
In fact, we have even easier way to calculate $5^3 bmod 7$. If we notice that $5equiv -2 pmod 7$ then
$$5^3 equiv (-2)^3 equiv -8 equiv -1 pmod 7.$$
For more about similar computations, have a look at How do I compute $a^b,bmod c$ by hand? and other related posts.
answered Feb 1 '16 at 15:12
Martin SleziakMartin Sleziak
44.8k10119272
$endgroup$
$begingroup$
I don't understand the last part of your answer. And this actually what I been searching at the first place. I asked about it here
$endgroup$
– Ilya Gazman
Feb 1 '16 at 15:43
$begingroup$
By the last part, you mean the one starting: "You may notice that instead..."? (BTW I think that if, for some reason, the answer is not sufficient for you, you probably should not have accepted it. The green tick sends a message to other potential answerers: "The OP is already satisfied with the existing answers." There is no reason to be hasty with accepting one of the answers.)
$endgroup$
– Martin Sleziak
Feb 1 '16 at 15:44
$begingroup$
Yeah, how do you make the calculation of the big power easier.
$endgroup$
– Ilya Gazman
Feb 1 '16 at 15:45
$begingroup$
@Ilya_Gazman I have tried to add some explanation and also a link to other post(s) which might help you with this.
$endgroup$
– Martin Sleziak
Feb 1 '16 at 15:54
$begingroup$
Big big big tnx I am reading it now.
$endgroup$
– Ilya Gazman
Feb 1 '16 at 16:01
add a comment |
$begingroup$
Since you say you have read about Legendre symbol on Wikipedia, you should already know that $left(frac{a}{p}right)$ is defined as $0$ if $pmid a$ and as $pm1$ for $pnmid a$, depending on whether $a$ is a quadratic residue modulo $p$ or not.
According to Euler's criterion, the congruence
$$left(frac{a}{p}right) equiv a^{(p-1)/2}$$
holds for any odd prime $p$.
There is nothing mysterious about the expression $a^{(p-1)/2}$, it is just a usual exponentiation. (It is useful to notice that $(p-1)/2$ is a positive integer if $p$ is an odd prime.)
Let us have a look on specific examples. For $p=5$ we have $(p-1)/2=2$ and we get
$$begin{array}{|c|c|c|}
hline
a & a^2 & left(frac{a}{5}right) \hline
0 & 0 & 0 \hline
1 & 1 & 1 \hline
2 & 4 &-1 \hline
3 & 9 &-1 \hline
4 &16 & 1 \hline
end{array}
$$
If you look at the second and third column, they are indeed congruent modulo $5$.
For $p=7$ we get the following table:
$$begin{array}{|c|c|c|}
hline
a & a^3 & left(frac{a}{7}right) \hline
0 & 0 & 0 \hline
1 & 1 & 1 \hline
2 & 8 & 1 \hline
3 &27 &-1 \hline
4 &64 & 1 \hline
5 &125&-1 \hline
6 &216&-1 \hline
end{array}
$$
(We know that quadratic residues modulo $7$ are $(pm1)^2equiv1pmod 7$, $(pm2)^2equiv4pmod 7$ and $(pm3)^2equiv2pmod 7$.)
You may notice that instead of calculating $a^3$ we might calculate $a^3bmod 7$, which would is a bit easier. For example $5^3=5^2cdot 5 equiv 25 cdot 5 equiv 4cdot 5 equiv 20 equiv -1 pmod 7$.
This is more about the the basic properties of congruences rather than about the Legendre symbol, but I will try to explain the previous computation, per request in a comment by the OP.
The only thing we are using here is the fact that if $a_1equiv b_1pmod n$ and $a_2equiv b_2pmod n$, then also $a_1b_1equiv a_2b_2pmod n$.
Using this rule we know that
$$25cdot 5equiv 4cdot 5pmod 7$$
since $25equiv 4pmod 7$.
In fact, we have even easier way to calculate $5^3 bmod 7$. If we notice that $5equiv -2 pmod 7$ then
$$5^3 equiv (-2)^3 equiv -8 equiv -1 pmod 7.$$
For more about similar computations, have a look at How do I compute $a^b,bmod c$ by hand? and other related posts.
answered Feb 1 '16 at 15:12
Martin SleziakMartin Sleziak
44.8k10119272
$endgroup$
$begingroup$
I don't understand the last part of your answer. And this actually what I been searching at the first place. I asked about it here
$endgroup$
– Ilya Gazman
Feb 1 '16 at 15:43
$begingroup$
By the last part, you mean the one starting: "You may notice that instead..."? (BTW I think that if, for some reason, the answer is not sufficient for you, you probably should not have accepted it. The green tick sends a message to other potential answerers: "The OP is already satisfied with the existing answers." There is no reason to be hasty with accepting one of the answers.)
$endgroup$
– Martin Sleziak
Feb 1 '16 at 15:44
$begingroup$
Yeah, how do you make the calculation of the big power easier.
$endgroup$
– Ilya Gazman
Feb 1 '16 at 15:45
$begingroup$
@Ilya_Gazman I have tried to add some explanation and also a link to other post(s) which might help you with this.
$endgroup$
– Martin Sleziak
Feb 1 '16 at 15:54
$begingroup$
Big big big tnx I am reading it now.
$endgroup$
– Ilya Gazman
Feb 1 '16 at 16:01
add a comment |
$begingroup$
Since you say you have read about Legendre symbol on Wikipedia, you should already know that $left(frac{a}{p}right)$ is defined as $0$ if $pmid a$ and as $pm1$ for $pnmid a$, depending on whether $a$ is a quadratic residue modulo $p$ or not.
According to Euler's criterion, the congruence
$$left(frac{a}{p}right) equiv a^{(p-1)/2}$$
holds for any odd prime $p$.
There is nothing mysterious about the expression $a^{(p-1)/2}$, it is just a usual exponentiation. (It is useful to notice that $(p-1)/2$ is a positive integer if $p$ is an odd prime.)
Let us have a look on specific examples. For $p=5$ we have $(p-1)/2=2$ and we get
$$begin{array}{|c|c|c|}
hline
a & a^2 & left(frac{a}{5}right) \hline
0 & 0 & 0 \hline
1 & 1 & 1 \hline
2 & 4 &-1 \hline
3 & 9 &-1 \hline
4 &16 & 1 \hline
end{array}
$$
If you look at the second and third column, they are indeed congruent modulo $5$.
For $p=7$ we get the following table:
$$begin{array}{|c|c|c|}
hline
a & a^3 & left(frac{a}{7}right) \hline
0 & 0 & 0 \hline
1 & 1 & 1 \hline
2 & 8 & 1 \hline
3 &27 &-1 \hline
4 &64 & 1 \hline
5 &125&-1 \hline
6 &216&-1 \hline
end{array}
$$
(We know that quadratic residues modulo $7$ are $(pm1)^2equiv1pmod 7$, $(pm2)^2equiv4pmod 7$ and $(pm3)^2equiv2pmod 7$.)
You may notice that instead of calculating $a^3$ we might calculate $a^3bmod 7$, which would is a bit easier. For example $5^3=5^2cdot 5 equiv 25 cdot 5 equiv 4cdot 5 equiv 20 equiv -1 pmod 7$.
This is more about the the basic properties of congruences rather than about the Legendre symbol, but I will try to explain the previous computation, per request in a comment by the OP.
The only thing we are using here is the fact that if $a_1equiv b_1pmod n$ and $a_2equiv b_2pmod n$, then also $a_1b_1equiv a_2b_2pmod n$.
Using this rule we know that
$$25cdot 5equiv 4cdot 5pmod 7$$
since $25equiv 4pmod 7$.
In fact, we have even easier way to calculate $5^3 bmod 7$. If we notice that $5equiv -2 pmod 7$ then
$$5^3 equiv (-2)^3 equiv -8 equiv -1 pmod 7.$$
For more about similar computations, have a look at How do I compute $a^b,bmod c$ by hand? and other related posts.
answered Feb 1 '16 at 15:12
Martin SleziakMartin Sleziak
44.8k10119272
$endgroup$
Since you say you have read about Legendre symbol on Wikipedia, you should already know that $left(frac{a}{p}right)$ is defined as $0$ if $pmid a$ and as $pm1$ for $pnmid a$, depending on whether $a$ is a quadratic residue modulo $p$ or not.
According to Euler's criterion, the congruence
$$left(frac{a}{p}right) equiv a^{(p-1)/2}$$
holds for any odd prime $p$.
There is nothing mysterious about the expression $a^{(p-1)/2}$, it is just a usual exponentiation. (It is useful to notice that $(p-1)/2$ is a positive integer if $p$ is an odd prime.)
Let us have a look on specific examples. For $p=5$ we have $(p-1)/2=2$ and we get
$$begin{array}{|c|c|c|}
hline
a & a^2 & left(frac{a}{5}right) \hline
0 & 0 & 0 \hline
1 & 1 & 1 \hline
2 & 4 &-1 \hline
3 & 9 &-1 \hline
4 &16 & 1 \hline
end{array}
$$
If you look at the second and third column, they are indeed congruent modulo $5$.
For $p=7$ we get the following table:
$$begin{array}{|c|c|c|}
hline
a & a^3 & left(frac{a}{7}right) \hline
0 & 0 & 0 \hline
1 & 1 & 1 \hline
2 & 8 & 1 \hline
3 &27 &-1 \hline
4 &64 & 1 \hline
5 &125&-1 \hline
6 &216&-1 \hline
end{array}
$$
(We know that quadratic residues modulo $7$ are $(pm1)^2equiv1pmod 7$, $(pm2)^2equiv4pmod 7$ and $(pm3)^2equiv2pmod 7$.)
You may notice that instead of calculating $a^3$ we might calculate $a^3bmod 7$, which would is a bit easier. For example $5^3=5^2cdot 5 equiv 25 cdot 5 equiv 4cdot 5 equiv 20 equiv -1 pmod 7$.
This is more about the the basic properties of congruences rather than about the Legendre symbol, but I will try to explain the previous computation, per request in a comment by the OP.
The only thing we are using here is the fact that if $a_1equiv b_1pmod n$ and $a_2equiv b_2pmod n$, then also $a_1b_1equiv a_2b_2pmod n$.
Using this rule we know that
$$25cdot 5equiv 4cdot 5pmod 7$$
since $25equiv 4pmod 7$.
In fact, we have even easier way to calculate $5^3 bmod 7$. If we notice that $5equiv -2 pmod 7$ then
$$5^3 equiv (-2)^3 equiv -8 equiv -1 pmod 7.$$
For more about similar computations, have a look at How do I compute $a^b,bmod c$ by hand? and other related posts.
answered Feb 1 '16 at 15:12
Martin SleziakMartin Sleziak
44.8k10119272
edited Dec 13 '18 at 2:40
answered Feb 1 '16 at 15:12
Martin SleziakMartin Sleziak
44.8k10119272
answered Feb 1 '16 at 15:12
Martin SleziakMartin Sleziak
44.8k10119272
answered Feb 1 '16 at 15:12
Martin SleziakMartin Sleziak
44.8k10119272
44.8k10119272
$begingroup$
I don't understand the last part of your answer. And this actually what I been searching at the first place. I asked about it here
$endgroup$
– Ilya Gazman
Feb 1 '16 at 15:43
$begingroup$
By the last part, you mean the one starting: "You may notice that instead..."? (BTW I think that if, for some reason, the answer is not sufficient for you, you probably should not have accepted it. The green tick sends a message to other potential answerers: "The OP is already satisfied with the existing answers." There is no reason to be hasty with accepting one of the answers.)
$endgroup$
– Martin Sleziak
Feb 1 '16 at 15:44
$begingroup$
Yeah, how do you make the calculation of the big power easier.
$endgroup$
– Ilya Gazman
Feb 1 '16 at 15:45
$begingroup$
@Ilya_Gazman I have tried to add some explanation and also a link to other post(s) which might help you with this.
$endgroup$
– Martin Sleziak
Feb 1 '16 at 15:54
$begingroup$
Big big big tnx I am reading it now.
$endgroup$
– Ilya Gazman
Feb 1 '16 at 16:01
add a comment |
$begingroup$
I don't understand the last part of your answer. And this actually what I been searching at the first place. I asked about it here
$endgroup$
– Ilya Gazman
Feb 1 '16 at 15:43
$begingroup$
By the last part, you mean the one starting: "You may notice that instead..."? (BTW I think that if, for some reason, the answer is not sufficient for you, you probably should not have accepted it. The green tick sends a message to other potential answerers: "The OP is already satisfied with the existing answers." There is no reason to be hasty with accepting one of the answers.)
$endgroup$
– Martin Sleziak
Feb 1 '16 at 15:44
$begingroup$
Yeah, how do you make the calculation of the big power easier.
$endgroup$
– Ilya Gazman
Feb 1 '16 at 15:45
$begingroup$
@Ilya_Gazman I have tried to add some explanation and also a link to other post(s) which might help you with this.
$endgroup$
– Martin Sleziak
Feb 1 '16 at 15:54
$begingroup$
Big big big tnx I am reading it now.
$endgroup$
– Ilya Gazman
Feb 1 '16 at 16:01
$begingroup$
I don't understand the last part of your answer. And this actually what I been searching at the first place. I asked about it here
$endgroup$
– Ilya Gazman
Feb 1 '16 at 15:43
$begingroup$
I don't understand the last part of your answer. And this actually what I been searching at the first place. I asked about it here
$endgroup$
– Ilya Gazman
Feb 1 '16 at 15:43
$begingroup$
By the last part, you mean the one starting: "You may notice that instead..."? (BTW I think that if, for some reason, the answer is not sufficient for you, you probably should not have accepted it. The green tick sends a message to other potential answerers: "The OP is already satisfied with the existing answers." There is no reason to be hasty with accepting one of the answers.)
$endgroup$
– Martin Sleziak
Feb 1 '16 at 15:44
$begingroup$
By the last part, you mean the one starting: "You may notice that instead..."? (BTW I think that if, for some reason, the answer is not sufficient for you, you probably should not have accepted it. The green tick sends a message to other potential answerers: "The OP is already satisfied with the existing answers." There is no reason to be hasty with accepting one of the answers.)
$endgroup$
– Martin Sleziak
Feb 1 '16 at 15:44
$begingroup$
Yeah, how do you make the calculation of the big power easier.
$endgroup$
– Ilya Gazman
Feb 1 '16 at 15:45
$begingroup$
Yeah, how do you make the calculation of the big power easier.
$endgroup$
– Ilya Gazman
Feb 1 '16 at 15:45
$begingroup$
@Ilya_Gazman I have tried to add some explanation and also a link to other post(s) which might help you with this.
$endgroup$
– Martin Sleziak
Feb 1 '16 at 15:54
$begingroup$
@Ilya_Gazman I have tried to add some explanation and also a link to other post(s) which might help you with this.
$endgroup$
– Martin Sleziak
Feb 1 '16 at 15:54
$begingroup$
Big big big tnx I am reading it now.
$endgroup$
– Ilya Gazman
Feb 1 '16 at 16:01
$begingroup$
Big big big tnx I am reading it now.
$endgroup$
– Ilya Gazman
Feb 1 '16 at 16:01
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%2f1635987%2flegendre-symbol-what-is-it%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$
@ThomasAndrews tnx, first covered.
$endgroup$
– Ilya Gazman
Feb 1 '16 at 15:07
1
$begingroup$
It's the usual definition of exponentiation; $frac{p-1}{2}$ will always be an integer because $p$ is odd.
$endgroup$
– DylanSp
Feb 1 '16 at 15:07
2
$begingroup$
It would really help if you were specific about what you are asking. Do you know what $aequiv bpmod p$ means, for example? What is confusing you? Are you really asking us to explain what the expression means, or are you asking us to explain why the expression is true?
$endgroup$
– Thomas Andrews
Feb 1 '16 at 15:08
$begingroup$
@ThomasAndrews I am asking what the expression means. This is a definition of new symbols and I am just trying to make sure that I am reading it right and it's the same power that I know and not new definition with the new Legendre symbol. I just trying to understand what is Legendre symbol and how to use it. Sorry if my question may sims to trivial.
$endgroup$
– Ilya Gazman
Feb 1 '16 at 15:12