Mixing
Finding all possible remainders of perfect squares mod $n$, $nin mathbbZ_+$
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
Is there a way to generalize what remainders of perfect squares to expect for different bases. for $a^2equiv 0,1 text mod 3$. but what about $a^2equiv r text mod n in mathbbZ_+$. For e.g if I want to know all the possible remainders $r$ for $a^2$ mod $117$, then will it still have $0,1$, if not, then how can I find all the remainders?
Edit
Well clearly for the e.g I provided we'd have all $a^2leq 117$ in $r$, but I guess the question was whether or not the $r$ that appear in base $5$ will also appear in base $22$, and the $r$ in base $q$ will also appear in base $k$, s.t $q<k$
Thanks
elementary-number-theory proof-writing
asked Jul 14 at 21:14
john fowles
1,093817
add a comment |Â
up vote
3
down vote
favorite
Is there a way to generalize what remainders of perfect squares to expect for different bases. for $a^2equiv 0,1 text mod 3$. but what about $a^2equiv r text mod n in mathbbZ_+$. For e.g if I want to know all the possible remainders $r$ for $a^2$ mod $117$, then will it still have $0,1$, if not, then how can I find all the remainders?
Edit
Well clearly for the e.g I provided we'd have all $a^2leq 117$ in $r$, but I guess the question was whether or not the $r$ that appear in base $5$ will also appear in base $22$, and the $r$ in base $q$ will also appear in base $k$, s.t $q<k$
Thanks
elementary-number-theory proof-writing
asked Jul 14 at 21:14
john fowles
1,093817
1
en.wikipedia.org/wiki/Quadratic_residue
– Mason
Jul 14 at 21:23
For $n$ prime, it is always half of the non-zero remainders, and you can use quadratic reciprocity to check any particular $r$.
– Thomas Andrews
Jul 14 at 21:23
$0$ and $1$ will always be residues of perfect squares to any modulus, but there will generally be others.
– Joffan
Jul 14 at 23:14
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
Is there a way to generalize what remainders of perfect squares to expect for different bases. for $a^2equiv 0,1 text mod 3$. but what about $a^2equiv r text mod n in mathbbZ_+$. For e.g if I want to know all the possible remainders $r$ for $a^2$ mod $117$, then will it still have $0,1$, if not, then how can I find all the remainders?
Edit
Well clearly for the e.g I provided we'd have all $a^2leq 117$ in $r$, but I guess the question was whether or not the $r$ that appear in base $5$ will also appear in base $22$, and the $r$ in base $q$ will also appear in base $k$, s.t $q<k$
Thanks
elementary-number-theory proof-writing
asked Jul 14 at 21:14
john fowles
1,093817
Is there a way to generalize what remainders of perfect squares to expect for different bases. for $a^2equiv 0,1 text mod 3$. but what about $a^2equiv r text mod n in mathbbZ_+$. For e.g if I want to know all the possible remainders $r$ for $a^2$ mod $117$, then will it still have $0,1$, if not, then how can I find all the remainders?
Edit
Well clearly for the e.g I provided we'd have all $a^2leq 117$ in $r$, but I guess the question was whether or not the $r$ that appear in base $5$ will also appear in base $22$, and the $r$ in base $q$ will also appear in base $k$, s.t $q<k$
Thanks
elementary-number-theory proof-writing
asked Jul 14 at 21:14
john fowles
1,093817
edited Jul 14 at 23:26
asked Jul 14 at 21:14
john fowles
1,093817
asked Jul 14 at 21:14
john fowles
1,093817
asked Jul 14 at 21:14
john fowles
1,093817
1,093817
1
en.wikipedia.org/wiki/Quadratic_residue
– Mason
Jul 14 at 21:23
For $n$ prime, it is always half of the non-zero remainders, and you can use quadratic reciprocity to check any particular $r$.
– Thomas Andrews
Jul 14 at 21:23
$0$ and $1$ will always be residues of perfect squares to any modulus, but there will generally be others.
– Joffan
Jul 14 at 23:14
add a comment |Â
1
en.wikipedia.org/wiki/Quadratic_residue
– Mason
Jul 14 at 21:23
For $n$ prime, it is always half of the non-zero remainders, and you can use quadratic reciprocity to check any particular $r$.
– Thomas Andrews
Jul 14 at 21:23
$0$ and $1$ will always be residues of perfect squares to any modulus, but there will generally be others.
– Joffan
Jul 14 at 23:14
1
1
en.wikipedia.org/wiki/Quadratic_residue
– Mason
Jul 14 at 21:23
en.wikipedia.org/wiki/Quadratic_residue
– Mason
Jul 14 at 21:23
For $n$ prime, it is always half of the non-zero remainders, and you can use quadratic reciprocity to check any particular $r$.
– Thomas Andrews
Jul 14 at 21:23
For $n$ prime, it is always half of the non-zero remainders, and you can use quadratic reciprocity to check any particular $r$.
– Thomas Andrews
Jul 14 at 21:23
$0$ and $1$ will always be residues of perfect squares to any modulus, but there will generally be others.
– Joffan
Jul 14 at 23:14
$0$ and $1$ will always be residues of perfect squares to any modulus, but there will generally be others.
– Joffan
Jul 14 at 23:14
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
3
down vote
accepted
Yes, there's some machinery you can use to figure out if $r$ is a remainder of a perfect square mod $n$. These $r$'s are called quadratic residues, and the main technique at play to see if $r$ is a quadratic residue is quadratic reciprocity and properties of Legendre symbols.
answered Jul 14 at 21:23
Marcus M
8,1731847
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
Yes, there's some machinery you can use to figure out if $r$ is a remainder of a perfect square mod $n$. These $r$'s are called quadratic residues, and the main technique at play to see if $r$ is a quadratic residue is quadratic reciprocity and properties of Legendre symbols.
answered Jul 14 at 21:23
Marcus M
8,1731847
add a comment |Â
up vote
3
down vote
accepted
Yes, there's some machinery you can use to figure out if $r$ is a remainder of a perfect square mod $n$. These $r$'s are called quadratic residues, and the main technique at play to see if $r$ is a quadratic residue is quadratic reciprocity and properties of Legendre symbols.
answered Jul 14 at 21:23
Marcus M
8,1731847
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
Yes, there's some machinery you can use to figure out if $r$ is a remainder of a perfect square mod $n$. These $r$'s are called quadratic residues, and the main technique at play to see if $r$ is a quadratic residue is quadratic reciprocity and properties of Legendre symbols.
answered Jul 14 at 21:23
Marcus M
8,1731847
Yes, there's some machinery you can use to figure out if $r$ is a remainder of a perfect square mod $n$. These $r$'s are called quadratic residues, and the main technique at play to see if $r$ is a quadratic residue is quadratic reciprocity and properties of Legendre symbols.
answered Jul 14 at 21:23
Marcus M
8,1731847
answered Jul 14 at 21:23
Marcus M
8,1731847
answered Jul 14 at 21:23
Marcus M
8,1731847
answered Jul 14 at 21:23
Marcus M
8,1731847
8,1731847
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%2f2851968%2ffinding-all-possible-remainders-of-perfect-squares-mod-n-n-in-mathbbz%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
en.wikipedia.org/wiki/Quadratic_residue
– Mason
Jul 14 at 21:23
For $n$ prime, it is always half of the non-zero remainders, and you can use quadratic reciprocity to check any particular $r$.
– Thomas Andrews
Jul 14 at 21:23
$0$ and $1$ will always be residues of perfect squares to any modulus, but there will generally be others.
– Joffan
Jul 14 at 23:14