Mixing
The number of solutions to $x^k = a$ over $G$ a finite cyclic group is $gcd(k,|G|)$
$begingroup$
Well this question arises from the next theorem : Let $G$ a finite cyclic group of order $n$ , then: There is a solution for $x^k = a Leftrightarrow a^frac{n}{gcd(k,n)} = e$.
I wish to show that in case there is a solution $x_0in G$, such that $x_0^k=a$, then there are exactly $gcd(k,n)$ solutions for $x^k =a$.
Well, I worked out that $a$ is a $k'th$ root in $G$ $Rightarrow$ $a$ is a $gcd(k,n)'th$ root in $G$.
An other observation is that there are exactly $frac{n}{gcd(k,n)}$ elements in $G$ which are roots of order $k$, cause in case $d||G|$, there are exactly $d$ solution for $x^d=e$.
group-theory finite-groups modular-arithmetic cyclic-groups
asked Jan 18 at 10:55
dandan
590613
$endgroup$
add a comment |
$begingroup$
Well this question arises from the next theorem : Let $G$ a finite cyclic group of order $n$ , then: There is a solution for $x^k = a Leftrightarrow a^frac{n}{gcd(k,n)} = e$.
I wish to show that in case there is a solution $x_0in G$, such that $x_0^k=a$, then there are exactly $gcd(k,n)$ solutions for $x^k =a$.
Well, I worked out that $a$ is a $k'th$ root in $G$ $Rightarrow$ $a$ is a $gcd(k,n)'th$ root in $G$.
An other observation is that there are exactly $frac{n}{gcd(k,n)}$ elements in $G$ which are roots of order $k$, cause in case $d||G|$, there are exactly $d$ solution for $x^d=e$.
group-theory finite-groups modular-arithmetic cyclic-groups
asked Jan 18 at 10:55
dandan
590613
$endgroup$
$begingroup$
Is $G$ cyclic or just finite of order $n$?
$endgroup$
– Stockfish
Jan 18 at 11:14
$begingroup$
finite and cyclic @Stockfish
$endgroup$
– dan
Jan 18 at 11:16
1
$begingroup$
Please add all information at the beginning of your post, even if it's contained in the header :)
$endgroup$
– Stockfish
Jan 18 at 11:18
$begingroup$
@Stockfish Thanks,I forgot the cyclic part when citing the theorem. =)
$endgroup$
– dan
Jan 18 at 11:19
add a comment |
$begingroup$
Well this question arises from the next theorem : Let $G$ a finite cyclic group of order $n$ , then: There is a solution for $x^k = a Leftrightarrow a^frac{n}{gcd(k,n)} = e$.
I wish to show that in case there is a solution $x_0in G$, such that $x_0^k=a$, then there are exactly $gcd(k,n)$ solutions for $x^k =a$.
Well, I worked out that $a$ is a $k'th$ root in $G$ $Rightarrow$ $a$ is a $gcd(k,n)'th$ root in $G$.
An other observation is that there are exactly $frac{n}{gcd(k,n)}$ elements in $G$ which are roots of order $k$, cause in case $d||G|$, there are exactly $d$ solution for $x^d=e$.
group-theory finite-groups modular-arithmetic cyclic-groups
asked Jan 18 at 10:55
dandan
590613
$endgroup$
Well this question arises from the next theorem : Let $G$ a finite cyclic group of order $n$ , then: There is a solution for $x^k = a Leftrightarrow a^frac{n}{gcd(k,n)} = e$.
I wish to show that in case there is a solution $x_0in G$, such that $x_0^k=a$, then there are exactly $gcd(k,n)$ solutions for $x^k =a$.
Well, I worked out that $a$ is a $k'th$ root in $G$ $Rightarrow$ $a$ is a $gcd(k,n)'th$ root in $G$.
An other observation is that there are exactly $frac{n}{gcd(k,n)}$ elements in $G$ which are roots of order $k$, cause in case $d||G|$, there are exactly $d$ solution for $x^d=e$.
group-theory finite-groups modular-arithmetic cyclic-groups
group-theory finite-groups modular-arithmetic cyclic-groups
asked Jan 18 at 10:55
dandan
590613
asked Jan 18 at 10:55
dandan
590613
edited Jan 19 at 16:19
dan
asked Jan 18 at 10:55
dandan
590613
asked Jan 18 at 10:55
dandan
590613
asked Jan 18 at 10:55
dandan
590613
590613
$begingroup$
Is $G$ cyclic or just finite of order $n$?
$endgroup$
– Stockfish
Jan 18 at 11:14
$begingroup$
finite and cyclic @Stockfish
$endgroup$
– dan
Jan 18 at 11:16
1
$begingroup$
Please add all information at the beginning of your post, even if it's contained in the header :)
$endgroup$
– Stockfish
Jan 18 at 11:18
$begingroup$
@Stockfish Thanks,I forgot the cyclic part when citing the theorem. =)
$endgroup$
– dan
Jan 18 at 11:19
add a comment |
$begingroup$
Is $G$ cyclic or just finite of order $n$?
$endgroup$
– Stockfish
Jan 18 at 11:14
$begingroup$
finite and cyclic @Stockfish
$endgroup$
– dan
Jan 18 at 11:16
1
$begingroup$
Please add all information at the beginning of your post, even if it's contained in the header :)
$endgroup$
– Stockfish
Jan 18 at 11:18
$begingroup$
@Stockfish Thanks,I forgot the cyclic part when citing the theorem. =)
$endgroup$
– dan
Jan 18 at 11:19
$begingroup$
Is $G$ cyclic or just finite of order $n$?
$endgroup$
– Stockfish
Jan 18 at 11:14
$begingroup$
Is $G$ cyclic or just finite of order $n$?
$endgroup$
– Stockfish
Jan 18 at 11:14
$begingroup$
finite and cyclic @Stockfish
$endgroup$
– dan
Jan 18 at 11:16
$begingroup$
finite and cyclic @Stockfish
$endgroup$
– dan
Jan 18 at 11:16
1
1
$begingroup$
Please add all information at the beginning of your post, even if it's contained in the header :)
$endgroup$
– Stockfish
Jan 18 at 11:18
$begingroup$
Please add all information at the beginning of your post, even if it's contained in the header :)
$endgroup$
– Stockfish
Jan 18 at 11:18
$begingroup$
@Stockfish Thanks,I forgot the cyclic part when citing the theorem. =)
$endgroup$
– dan
Jan 18 at 11:19
$begingroup$
@Stockfish Thanks,I forgot the cyclic part when citing the theorem. =)
$endgroup$
– dan
Jan 18 at 11:19
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Let $g$ be any generator of the group $G$. Then, for some $i$ we must have $x_0=g^i$. This $i$ will be fixed throughout the rest of the answer.
Since $x_0^k=a$, $(g^i)^k=aimplies g^{ik}=a$. We can also see that the order of the element $g$ is $n$ (since $g$ generates $G$, a group of order $n$).
As a result, notice that any other representation of $a$ as a power $g$, like, say $g^m=a$ will satisfy $n|(ik-m)$ as we can write $g^{ik}=g^mimplies g^{ik}*(g^m)^{-1}=eimplies g^{ik-m}=eimplies operatorname{ord}(g)|(ik-m)$.
So suppose for some $yin G$ (that may or may not be equal to $x_0$), we have $y^k=a$.
We can write $y$ as $g^j$, where $0leq j< n$ so that $g^{jk}=a$.
This means (referring back to the "As a result..." line):
$$n|(ik-jk)implies n|k(i-j)impliesfrac{n}{g.c.d(n,k)}Big|frac{k}{g.c.d(n,k)}(i-j)$$
But $frac{n}{g.c.d(n,k)}$ and $frac{k}{g.c.d(n,k)}$ are coprime (we have divided out their greatest common factor) so
$frac{n}{g.c.d(n,k)}Big|(i-j)$.
On the other hand, suppose we are given some $0leq j< n$ such that $frac{n}{g.c.d(n,k)}Big|(i-j)$. Then
$$g^{ik-jk}=g^{(i-j)k}=g^{(frac{n}{g.c.d(n,k)}s)k}=(g^n)^{sfrac{k}{g.c.d(n,k)}}=e^{sfrac{k}{g.c.d(n,k)}}=e$$
So $$g^{ik}=g^{jk}implies (g^j)^k=a$$
(above we have used $s=frac{n}{g.c.d(n,k)}/(i-j)$).
Each element in $G$ can be represented uniquely as a power of $g$ between $0$ and $n-1$. So what we have shown is that $g^j$ is a $k$th root of $a$ (aside from $x_0$) iff $frac{n}{g.c.d(n,k)}Big|(i-j)$. This means we can consider all distinct values of $joperatorname{mod}n$ such that $j=i-sfrac{n}{g.c.d(n,k)}$ (where $s$ is some integer), and $g^j$ will give us all the corresponding $k$th roots of $a$.
Now, what you say that you wish to show is equivalent to saying that there is some group of $g.c.d(n,k)$ integers which we can plug in in place of $s$ in the above expression to generate values of $j$ that are distinct $operatorname{mod}n$.
This is equivalent to saying $g.c.d(n,k)jequiv g.c.d(n,k)i;operatorname{mod}n$ has exactly $g.c.d(n,k)$ mutually incongruent solutions in $j$.
Lucky for us, we know that, in general, $axequiv boperatorname{mod}n$ has exactly $g.c.d(a,n)$ mutually incongruent solutions in $x$ (assuming $g.c.d(a,n)|b$) (you can find more info here)
So the equation $g.c.d(n,k)jequiv g.c.d(n,k)i;operatorname{mod}n$ has exactly $g.c.d(n,g.c.d(n,k))=g.c.d(n,k)$ solutions in $j$, giving us exactly $g.c.d(n,k)$ corresponding $k$th roots of $a$, as desired.
(please comment or edit for any corrections)
answered Jan 19 at 18:59
Cardioid_Ass_22Cardioid_Ass_22
40814
$endgroup$
1
$begingroup$
Thanks for the clear and detailed answer!
$endgroup$
– dan
Jan 20 at 10:43
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%2f3078090%2fthe-number-of-solutions-to-xk-a-over-g-a-finite-cyclic-group-is-gcdk%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$
Let $g$ be any generator of the group $G$. Then, for some $i$ we must have $x_0=g^i$. This $i$ will be fixed throughout the rest of the answer.
Since $x_0^k=a$, $(g^i)^k=aimplies g^{ik}=a$. We can also see that the order of the element $g$ is $n$ (since $g$ generates $G$, a group of order $n$).
As a result, notice that any other representation of $a$ as a power $g$, like, say $g^m=a$ will satisfy $n|(ik-m)$ as we can write $g^{ik}=g^mimplies g^{ik}*(g^m)^{-1}=eimplies g^{ik-m}=eimplies operatorname{ord}(g)|(ik-m)$.
So suppose for some $yin G$ (that may or may not be equal to $x_0$), we have $y^k=a$.
We can write $y$ as $g^j$, where $0leq j< n$ so that $g^{jk}=a$.
This means (referring back to the "As a result..." line):
$$n|(ik-jk)implies n|k(i-j)impliesfrac{n}{g.c.d(n,k)}Big|frac{k}{g.c.d(n,k)}(i-j)$$
But $frac{n}{g.c.d(n,k)}$ and $frac{k}{g.c.d(n,k)}$ are coprime (we have divided out their greatest common factor) so
$frac{n}{g.c.d(n,k)}Big|(i-j)$.
On the other hand, suppose we are given some $0leq j< n$ such that $frac{n}{g.c.d(n,k)}Big|(i-j)$. Then
$$g^{ik-jk}=g^{(i-j)k}=g^{(frac{n}{g.c.d(n,k)}s)k}=(g^n)^{sfrac{k}{g.c.d(n,k)}}=e^{sfrac{k}{g.c.d(n,k)}}=e$$
So $$g^{ik}=g^{jk}implies (g^j)^k=a$$
(above we have used $s=frac{n}{g.c.d(n,k)}/(i-j)$).
Each element in $G$ can be represented uniquely as a power of $g$ between $0$ and $n-1$. So what we have shown is that $g^j$ is a $k$th root of $a$ (aside from $x_0$) iff $frac{n}{g.c.d(n,k)}Big|(i-j)$. This means we can consider all distinct values of $joperatorname{mod}n$ such that $j=i-sfrac{n}{g.c.d(n,k)}$ (where $s$ is some integer), and $g^j$ will give us all the corresponding $k$th roots of $a$.
Now, what you say that you wish to show is equivalent to saying that there is some group of $g.c.d(n,k)$ integers which we can plug in in place of $s$ in the above expression to generate values of $j$ that are distinct $operatorname{mod}n$.
This is equivalent to saying $g.c.d(n,k)jequiv g.c.d(n,k)i;operatorname{mod}n$ has exactly $g.c.d(n,k)$ mutually incongruent solutions in $j$.
Lucky for us, we know that, in general, $axequiv boperatorname{mod}n$ has exactly $g.c.d(a,n)$ mutually incongruent solutions in $x$ (assuming $g.c.d(a,n)|b$) (you can find more info here)
So the equation $g.c.d(n,k)jequiv g.c.d(n,k)i;operatorname{mod}n$ has exactly $g.c.d(n,g.c.d(n,k))=g.c.d(n,k)$ solutions in $j$, giving us exactly $g.c.d(n,k)$ corresponding $k$th roots of $a$, as desired.
(please comment or edit for any corrections)
answered Jan 19 at 18:59
Cardioid_Ass_22Cardioid_Ass_22
40814
$endgroup$
1
$begingroup$
Thanks for the clear and detailed answer!
$endgroup$
– dan
Jan 20 at 10:43
add a comment |
$begingroup$
Let $g$ be any generator of the group $G$. Then, for some $i$ we must have $x_0=g^i$. This $i$ will be fixed throughout the rest of the answer.
Since $x_0^k=a$, $(g^i)^k=aimplies g^{ik}=a$. We can also see that the order of the element $g$ is $n$ (since $g$ generates $G$, a group of order $n$).
As a result, notice that any other representation of $a$ as a power $g$, like, say $g^m=a$ will satisfy $n|(ik-m)$ as we can write $g^{ik}=g^mimplies g^{ik}*(g^m)^{-1}=eimplies g^{ik-m}=eimplies operatorname{ord}(g)|(ik-m)$.
So suppose for some $yin G$ (that may or may not be equal to $x_0$), we have $y^k=a$.
We can write $y$ as $g^j$, where $0leq j< n$ so that $g^{jk}=a$.
This means (referring back to the "As a result..." line):
$$n|(ik-jk)implies n|k(i-j)impliesfrac{n}{g.c.d(n,k)}Big|frac{k}{g.c.d(n,k)}(i-j)$$
But $frac{n}{g.c.d(n,k)}$ and $frac{k}{g.c.d(n,k)}$ are coprime (we have divided out their greatest common factor) so
$frac{n}{g.c.d(n,k)}Big|(i-j)$.
On the other hand, suppose we are given some $0leq j< n$ such that $frac{n}{g.c.d(n,k)}Big|(i-j)$. Then
$$g^{ik-jk}=g^{(i-j)k}=g^{(frac{n}{g.c.d(n,k)}s)k}=(g^n)^{sfrac{k}{g.c.d(n,k)}}=e^{sfrac{k}{g.c.d(n,k)}}=e$$
So $$g^{ik}=g^{jk}implies (g^j)^k=a$$
(above we have used $s=frac{n}{g.c.d(n,k)}/(i-j)$).
Each element in $G$ can be represented uniquely as a power of $g$ between $0$ and $n-1$. So what we have shown is that $g^j$ is a $k$th root of $a$ (aside from $x_0$) iff $frac{n}{g.c.d(n,k)}Big|(i-j)$. This means we can consider all distinct values of $joperatorname{mod}n$ such that $j=i-sfrac{n}{g.c.d(n,k)}$ (where $s$ is some integer), and $g^j$ will give us all the corresponding $k$th roots of $a$.
Now, what you say that you wish to show is equivalent to saying that there is some group of $g.c.d(n,k)$ integers which we can plug in in place of $s$ in the above expression to generate values of $j$ that are distinct $operatorname{mod}n$.
This is equivalent to saying $g.c.d(n,k)jequiv g.c.d(n,k)i;operatorname{mod}n$ has exactly $g.c.d(n,k)$ mutually incongruent solutions in $j$.
Lucky for us, we know that, in general, $axequiv boperatorname{mod}n$ has exactly $g.c.d(a,n)$ mutually incongruent solutions in $x$ (assuming $g.c.d(a,n)|b$) (you can find more info here)
So the equation $g.c.d(n,k)jequiv g.c.d(n,k)i;operatorname{mod}n$ has exactly $g.c.d(n,g.c.d(n,k))=g.c.d(n,k)$ solutions in $j$, giving us exactly $g.c.d(n,k)$ corresponding $k$th roots of $a$, as desired.
(please comment or edit for any corrections)
answered Jan 19 at 18:59
Cardioid_Ass_22Cardioid_Ass_22
40814
$endgroup$
1
$begingroup$
Thanks for the clear and detailed answer!
$endgroup$
– dan
Jan 20 at 10:43
add a comment |
$begingroup$
Let $g$ be any generator of the group $G$. Then, for some $i$ we must have $x_0=g^i$. This $i$ will be fixed throughout the rest of the answer.
Since $x_0^k=a$, $(g^i)^k=aimplies g^{ik}=a$. We can also see that the order of the element $g$ is $n$ (since $g$ generates $G$, a group of order $n$).
As a result, notice that any other representation of $a$ as a power $g$, like, say $g^m=a$ will satisfy $n|(ik-m)$ as we can write $g^{ik}=g^mimplies g^{ik}*(g^m)^{-1}=eimplies g^{ik-m}=eimplies operatorname{ord}(g)|(ik-m)$.
So suppose for some $yin G$ (that may or may not be equal to $x_0$), we have $y^k=a$.
We can write $y$ as $g^j$, where $0leq j< n$ so that $g^{jk}=a$.
This means (referring back to the "As a result..." line):
$$n|(ik-jk)implies n|k(i-j)impliesfrac{n}{g.c.d(n,k)}Big|frac{k}{g.c.d(n,k)}(i-j)$$
But $frac{n}{g.c.d(n,k)}$ and $frac{k}{g.c.d(n,k)}$ are coprime (we have divided out their greatest common factor) so
$frac{n}{g.c.d(n,k)}Big|(i-j)$.
On the other hand, suppose we are given some $0leq j< n$ such that $frac{n}{g.c.d(n,k)}Big|(i-j)$. Then
$$g^{ik-jk}=g^{(i-j)k}=g^{(frac{n}{g.c.d(n,k)}s)k}=(g^n)^{sfrac{k}{g.c.d(n,k)}}=e^{sfrac{k}{g.c.d(n,k)}}=e$$
So $$g^{ik}=g^{jk}implies (g^j)^k=a$$
(above we have used $s=frac{n}{g.c.d(n,k)}/(i-j)$).
Each element in $G$ can be represented uniquely as a power of $g$ between $0$ and $n-1$. So what we have shown is that $g^j$ is a $k$th root of $a$ (aside from $x_0$) iff $frac{n}{g.c.d(n,k)}Big|(i-j)$. This means we can consider all distinct values of $joperatorname{mod}n$ such that $j=i-sfrac{n}{g.c.d(n,k)}$ (where $s$ is some integer), and $g^j$ will give us all the corresponding $k$th roots of $a$.
Now, what you say that you wish to show is equivalent to saying that there is some group of $g.c.d(n,k)$ integers which we can plug in in place of $s$ in the above expression to generate values of $j$ that are distinct $operatorname{mod}n$.
This is equivalent to saying $g.c.d(n,k)jequiv g.c.d(n,k)i;operatorname{mod}n$ has exactly $g.c.d(n,k)$ mutually incongruent solutions in $j$.
Lucky for us, we know that, in general, $axequiv boperatorname{mod}n$ has exactly $g.c.d(a,n)$ mutually incongruent solutions in $x$ (assuming $g.c.d(a,n)|b$) (you can find more info here)
So the equation $g.c.d(n,k)jequiv g.c.d(n,k)i;operatorname{mod}n$ has exactly $g.c.d(n,g.c.d(n,k))=g.c.d(n,k)$ solutions in $j$, giving us exactly $g.c.d(n,k)$ corresponding $k$th roots of $a$, as desired.
(please comment or edit for any corrections)
answered Jan 19 at 18:59
Cardioid_Ass_22Cardioid_Ass_22
40814
$endgroup$
Let $g$ be any generator of the group $G$. Then, for some $i$ we must have $x_0=g^i$. This $i$ will be fixed throughout the rest of the answer.
Since $x_0^k=a$, $(g^i)^k=aimplies g^{ik}=a$. We can also see that the order of the element $g$ is $n$ (since $g$ generates $G$, a group of order $n$).
As a result, notice that any other representation of $a$ as a power $g$, like, say $g^m=a$ will satisfy $n|(ik-m)$ as we can write $g^{ik}=g^mimplies g^{ik}*(g^m)^{-1}=eimplies g^{ik-m}=eimplies operatorname{ord}(g)|(ik-m)$.
So suppose for some $yin G$ (that may or may not be equal to $x_0$), we have $y^k=a$.
We can write $y$ as $g^j$, where $0leq j< n$ so that $g^{jk}=a$.
This means (referring back to the "As a result..." line):
$$n|(ik-jk)implies n|k(i-j)impliesfrac{n}{g.c.d(n,k)}Big|frac{k}{g.c.d(n,k)}(i-j)$$
But $frac{n}{g.c.d(n,k)}$ and $frac{k}{g.c.d(n,k)}$ are coprime (we have divided out their greatest common factor) so
$frac{n}{g.c.d(n,k)}Big|(i-j)$.
On the other hand, suppose we are given some $0leq j< n$ such that $frac{n}{g.c.d(n,k)}Big|(i-j)$. Then
$$g^{ik-jk}=g^{(i-j)k}=g^{(frac{n}{g.c.d(n,k)}s)k}=(g^n)^{sfrac{k}{g.c.d(n,k)}}=e^{sfrac{k}{g.c.d(n,k)}}=e$$
So $$g^{ik}=g^{jk}implies (g^j)^k=a$$
(above we have used $s=frac{n}{g.c.d(n,k)}/(i-j)$).
Each element in $G$ can be represented uniquely as a power of $g$ between $0$ and $n-1$. So what we have shown is that $g^j$ is a $k$th root of $a$ (aside from $x_0$) iff $frac{n}{g.c.d(n,k)}Big|(i-j)$. This means we can consider all distinct values of $joperatorname{mod}n$ such that $j=i-sfrac{n}{g.c.d(n,k)}$ (where $s$ is some integer), and $g^j$ will give us all the corresponding $k$th roots of $a$.
Now, what you say that you wish to show is equivalent to saying that there is some group of $g.c.d(n,k)$ integers which we can plug in in place of $s$ in the above expression to generate values of $j$ that are distinct $operatorname{mod}n$.
This is equivalent to saying $g.c.d(n,k)jequiv g.c.d(n,k)i;operatorname{mod}n$ has exactly $g.c.d(n,k)$ mutually incongruent solutions in $j$.
Lucky for us, we know that, in general, $axequiv boperatorname{mod}n$ has exactly $g.c.d(a,n)$ mutually incongruent solutions in $x$ (assuming $g.c.d(a,n)|b$) (you can find more info here)
So the equation $g.c.d(n,k)jequiv g.c.d(n,k)i;operatorname{mod}n$ has exactly $g.c.d(n,g.c.d(n,k))=g.c.d(n,k)$ solutions in $j$, giving us exactly $g.c.d(n,k)$ corresponding $k$th roots of $a$, as desired.
(please comment or edit for any corrections)
answered Jan 19 at 18:59
Cardioid_Ass_22Cardioid_Ass_22
40814
edited Jan 20 at 16:54
answered Jan 19 at 18:59
Cardioid_Ass_22Cardioid_Ass_22
40814
answered Jan 19 at 18:59
Cardioid_Ass_22Cardioid_Ass_22
40814
answered Jan 19 at 18:59
Cardioid_Ass_22Cardioid_Ass_22
40814
40814
1
$begingroup$
Thanks for the clear and detailed answer!
$endgroup$
– dan
Jan 20 at 10:43
add a comment |
1
$begingroup$
Thanks for the clear and detailed answer!
$endgroup$
– dan
Jan 20 at 10:43
1
1
$begingroup$
Thanks for the clear and detailed answer!
$endgroup$
– dan
Jan 20 at 10:43
$begingroup$
Thanks for the clear and detailed answer!
$endgroup$
– dan
Jan 20 at 10:43
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%2f3078090%2fthe-number-of-solutions-to-xk-a-over-g-a-finite-cyclic-group-is-gcdk%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$
Is $G$ cyclic or just finite of order $n$?
$endgroup$
– Stockfish
Jan 18 at 11:14
$begingroup$
finite and cyclic @Stockfish
$endgroup$
– dan
Jan 18 at 11:16
1
$begingroup$
Please add all information at the beginning of your post, even if it's contained in the header :)
$endgroup$
– Stockfish
Jan 18 at 11:18
$begingroup$
@Stockfish Thanks,I forgot the cyclic part when citing the theorem. =)
$endgroup$
– dan
Jan 18 at 11:19