Mixing
the solutions are quadratic nonresidues modulo $p$
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
Let $q$ be an odd prime number, such that $p=4q+1$ is also an odd prime. I want to show that the congruence $x^2 equiv -1 pmodp$ has two (incongruenct modulo $p$) solutions, which are quadratic nonresidues modulo $p$.
I have thought to consider the Jacobi symbol.
We have that $left( frac-1pright)=left( frac-14q+1right)=(-1)^frac4q+1-12=(-1)^2q=1$.
From this we deduce that $x^2 equiv -1 pmodp$ has two incongruent modulo $p$ solutions, right?
How do we deduce that the solutions are quadratic nonresidues modulo $p$ ?
number-theory quadratic-residues
asked Aug 6 at 20:09
Evinda
451412
add a comment |Â
up vote
0
down vote
favorite
Let $q$ be an odd prime number, such that $p=4q+1$ is also an odd prime. I want to show that the congruence $x^2 equiv -1 pmodp$ has two (incongruenct modulo $p$) solutions, which are quadratic nonresidues modulo $p$.
I have thought to consider the Jacobi symbol.
We have that $left( frac-1pright)=left( frac-14q+1right)=(-1)^frac4q+1-12=(-1)^2q=1$.
From this we deduce that $x^2 equiv -1 pmodp$ has two incongruent modulo $p$ solutions, right?
How do we deduce that the solutions are quadratic nonresidues modulo $p$ ?
number-theory quadratic-residues
asked Aug 6 at 20:09
Evinda
451412
1
Hint: suppose you got quadratic residues. Deduce the existence of an element of order $8$, derive contradiction.
– lulu
Aug 6 at 20:14
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Let $q$ be an odd prime number, such that $p=4q+1$ is also an odd prime. I want to show that the congruence $x^2 equiv -1 pmodp$ has two (incongruenct modulo $p$) solutions, which are quadratic nonresidues modulo $p$.
I have thought to consider the Jacobi symbol.
We have that $left( frac-1pright)=left( frac-14q+1right)=(-1)^frac4q+1-12=(-1)^2q=1$.
From this we deduce that $x^2 equiv -1 pmodp$ has two incongruent modulo $p$ solutions, right?
How do we deduce that the solutions are quadratic nonresidues modulo $p$ ?
number-theory quadratic-residues
asked Aug 6 at 20:09
Evinda
451412
Let $q$ be an odd prime number, such that $p=4q+1$ is also an odd prime. I want to show that the congruence $x^2 equiv -1 pmodp$ has two (incongruenct modulo $p$) solutions, which are quadratic nonresidues modulo $p$.
I have thought to consider the Jacobi symbol.
We have that $left( frac-1pright)=left( frac-14q+1right)=(-1)^frac4q+1-12=(-1)^2q=1$.
From this we deduce that $x^2 equiv -1 pmodp$ has two incongruent modulo $p$ solutions, right?
How do we deduce that the solutions are quadratic nonresidues modulo $p$ ?
number-theory quadratic-residues
asked Aug 6 at 20:09
Evinda
451412
asked Aug 6 at 20:09
Evinda
451412
asked Aug 6 at 20:09
Evinda
451412
asked Aug 6 at 20:09
Evinda
451412
451412
1
Hint: suppose you got quadratic residues. Deduce the existence of an element of order $8$, derive contradiction.
– lulu
Aug 6 at 20:14
add a comment |Â
1
Hint: suppose you got quadratic residues. Deduce the existence of an element of order $8$, derive contradiction.
– lulu
Aug 6 at 20:14
1
1
Hint: suppose you got quadratic residues. Deduce the existence of an element of order $8$, derive contradiction.
– lulu
Aug 6 at 20:14
Hint: suppose you got quadratic residues. Deduce the existence of an element of order $8$, derive contradiction.
– lulu
Aug 6 at 20:14
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
Suppose $x$ could be a quadratic residue modulo $p$ then we could write $xequiv a^2bmod p$ for some integer $a$ therefore $a^4equiv -1bmod pimplies a^p-1equiv (-1)^fracp-14bmod pimplies 1equiv (-1)^qbmod p$ but since $q$ is an odd prime this means $1equiv -1bmod pimplies 2equiv 0bmod pimplies pmid 2implies p=2$ which is a contradiction. Therefore $x$ must be quadratic non-residue or equivilently $left( fracxpright)=-1$, and since $left( frac-xpright)=left( frac-1pright)left( fracxpright)=left( fracxpright)=-1$ we see $-x$ is also a quadratic non-residue, thus all solutions $y$ to the equation $y^2equiv -1bmod p$ are quadratic non-residues modulo $p$.
answered Aug 6 at 20:20
Ethan
6,78311963
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
Suppose $x$ could be a quadratic residue modulo $p$ then we could write $xequiv a^2bmod p$ for some integer $a$ therefore $a^4equiv -1bmod pimplies a^p-1equiv (-1)^fracp-14bmod pimplies 1equiv (-1)^qbmod p$ but since $q$ is an odd prime this means $1equiv -1bmod pimplies 2equiv 0bmod pimplies pmid 2implies p=2$ which is a contradiction. Therefore $x$ must be quadratic non-residue or equivilently $left( fracxpright)=-1$, and since $left( frac-xpright)=left( frac-1pright)left( fracxpright)=left( fracxpright)=-1$ we see $-x$ is also a quadratic non-residue, thus all solutions $y$ to the equation $y^2equiv -1bmod p$ are quadratic non-residues modulo $p$.
answered Aug 6 at 20:20
Ethan
6,78311963
add a comment |Â
up vote
2
down vote
accepted
Suppose $x$ could be a quadratic residue modulo $p$ then we could write $xequiv a^2bmod p$ for some integer $a$ therefore $a^4equiv -1bmod pimplies a^p-1equiv (-1)^fracp-14bmod pimplies 1equiv (-1)^qbmod p$ but since $q$ is an odd prime this means $1equiv -1bmod pimplies 2equiv 0bmod pimplies pmid 2implies p=2$ which is a contradiction. Therefore $x$ must be quadratic non-residue or equivilently $left( fracxpright)=-1$, and since $left( frac-xpright)=left( frac-1pright)left( fracxpright)=left( fracxpright)=-1$ we see $-x$ is also a quadratic non-residue, thus all solutions $y$ to the equation $y^2equiv -1bmod p$ are quadratic non-residues modulo $p$.
answered Aug 6 at 20:20
Ethan
6,78311963
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
Suppose $x$ could be a quadratic residue modulo $p$ then we could write $xequiv a^2bmod p$ for some integer $a$ therefore $a^4equiv -1bmod pimplies a^p-1equiv (-1)^fracp-14bmod pimplies 1equiv (-1)^qbmod p$ but since $q$ is an odd prime this means $1equiv -1bmod pimplies 2equiv 0bmod pimplies pmid 2implies p=2$ which is a contradiction. Therefore $x$ must be quadratic non-residue or equivilently $left( fracxpright)=-1$, and since $left( frac-xpright)=left( frac-1pright)left( fracxpright)=left( fracxpright)=-1$ we see $-x$ is also a quadratic non-residue, thus all solutions $y$ to the equation $y^2equiv -1bmod p$ are quadratic non-residues modulo $p$.
answered Aug 6 at 20:20
Ethan
6,78311963
Suppose $x$ could be a quadratic residue modulo $p$ then we could write $xequiv a^2bmod p$ for some integer $a$ therefore $a^4equiv -1bmod pimplies a^p-1equiv (-1)^fracp-14bmod pimplies 1equiv (-1)^qbmod p$ but since $q$ is an odd prime this means $1equiv -1bmod pimplies 2equiv 0bmod pimplies pmid 2implies p=2$ which is a contradiction. Therefore $x$ must be quadratic non-residue or equivilently $left( fracxpright)=-1$, and since $left( frac-xpright)=left( frac-1pright)left( fracxpright)=left( fracxpright)=-1$ we see $-x$ is also a quadratic non-residue, thus all solutions $y$ to the equation $y^2equiv -1bmod p$ are quadratic non-residues modulo $p$.
answered Aug 6 at 20:20
Ethan
6,78311963
answered Aug 6 at 20:20
Ethan
6,78311963
answered Aug 6 at 20:20
Ethan
6,78311963
answered Aug 6 at 20:20
Ethan
6,78311963
6,78311963
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2874271%2fthe-solutions-are-quadratic-nonresidues-modulo-p%23new-answer', 'question_page');
);
Post as a guest
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
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
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
1
Hint: suppose you got quadratic residues. Deduce the existence of an element of order $8$, derive contradiction.
– lulu
Aug 6 at 20:14