Let the divisors of $p-1$ be $d_1,d_2,cdots$Let $g mod p$ be a primitive root ,then for each $d_i$ there is...
$begingroup$
I am trying,without success,to prove this statement:
Let the divisors of $p-1$ be $d_1,d_2,cdots$ Prove that if we have a
primitive root $g mod p$ ,then for each $d_i$ there is an element
with period $d_i$
I am trying,without success,to prove this statement:
Let the divisors of $p-1$ be $d_1,d_2,cdots$ Prove that if we have a
primitive root $g mod p$ ,then for each $d_i$ there is an element
with period $d_i$
My thinking:
It's given that $g$ is a primitive root ,now let $g=a^t$ where $a$ is not a multiple of $p$ and $t$ is some real number ,so we have that $a^{t},a^{2t},a^{3t},cdots equiv 1 mod p$
Now I know that from Fermat we have $a^{p-1} equiv 1 mod p$, so $p-1=tcdot k $ for some integer $k$.
Since we have that each of $d_i$ is a divisor of $p-1$ we have that $p-1=d_i cdot q $ where $q$ is an integer,then $d_i cdot q =tcdot k$ so I have that $$ a^{d_i}=a^{tk/q} =(a^{tk})^{1/q}$$
Since we have $a^{tk}equiv 1 mod p $ we have also that $left(a^{tk}right)^{1/q} equiv 1^{1/q} equiv 1 mod p$
Now I don't know what should I do now ,I am terribly confused (I haven't someone to ask for advice)
elementary-number-theory
asked Jan 15 '16 at 13:19
Mr. YMr. Y
1,369721
$endgroup$
|
show 6 more comments
$begingroup$
I am trying,without success,to prove this statement:
Let the divisors of $p-1$ be $d_1,d_2,cdots$ Prove that if we have a
primitive root $g mod p$ ,then for each $d_i$ there is an element
with period $d_i$
I am trying,without success,to prove this statement:
Let the divisors of $p-1$ be $d_1,d_2,cdots$ Prove that if we have a
primitive root $g mod p$ ,then for each $d_i$ there is an element
with period $d_i$
My thinking:
It's given that $g$ is a primitive root ,now let $g=a^t$ where $a$ is not a multiple of $p$ and $t$ is some real number ,so we have that $a^{t},a^{2t},a^{3t},cdots equiv 1 mod p$
Now I know that from Fermat we have $a^{p-1} equiv 1 mod p$, so $p-1=tcdot k $ for some integer $k$.
Since we have that each of $d_i$ is a divisor of $p-1$ we have that $p-1=d_i cdot q $ where $q$ is an integer,then $d_i cdot q =tcdot k$ so I have that $$ a^{d_i}=a^{tk/q} =(a^{tk})^{1/q}$$
Since we have $a^{tk}equiv 1 mod p $ we have also that $left(a^{tk}right)^{1/q} equiv 1^{1/q} equiv 1 mod p$
Now I don't know what should I do now ,I am terribly confused (I haven't someone to ask for advice)
elementary-number-theory
asked Jan 15 '16 at 13:19
Mr. YMr. Y
1,369721
$endgroup$
1
$begingroup$
What is $a$ and $t$? Also, $1^{1/q}$ need not be equal to $1$ modulo something.
$endgroup$
– Wojowu
Jan 15 '16 at 13:24
$begingroup$
Yes I've confused it all ,$t=p-1$ and $a$ is some integer which is not congruent to $0 mod p$
$endgroup$
– Mr. Y
Jan 15 '16 at 13:34
$begingroup$
In that case, $g=a^t$ never holds for $p>2$, because $a^tequiv 1$ and $gnotequiv 1$.
$endgroup$
– Wojowu
Jan 15 '16 at 13:37
$begingroup$
Can't I have $g=a^{t}$ for some real $t$ ?
$endgroup$
– Mr. Y
Jan 15 '16 at 13:45
1
$begingroup$
It isn't at all useful to consider real exponentiation for congruence problems, because it's not true that if $aequiv bmod p$, then $a^t=b^tmod p$. Instead, I would suggest you looking at the integer powers of $g$ itself.
$endgroup$
– Wojowu
Jan 15 '16 at 13:56
|
show 6 more comments
$begingroup$
I am trying,without success,to prove this statement:
Let the divisors of $p-1$ be $d_1,d_2,cdots$ Prove that if we have a
primitive root $g mod p$ ,then for each $d_i$ there is an element
with period $d_i$
I am trying,without success,to prove this statement:
Let the divisors of $p-1$ be $d_1,d_2,cdots$ Prove that if we have a
primitive root $g mod p$ ,then for each $d_i$ there is an element
with period $d_i$
My thinking:
It's given that $g$ is a primitive root ,now let $g=a^t$ where $a$ is not a multiple of $p$ and $t$ is some real number ,so we have that $a^{t},a^{2t},a^{3t},cdots equiv 1 mod p$
Now I know that from Fermat we have $a^{p-1} equiv 1 mod p$, so $p-1=tcdot k $ for some integer $k$.
Since we have that each of $d_i$ is a divisor of $p-1$ we have that $p-1=d_i cdot q $ where $q$ is an integer,then $d_i cdot q =tcdot k$ so I have that $$ a^{d_i}=a^{tk/q} =(a^{tk})^{1/q}$$
Since we have $a^{tk}equiv 1 mod p $ we have also that $left(a^{tk}right)^{1/q} equiv 1^{1/q} equiv 1 mod p$
Now I don't know what should I do now ,I am terribly confused (I haven't someone to ask for advice)
elementary-number-theory
asked Jan 15 '16 at 13:19
Mr. YMr. Y
1,369721
$endgroup$
I am trying,without success,to prove this statement:
Let the divisors of $p-1$ be $d_1,d_2,cdots$ Prove that if we have a
primitive root $g mod p$ ,then for each $d_i$ there is an element
with period $d_i$
I am trying,without success,to prove this statement:
Let the divisors of $p-1$ be $d_1,d_2,cdots$ Prove that if we have a
primitive root $g mod p$ ,then for each $d_i$ there is an element
with period $d_i$
My thinking:
It's given that $g$ is a primitive root ,now let $g=a^t$ where $a$ is not a multiple of $p$ and $t$ is some real number ,so we have that $a^{t},a^{2t},a^{3t},cdots equiv 1 mod p$
Now I know that from Fermat we have $a^{p-1} equiv 1 mod p$, so $p-1=tcdot k $ for some integer $k$.
Since we have that each of $d_i$ is a divisor of $p-1$ we have that $p-1=d_i cdot q $ where $q$ is an integer,then $d_i cdot q =tcdot k$ so I have that $$ a^{d_i}=a^{tk/q} =(a^{tk})^{1/q}$$
Since we have $a^{tk}equiv 1 mod p $ we have also that $left(a^{tk}right)^{1/q} equiv 1^{1/q} equiv 1 mod p$
Now I don't know what should I do now ,I am terribly confused (I haven't someone to ask for advice)
elementary-number-theory
elementary-number-theory
asked Jan 15 '16 at 13:19
Mr. YMr. Y
1,369721
asked Jan 15 '16 at 13:19
Mr. YMr. Y
1,369721
edited Jan 15 '16 at 13:54
Mr. Y
asked Jan 15 '16 at 13:19
Mr. YMr. Y
1,369721
asked Jan 15 '16 at 13:19
Mr. YMr. Y
1,369721
asked Jan 15 '16 at 13:19
Mr. YMr. Y
1,369721
1,369721
1
$begingroup$
What is $a$ and $t$? Also, $1^{1/q}$ need not be equal to $1$ modulo something.
$endgroup$
– Wojowu
Jan 15 '16 at 13:24
$begingroup$
Yes I've confused it all ,$t=p-1$ and $a$ is some integer which is not congruent to $0 mod p$
$endgroup$
– Mr. Y
Jan 15 '16 at 13:34
$begingroup$
In that case, $g=a^t$ never holds for $p>2$, because $a^tequiv 1$ and $gnotequiv 1$.
$endgroup$
– Wojowu
Jan 15 '16 at 13:37
$begingroup$
Can't I have $g=a^{t}$ for some real $t$ ?
$endgroup$
– Mr. Y
Jan 15 '16 at 13:45
1
$begingroup$
It isn't at all useful to consider real exponentiation for congruence problems, because it's not true that if $aequiv bmod p$, then $a^t=b^tmod p$. Instead, I would suggest you looking at the integer powers of $g$ itself.
$endgroup$
– Wojowu
Jan 15 '16 at 13:56
|
show 6 more comments
1
$begingroup$
What is $a$ and $t$? Also, $1^{1/q}$ need not be equal to $1$ modulo something.
$endgroup$
– Wojowu
Jan 15 '16 at 13:24
$begingroup$
Yes I've confused it all ,$t=p-1$ and $a$ is some integer which is not congruent to $0 mod p$
$endgroup$
– Mr. Y
Jan 15 '16 at 13:34
$begingroup$
In that case, $g=a^t$ never holds for $p>2$, because $a^tequiv 1$ and $gnotequiv 1$.
$endgroup$
– Wojowu
Jan 15 '16 at 13:37
$begingroup$
Can't I have $g=a^{t}$ for some real $t$ ?
$endgroup$
– Mr. Y
Jan 15 '16 at 13:45
1
$begingroup$
It isn't at all useful to consider real exponentiation for congruence problems, because it's not true that if $aequiv bmod p$, then $a^t=b^tmod p$. Instead, I would suggest you looking at the integer powers of $g$ itself.
$endgroup$
– Wojowu
Jan 15 '16 at 13:56
1
1
$begingroup$
What is $a$ and $t$? Also, $1^{1/q}$ need not be equal to $1$ modulo something.
$endgroup$
– Wojowu
Jan 15 '16 at 13:24
$begingroup$
What is $a$ and $t$? Also, $1^{1/q}$ need not be equal to $1$ modulo something.
$endgroup$
– Wojowu
Jan 15 '16 at 13:24
$begingroup$
Yes I've confused it all ,$t=p-1$ and $a$ is some integer which is not congruent to $0 mod p$
$endgroup$
– Mr. Y
Jan 15 '16 at 13:34
$begingroup$
Yes I've confused it all ,$t=p-1$ and $a$ is some integer which is not congruent to $0 mod p$
$endgroup$
– Mr. Y
Jan 15 '16 at 13:34
$begingroup$
In that case, $g=a^t$ never holds for $p>2$, because $a^tequiv 1$ and $gnotequiv 1$.
$endgroup$
– Wojowu
Jan 15 '16 at 13:37
$begingroup$
In that case, $g=a^t$ never holds for $p>2$, because $a^tequiv 1$ and $gnotequiv 1$.
$endgroup$
– Wojowu
Jan 15 '16 at 13:37
$begingroup$
Can't I have $g=a^{t}$ for some real $t$ ?
$endgroup$
– Mr. Y
Jan 15 '16 at 13:45
$begingroup$
Can't I have $g=a^{t}$ for some real $t$ ?
$endgroup$
– Mr. Y
Jan 15 '16 at 13:45
1
1
$begingroup$
It isn't at all useful to consider real exponentiation for congruence problems, because it's not true that if $aequiv bmod p$, then $a^t=b^tmod p$. Instead, I would suggest you looking at the integer powers of $g$ itself.
$endgroup$
– Wojowu
Jan 15 '16 at 13:56
$begingroup$
It isn't at all useful to consider real exponentiation for congruence problems, because it's not true that if $aequiv bmod p$, then $a^t=b^tmod p$. Instead, I would suggest you looking at the integer powers of $g$ itself.
$endgroup$
– Wojowu
Jan 15 '16 at 13:56
|
show 6 more comments
1 Answer
1
active
oldest
votes
$begingroup$
It's a much more general fact. If $g$ is an element of period $n$ in a group, and $m$ divides $n$, then the period of $g^{n/m}$ is $m$.
Even more generally, when $k$ is arbitrary, then the period of $g^{k}$ is
$$
frac{n}{gcd(n, k)}.
$$
Proof of the first statement.
For $1 le k < m$, we have $(n/m) cdot k < n$, so
$(g^{n/m})^{k} = g^{(n/m)cdot k} ne 1$. However $(g^{n/m})^{m} = g^{(n/m) cdot m} = g^{n} = 1$, so the period of $g^{n/m}$ is exactly $m$.
answered Jan 15 '16 at 13:58
Andreas CarantiAndreas Caranti
56.6k34395
$endgroup$
$begingroup$
If it's not too much disturb,where can I see the proof of this ?
$endgroup$
– Mr. Y
Jan 15 '16 at 14:22
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%2f1613325%2flet-the-divisors-of-p-1-be-d-1-d-2-cdotslet-g-mod-p-be-a-primitive-root%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$
It's a much more general fact. If $g$ is an element of period $n$ in a group, and $m$ divides $n$, then the period of $g^{n/m}$ is $m$.
Even more generally, when $k$ is arbitrary, then the period of $g^{k}$ is
$$
frac{n}{gcd(n, k)}.
$$
Proof of the first statement.
For $1 le k < m$, we have $(n/m) cdot k < n$, so
$(g^{n/m})^{k} = g^{(n/m)cdot k} ne 1$. However $(g^{n/m})^{m} = g^{(n/m) cdot m} = g^{n} = 1$, so the period of $g^{n/m}$ is exactly $m$.
answered Jan 15 '16 at 13:58
Andreas CarantiAndreas Caranti
56.6k34395
$endgroup$
$begingroup$
If it's not too much disturb,where can I see the proof of this ?
$endgroup$
– Mr. Y
Jan 15 '16 at 14:22
add a comment |
$begingroup$
It's a much more general fact. If $g$ is an element of period $n$ in a group, and $m$ divides $n$, then the period of $g^{n/m}$ is $m$.
Even more generally, when $k$ is arbitrary, then the period of $g^{k}$ is
$$
frac{n}{gcd(n, k)}.
$$
Proof of the first statement.
For $1 le k < m$, we have $(n/m) cdot k < n$, so
$(g^{n/m})^{k} = g^{(n/m)cdot k} ne 1$. However $(g^{n/m})^{m} = g^{(n/m) cdot m} = g^{n} = 1$, so the period of $g^{n/m}$ is exactly $m$.
answered Jan 15 '16 at 13:58
Andreas CarantiAndreas Caranti
56.6k34395
$endgroup$
$begingroup$
If it's not too much disturb,where can I see the proof of this ?
$endgroup$
– Mr. Y
Jan 15 '16 at 14:22
add a comment |
$begingroup$
It's a much more general fact. If $g$ is an element of period $n$ in a group, and $m$ divides $n$, then the period of $g^{n/m}$ is $m$.
Even more generally, when $k$ is arbitrary, then the period of $g^{k}$ is
$$
frac{n}{gcd(n, k)}.
$$
Proof of the first statement.
For $1 le k < m$, we have $(n/m) cdot k < n$, so
$(g^{n/m})^{k} = g^{(n/m)cdot k} ne 1$. However $(g^{n/m})^{m} = g^{(n/m) cdot m} = g^{n} = 1$, so the period of $g^{n/m}$ is exactly $m$.
answered Jan 15 '16 at 13:58
Andreas CarantiAndreas Caranti
56.6k34395
$endgroup$
It's a much more general fact. If $g$ is an element of period $n$ in a group, and $m$ divides $n$, then the period of $g^{n/m}$ is $m$.
Even more generally, when $k$ is arbitrary, then the period of $g^{k}$ is
$$
frac{n}{gcd(n, k)}.
$$
Proof of the first statement.
For $1 le k < m$, we have $(n/m) cdot k < n$, so
$(g^{n/m})^{k} = g^{(n/m)cdot k} ne 1$. However $(g^{n/m})^{m} = g^{(n/m) cdot m} = g^{n} = 1$, so the period of $g^{n/m}$ is exactly $m$.
answered Jan 15 '16 at 13:58
Andreas CarantiAndreas Caranti
56.6k34395
edited Jan 4 at 10:10
answered Jan 15 '16 at 13:58
Andreas CarantiAndreas Caranti
56.6k34395
answered Jan 15 '16 at 13:58
Andreas CarantiAndreas Caranti
56.6k34395
answered Jan 15 '16 at 13:58
Andreas CarantiAndreas Caranti
56.6k34395
56.6k34395
$begingroup$
If it's not too much disturb,where can I see the proof of this ?
$endgroup$
– Mr. Y
Jan 15 '16 at 14:22
add a comment |
$begingroup$
If it's not too much disturb,where can I see the proof of this ?
$endgroup$
– Mr. Y
Jan 15 '16 at 14:22
$begingroup$
If it's not too much disturb,where can I see the proof of this ?
$endgroup$
– Mr. Y
Jan 15 '16 at 14:22
$begingroup$
If it's not too much disturb,where can I see the proof of this ?
$endgroup$
– Mr. Y
Jan 15 '16 at 14:22
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%2f1613325%2flet-the-divisors-of-p-1-be-d-1-d-2-cdotslet-g-mod-p-be-a-primitive-root%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
1
$begingroup$
What is $a$ and $t$? Also, $1^{1/q}$ need not be equal to $1$ modulo something.
$endgroup$
– Wojowu
Jan 15 '16 at 13:24
$begingroup$
Yes I've confused it all ,$t=p-1$ and $a$ is some integer which is not congruent to $0 mod p$
$endgroup$
– Mr. Y
Jan 15 '16 at 13:34
$begingroup$
In that case, $g=a^t$ never holds for $p>2$, because $a^tequiv 1$ and $gnotequiv 1$.
$endgroup$
– Wojowu
Jan 15 '16 at 13:37
$begingroup$
Can't I have $g=a^{t}$ for some real $t$ ?
$endgroup$
– Mr. Y
Jan 15 '16 at 13:45
1
$begingroup$
It isn't at all useful to consider real exponentiation for congruence problems, because it's not true that if $aequiv bmod p$, then $a^t=b^tmod p$. Instead, I would suggest you looking at the integer powers of $g$ itself.
$endgroup$
– Wojowu
Jan 15 '16 at 13:56