A question concerning higher residues (quadratic and so on)
$begingroup$
When $x equiv a pmod{n}$ one says that $a$ is the residue of $x$ modulo $n$.
So one can define:
$a$ is a 1-residue modulo $n$ if there is an $x$ with $x equiv a
pmod{n}$.
Clearly, every $a<n$ is a 1-residue modulo $n$.
When $x^2 equiv a pmod{n}$ one says that $a$ is the quadratic residue of $x$ modulo $n$.
So one can define:
$a$ is a 2-residue modulo $n$ if there is an $x$ with $x^2 equiv a
pmod{n}$.
In general:
$a$ is a k-residue modulo $n$ if there is an $x$ with $x^k equiv a
pmod{n}$.
And finally
$a$ is a higher residue modulo $n$ when it is a k-residue modulo
$n$ for some $k>1$.
In other words:
$a$ is a higher residue modulo $n$ when there is a $k>1$ and
an $x$ with $x^k equiv a pmod{n}$.
I have learned that
$a$ is a higher residue modulo $n$ iff it is a 1-residue modulo $n$.
– i.e. every $a < n$ is a higher residue.
An argument, why this is so, was given by Darij Grinberg in a comment to another question. It involves Euler's totient function $varphi$:
You can take $k=varphi(n)+1$ as $x^{varphi(n)} equiv 1 pmod{n}$
for each $x$ coprime to $n$.
Could anyone please clarify this argument - for me it's too concise.
elementary-number-theory modular-arithmetic totient-function quadratic-residues
asked Jan 11 at 20:57
Hans StrickerHans Stricker
6,03043886
$endgroup$
add a comment |
$begingroup$
When $x equiv a pmod{n}$ one says that $a$ is the residue of $x$ modulo $n$.
So one can define:
$a$ is a 1-residue modulo $n$ if there is an $x$ with $x equiv a
pmod{n}$.
Clearly, every $a<n$ is a 1-residue modulo $n$.
When $x^2 equiv a pmod{n}$ one says that $a$ is the quadratic residue of $x$ modulo $n$.
So one can define:
$a$ is a 2-residue modulo $n$ if there is an $x$ with $x^2 equiv a
pmod{n}$.
In general:
$a$ is a k-residue modulo $n$ if there is an $x$ with $x^k equiv a
pmod{n}$.
And finally
$a$ is a higher residue modulo $n$ when it is a k-residue modulo
$n$ for some $k>1$.
In other words:
$a$ is a higher residue modulo $n$ when there is a $k>1$ and
an $x$ with $x^k equiv a pmod{n}$.
I have learned that
$a$ is a higher residue modulo $n$ iff it is a 1-residue modulo $n$.
– i.e. every $a < n$ is a higher residue.
An argument, why this is so, was given by Darij Grinberg in a comment to another question. It involves Euler's totient function $varphi$:
You can take $k=varphi(n)+1$ as $x^{varphi(n)} equiv 1 pmod{n}$
for each $x$ coprime to $n$.
Could anyone please clarify this argument - for me it's too concise.
elementary-number-theory modular-arithmetic totient-function quadratic-residues
asked Jan 11 at 20:57
Hans StrickerHans Stricker
6,03043886
$endgroup$
$begingroup$
That argument only works for those classes prime to $n$. If, say, you let $n=4, a=2$ there is no $k>1$ for which $x^kequiv 2pmod 4$ has a solution.
$endgroup$
– lulu
Jan 11 at 21:04
$begingroup$
@lulu: Which "classes prime to $n$" do you mean? I only know "numbers coprime to $n$".
$endgroup$
– Hans Stricker
Jan 11 at 21:09
$begingroup$
Same thing. I mean the numbers coprime to $n$.
$endgroup$
– lulu
Jan 11 at 21:14
add a comment |
$begingroup$
When $x equiv a pmod{n}$ one says that $a$ is the residue of $x$ modulo $n$.
So one can define:
$a$ is a 1-residue modulo $n$ if there is an $x$ with $x equiv a
pmod{n}$.
Clearly, every $a<n$ is a 1-residue modulo $n$.
When $x^2 equiv a pmod{n}$ one says that $a$ is the quadratic residue of $x$ modulo $n$.
So one can define:
$a$ is a 2-residue modulo $n$ if there is an $x$ with $x^2 equiv a
pmod{n}$.
In general:
$a$ is a k-residue modulo $n$ if there is an $x$ with $x^k equiv a
pmod{n}$.
And finally
$a$ is a higher residue modulo $n$ when it is a k-residue modulo
$n$ for some $k>1$.
In other words:
$a$ is a higher residue modulo $n$ when there is a $k>1$ and
an $x$ with $x^k equiv a pmod{n}$.
I have learned that
$a$ is a higher residue modulo $n$ iff it is a 1-residue modulo $n$.
– i.e. every $a < n$ is a higher residue.
An argument, why this is so, was given by Darij Grinberg in a comment to another question. It involves Euler's totient function $varphi$:
You can take $k=varphi(n)+1$ as $x^{varphi(n)} equiv 1 pmod{n}$
for each $x$ coprime to $n$.
Could anyone please clarify this argument - for me it's too concise.
elementary-number-theory modular-arithmetic totient-function quadratic-residues
asked Jan 11 at 20:57
Hans StrickerHans Stricker
6,03043886
$endgroup$
When $x equiv a pmod{n}$ one says that $a$ is the residue of $x$ modulo $n$.
So one can define:
$a$ is a 1-residue modulo $n$ if there is an $x$ with $x equiv a
pmod{n}$.
Clearly, every $a<n$ is a 1-residue modulo $n$.
When $x^2 equiv a pmod{n}$ one says that $a$ is the quadratic residue of $x$ modulo $n$.
So one can define:
$a$ is a 2-residue modulo $n$ if there is an $x$ with $x^2 equiv a
pmod{n}$.
In general:
$a$ is a k-residue modulo $n$ if there is an $x$ with $x^k equiv a
pmod{n}$.
And finally
$a$ is a higher residue modulo $n$ when it is a k-residue modulo
$n$ for some $k>1$.
In other words:
$a$ is a higher residue modulo $n$ when there is a $k>1$ and
an $x$ with $x^k equiv a pmod{n}$.
I have learned that
$a$ is a higher residue modulo $n$ iff it is a 1-residue modulo $n$.
– i.e. every $a < n$ is a higher residue.
An argument, why this is so, was given by Darij Grinberg in a comment to another question. It involves Euler's totient function $varphi$:
You can take $k=varphi(n)+1$ as $x^{varphi(n)} equiv 1 pmod{n}$
for each $x$ coprime to $n$.
Could anyone please clarify this argument - for me it's too concise.
elementary-number-theory modular-arithmetic totient-function quadratic-residues
elementary-number-theory modular-arithmetic totient-function quadratic-residues
asked Jan 11 at 20:57
Hans StrickerHans Stricker
6,03043886
asked Jan 11 at 20:57
Hans StrickerHans Stricker
6,03043886
asked Jan 11 at 20:57
Hans StrickerHans Stricker
6,03043886
asked Jan 11 at 20:57
Hans StrickerHans Stricker
6,03043886
asked Jan 11 at 20:57
Hans StrickerHans Stricker
6,03043886
6,03043886
$begingroup$
That argument only works for those classes prime to $n$. If, say, you let $n=4, a=2$ there is no $k>1$ for which $x^kequiv 2pmod 4$ has a solution.
$endgroup$
– lulu
Jan 11 at 21:04
$begingroup$
@lulu: Which "classes prime to $n$" do you mean? I only know "numbers coprime to $n$".
$endgroup$
– Hans Stricker
Jan 11 at 21:09
$begingroup$
Same thing. I mean the numbers coprime to $n$.
$endgroup$
– lulu
Jan 11 at 21:14
add a comment |
$begingroup$
That argument only works for those classes prime to $n$. If, say, you let $n=4, a=2$ there is no $k>1$ for which $x^kequiv 2pmod 4$ has a solution.
$endgroup$
– lulu
Jan 11 at 21:04
$begingroup$
@lulu: Which "classes prime to $n$" do you mean? I only know "numbers coprime to $n$".
$endgroup$
– Hans Stricker
Jan 11 at 21:09
$begingroup$
Same thing. I mean the numbers coprime to $n$.
$endgroup$
– lulu
Jan 11 at 21:14
$begingroup$
That argument only works for those classes prime to $n$. If, say, you let $n=4, a=2$ there is no $k>1$ for which $x^kequiv 2pmod 4$ has a solution.
$endgroup$
– lulu
Jan 11 at 21:04
$begingroup$
That argument only works for those classes prime to $n$. If, say, you let $n=4, a=2$ there is no $k>1$ for which $x^kequiv 2pmod 4$ has a solution.
$endgroup$
– lulu
Jan 11 at 21:04
$begingroup$
@lulu: Which "classes prime to $n$" do you mean? I only know "numbers coprime to $n$".
$endgroup$
– Hans Stricker
Jan 11 at 21:09
$begingroup$
@lulu: Which "classes prime to $n$" do you mean? I only know "numbers coprime to $n$".
$endgroup$
– Hans Stricker
Jan 11 at 21:09
$begingroup$
Same thing. I mean the numbers coprime to $n$.
$endgroup$
– lulu
Jan 11 at 21:14
$begingroup$
Same thing. I mean the numbers coprime to $n$.
$endgroup$
– lulu
Jan 11 at 21:14
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
If $gcd(a,n)=1$ then $a$ is invertible $pmod n$, by Bezout's Lemma. Indeed the set of residues coprime with $n$ form a group under multiplication $pmod n$. By definition the order of that group is $varphi(n)$. It follows from basic group theory that $gcd(a,n)=1implies a^{varphi(n)}equiv 1pmod n$ whence that $a^{varphi(n)+1}equiv apmod n$
Note, however, that this argument only applies to residue classes prime to $n$. The claim you assert isn't true generally. For example, let $n=4,a=2$. We claim that, for $k>1$, the congruence $x^kequiv 2pmod 4$ has no solution. Indeed, we just go case by case. if $xequiv 0 $ then $x^kequiv 0$, if $xequiv 1$ then $x^kequiv 1$, if $xequiv 2$ then $x^kequiv 0$ (since $k>1$), and if $xequiv 3$ then $x^kequiv (-1)^knot equiv 0$.
answered Jan 11 at 21:15
lulululu
40.1k24778
$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%2f3070338%2fa-question-concerning-higher-residues-quadratic-and-so-on%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$
If $gcd(a,n)=1$ then $a$ is invertible $pmod n$, by Bezout's Lemma. Indeed the set of residues coprime with $n$ form a group under multiplication $pmod n$. By definition the order of that group is $varphi(n)$. It follows from basic group theory that $gcd(a,n)=1implies a^{varphi(n)}equiv 1pmod n$ whence that $a^{varphi(n)+1}equiv apmod n$
Note, however, that this argument only applies to residue classes prime to $n$. The claim you assert isn't true generally. For example, let $n=4,a=2$. We claim that, for $k>1$, the congruence $x^kequiv 2pmod 4$ has no solution. Indeed, we just go case by case. if $xequiv 0 $ then $x^kequiv 0$, if $xequiv 1$ then $x^kequiv 1$, if $xequiv 2$ then $x^kequiv 0$ (since $k>1$), and if $xequiv 3$ then $x^kequiv (-1)^knot equiv 0$.
answered Jan 11 at 21:15
lulululu
40.1k24778
$endgroup$
add a comment |
$begingroup$
If $gcd(a,n)=1$ then $a$ is invertible $pmod n$, by Bezout's Lemma. Indeed the set of residues coprime with $n$ form a group under multiplication $pmod n$. By definition the order of that group is $varphi(n)$. It follows from basic group theory that $gcd(a,n)=1implies a^{varphi(n)}equiv 1pmod n$ whence that $a^{varphi(n)+1}equiv apmod n$
Note, however, that this argument only applies to residue classes prime to $n$. The claim you assert isn't true generally. For example, let $n=4,a=2$. We claim that, for $k>1$, the congruence $x^kequiv 2pmod 4$ has no solution. Indeed, we just go case by case. if $xequiv 0 $ then $x^kequiv 0$, if $xequiv 1$ then $x^kequiv 1$, if $xequiv 2$ then $x^kequiv 0$ (since $k>1$), and if $xequiv 3$ then $x^kequiv (-1)^knot equiv 0$.
answered Jan 11 at 21:15
lulululu
40.1k24778
$endgroup$
add a comment |
$begingroup$
If $gcd(a,n)=1$ then $a$ is invertible $pmod n$, by Bezout's Lemma. Indeed the set of residues coprime with $n$ form a group under multiplication $pmod n$. By definition the order of that group is $varphi(n)$. It follows from basic group theory that $gcd(a,n)=1implies a^{varphi(n)}equiv 1pmod n$ whence that $a^{varphi(n)+1}equiv apmod n$
Note, however, that this argument only applies to residue classes prime to $n$. The claim you assert isn't true generally. For example, let $n=4,a=2$. We claim that, for $k>1$, the congruence $x^kequiv 2pmod 4$ has no solution. Indeed, we just go case by case. if $xequiv 0 $ then $x^kequiv 0$, if $xequiv 1$ then $x^kequiv 1$, if $xequiv 2$ then $x^kequiv 0$ (since $k>1$), and if $xequiv 3$ then $x^kequiv (-1)^knot equiv 0$.
answered Jan 11 at 21:15
lulululu
40.1k24778
$endgroup$
If $gcd(a,n)=1$ then $a$ is invertible $pmod n$, by Bezout's Lemma. Indeed the set of residues coprime with $n$ form a group under multiplication $pmod n$. By definition the order of that group is $varphi(n)$. It follows from basic group theory that $gcd(a,n)=1implies a^{varphi(n)}equiv 1pmod n$ whence that $a^{varphi(n)+1}equiv apmod n$
Note, however, that this argument only applies to residue classes prime to $n$. The claim you assert isn't true generally. For example, let $n=4,a=2$. We claim that, for $k>1$, the congruence $x^kequiv 2pmod 4$ has no solution. Indeed, we just go case by case. if $xequiv 0 $ then $x^kequiv 0$, if $xequiv 1$ then $x^kequiv 1$, if $xequiv 2$ then $x^kequiv 0$ (since $k>1$), and if $xequiv 3$ then $x^kequiv (-1)^knot equiv 0$.
answered Jan 11 at 21:15
lulululu
40.1k24778
answered Jan 11 at 21:15
lulululu
40.1k24778
answered Jan 11 at 21:15
lulululu
40.1k24778
answered Jan 11 at 21:15
lulululu
40.1k24778
40.1k24778
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%2f3070338%2fa-question-concerning-higher-residues-quadratic-and-so-on%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$
That argument only works for those classes prime to $n$. If, say, you let $n=4, a=2$ there is no $k>1$ for which $x^kequiv 2pmod 4$ has a solution.
$endgroup$
– lulu
Jan 11 at 21:04
$begingroup$
@lulu: Which "classes prime to $n$" do you mean? I only know "numbers coprime to $n$".
$endgroup$
– Hans Stricker
Jan 11 at 21:09
$begingroup$
Same thing. I mean the numbers coprime to $n$.
$endgroup$
– lulu
Jan 11 at 21:14