Assuming $g$ is a primitive root modulo a prime $p$, show that $p-g$ is a primitive root if and only if $p...
$begingroup$
Assume $g$ is a primitive root modulo a prime $p$. Show that $p-g$ is a primitive root if and only if $p equiv 1 pmod 4$.
I am studying for a number theory exam that is why I am posting a lot of questions related to primitive roots. I would really appreciate your help because they seem like really nice questions.
elementary-number-theory
$endgroup$
add a comment |
$begingroup$
Assume $g$ is a primitive root modulo a prime $p$. Show that $p-g$ is a primitive root if and only if $p equiv 1 pmod 4$.
I am studying for a number theory exam that is why I am posting a lot of questions related to primitive roots. I would really appreciate your help because they seem like really nice questions.
elementary-number-theory
$endgroup$
add a comment |
$begingroup$
Assume $g$ is a primitive root modulo a prime $p$. Show that $p-g$ is a primitive root if and only if $p equiv 1 pmod 4$.
I am studying for a number theory exam that is why I am posting a lot of questions related to primitive roots. I would really appreciate your help because they seem like really nice questions.
elementary-number-theory
$endgroup$
Assume $g$ is a primitive root modulo a prime $p$. Show that $p-g$ is a primitive root if and only if $p equiv 1 pmod 4$.
I am studying for a number theory exam that is why I am posting a lot of questions related to primitive roots. I would really appreciate your help because they seem like really nice questions.
elementary-number-theory
elementary-number-theory
edited Apr 16 '15 at 4:35
kate
5281717
5281717
asked Apr 10 '15 at 22:16
user2214user2214
1808
1808
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
We solve the first problem. The case $p=2$ is simple, so let $p$ be an odd prime.
If $pequiv 3pmod{4}$, then $p-g$ is not a primitive root of $p$. For $p-gequiv -gpmod{p}$. But $-1$ is a quadratic non-residue of $p$, and therefore $-g$ is a QR of $p$, so cannot be a primitive root of $p$.
Conversely, let $pequiv 1pmod{4}$. We show that $-g$ is a primitive root of $p$.
By Fermat's Theorem, $gequiv g^pequiv -(-g)^ppmod{p}$. But $-1$ is a QR of $p$, so $-1equiv g^{2k}equiv (-g)^{2k}pmof{p}$ for some integer $k$.
t follows that $gequiv (-g)^{2k}(-g)^ppmod{p}$. Thus $g$ is congruent to a power of $-g$. Since the powers of $g$ travel, modulo $p$, through $1,2,dots, p-1$, so do the powers of $-g$, and therefore $-g$ is a primitive root of $p$.
Remark: For other problems that you may post (and this one also) please indicate what you have tried, any progress you may have made, and where difficulties remain.
$endgroup$
$begingroup$
Thank you for solving the first question, but I believe I need some help for the 2nd one as well which seems more complicated.So since g is a primitive root mod p that we know that $g^{p-1}=1$ (mod p). We also know that if g is a primitive root then g or g+p is a primitive root of $p^2$.But How do I relate this facts to the 2nd question? @AndreNicolas
$endgroup$
– user2214
Apr 11 '15 at 20:13
1
$begingroup$
Your are welcome. Multipart questions in which the parts are not closely related often get closed quickly. I would prefer two questions, the second about primitive roots mod $p^2$. Recall that $g+kp$ is a primitive root mod $p^2$ for all but one $k$ in the interval $0$ to $p-1$.
$endgroup$
– André Nicolas
Apr 11 '15 at 22:34
add a comment |
$begingroup$
$$-g=g(-1)equiv g^{1+(p-1)/2}equiv g^{(p+1)/2}$$
We know, ord$_ma=d, $ord$_m(a^k)=dfrac d{(d,k)}$ (Proof @Page$#95$)
ord$_p g^{(p+1)/2}=dfrac{p-1}{left(p-1,dfrac{p+1}2right)}$
Now, if integer $d(>0)$ divides both, $d$ must divide $-(p-1)+2cdotdfrac{p+1}2=2$
As for odd prime $p,p-1$ is even
$left(p-1,dfrac{p+1}2right)=2$ if $dfrac{p+1}2$ is even $=2k$(say) $iff p=4k-1equiv-1pmod4$
$left(p-1,dfrac{p+1}2right)=1$ if $dfrac{p+1}2$ is odd $=2k+1$(say) $iff p=4k+1equiv1pmod4$
$endgroup$
$begingroup$
See also: math.stackexchange.com/questions/56028/…
$endgroup$
– lab bhattacharjee
Dec 6 '18 at 11:44
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%2f1229270%2fassuming-g-is-a-primitive-root-modulo-a-prime-p-show-that-p-g-is-a-primit%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
We solve the first problem. The case $p=2$ is simple, so let $p$ be an odd prime.
If $pequiv 3pmod{4}$, then $p-g$ is not a primitive root of $p$. For $p-gequiv -gpmod{p}$. But $-1$ is a quadratic non-residue of $p$, and therefore $-g$ is a QR of $p$, so cannot be a primitive root of $p$.
Conversely, let $pequiv 1pmod{4}$. We show that $-g$ is a primitive root of $p$.
By Fermat's Theorem, $gequiv g^pequiv -(-g)^ppmod{p}$. But $-1$ is a QR of $p$, so $-1equiv g^{2k}equiv (-g)^{2k}pmof{p}$ for some integer $k$.
t follows that $gequiv (-g)^{2k}(-g)^ppmod{p}$. Thus $g$ is congruent to a power of $-g$. Since the powers of $g$ travel, modulo $p$, through $1,2,dots, p-1$, so do the powers of $-g$, and therefore $-g$ is a primitive root of $p$.
Remark: For other problems that you may post (and this one also) please indicate what you have tried, any progress you may have made, and where difficulties remain.
$endgroup$
$begingroup$
Thank you for solving the first question, but I believe I need some help for the 2nd one as well which seems more complicated.So since g is a primitive root mod p that we know that $g^{p-1}=1$ (mod p). We also know that if g is a primitive root then g or g+p is a primitive root of $p^2$.But How do I relate this facts to the 2nd question? @AndreNicolas
$endgroup$
– user2214
Apr 11 '15 at 20:13
1
$begingroup$
Your are welcome. Multipart questions in which the parts are not closely related often get closed quickly. I would prefer two questions, the second about primitive roots mod $p^2$. Recall that $g+kp$ is a primitive root mod $p^2$ for all but one $k$ in the interval $0$ to $p-1$.
$endgroup$
– André Nicolas
Apr 11 '15 at 22:34
add a comment |
$begingroup$
We solve the first problem. The case $p=2$ is simple, so let $p$ be an odd prime.
If $pequiv 3pmod{4}$, then $p-g$ is not a primitive root of $p$. For $p-gequiv -gpmod{p}$. But $-1$ is a quadratic non-residue of $p$, and therefore $-g$ is a QR of $p$, so cannot be a primitive root of $p$.
Conversely, let $pequiv 1pmod{4}$. We show that $-g$ is a primitive root of $p$.
By Fermat's Theorem, $gequiv g^pequiv -(-g)^ppmod{p}$. But $-1$ is a QR of $p$, so $-1equiv g^{2k}equiv (-g)^{2k}pmof{p}$ for some integer $k$.
t follows that $gequiv (-g)^{2k}(-g)^ppmod{p}$. Thus $g$ is congruent to a power of $-g$. Since the powers of $g$ travel, modulo $p$, through $1,2,dots, p-1$, so do the powers of $-g$, and therefore $-g$ is a primitive root of $p$.
Remark: For other problems that you may post (and this one also) please indicate what you have tried, any progress you may have made, and where difficulties remain.
$endgroup$
$begingroup$
Thank you for solving the first question, but I believe I need some help for the 2nd one as well which seems more complicated.So since g is a primitive root mod p that we know that $g^{p-1}=1$ (mod p). We also know that if g is a primitive root then g or g+p is a primitive root of $p^2$.But How do I relate this facts to the 2nd question? @AndreNicolas
$endgroup$
– user2214
Apr 11 '15 at 20:13
1
$begingroup$
Your are welcome. Multipart questions in which the parts are not closely related often get closed quickly. I would prefer two questions, the second about primitive roots mod $p^2$. Recall that $g+kp$ is a primitive root mod $p^2$ for all but one $k$ in the interval $0$ to $p-1$.
$endgroup$
– André Nicolas
Apr 11 '15 at 22:34
add a comment |
$begingroup$
We solve the first problem. The case $p=2$ is simple, so let $p$ be an odd prime.
If $pequiv 3pmod{4}$, then $p-g$ is not a primitive root of $p$. For $p-gequiv -gpmod{p}$. But $-1$ is a quadratic non-residue of $p$, and therefore $-g$ is a QR of $p$, so cannot be a primitive root of $p$.
Conversely, let $pequiv 1pmod{4}$. We show that $-g$ is a primitive root of $p$.
By Fermat's Theorem, $gequiv g^pequiv -(-g)^ppmod{p}$. But $-1$ is a QR of $p$, so $-1equiv g^{2k}equiv (-g)^{2k}pmof{p}$ for some integer $k$.
t follows that $gequiv (-g)^{2k}(-g)^ppmod{p}$. Thus $g$ is congruent to a power of $-g$. Since the powers of $g$ travel, modulo $p$, through $1,2,dots, p-1$, so do the powers of $-g$, and therefore $-g$ is a primitive root of $p$.
Remark: For other problems that you may post (and this one also) please indicate what you have tried, any progress you may have made, and where difficulties remain.
$endgroup$
We solve the first problem. The case $p=2$ is simple, so let $p$ be an odd prime.
If $pequiv 3pmod{4}$, then $p-g$ is not a primitive root of $p$. For $p-gequiv -gpmod{p}$. But $-1$ is a quadratic non-residue of $p$, and therefore $-g$ is a QR of $p$, so cannot be a primitive root of $p$.
Conversely, let $pequiv 1pmod{4}$. We show that $-g$ is a primitive root of $p$.
By Fermat's Theorem, $gequiv g^pequiv -(-g)^ppmod{p}$. But $-1$ is a QR of $p$, so $-1equiv g^{2k}equiv (-g)^{2k}pmof{p}$ for some integer $k$.
t follows that $gequiv (-g)^{2k}(-g)^ppmod{p}$. Thus $g$ is congruent to a power of $-g$. Since the powers of $g$ travel, modulo $p$, through $1,2,dots, p-1$, so do the powers of $-g$, and therefore $-g$ is a primitive root of $p$.
Remark: For other problems that you may post (and this one also) please indicate what you have tried, any progress you may have made, and where difficulties remain.
edited Apr 10 '15 at 22:47
answered Apr 10 '15 at 22:40
André NicolasAndré Nicolas
452k36425810
452k36425810
$begingroup$
Thank you for solving the first question, but I believe I need some help for the 2nd one as well which seems more complicated.So since g is a primitive root mod p that we know that $g^{p-1}=1$ (mod p). We also know that if g is a primitive root then g or g+p is a primitive root of $p^2$.But How do I relate this facts to the 2nd question? @AndreNicolas
$endgroup$
– user2214
Apr 11 '15 at 20:13
1
$begingroup$
Your are welcome. Multipart questions in which the parts are not closely related often get closed quickly. I would prefer two questions, the second about primitive roots mod $p^2$. Recall that $g+kp$ is a primitive root mod $p^2$ for all but one $k$ in the interval $0$ to $p-1$.
$endgroup$
– André Nicolas
Apr 11 '15 at 22:34
add a comment |
$begingroup$
Thank you for solving the first question, but I believe I need some help for the 2nd one as well which seems more complicated.So since g is a primitive root mod p that we know that $g^{p-1}=1$ (mod p). We also know that if g is a primitive root then g or g+p is a primitive root of $p^2$.But How do I relate this facts to the 2nd question? @AndreNicolas
$endgroup$
– user2214
Apr 11 '15 at 20:13
1
$begingroup$
Your are welcome. Multipart questions in which the parts are not closely related often get closed quickly. I would prefer two questions, the second about primitive roots mod $p^2$. Recall that $g+kp$ is a primitive root mod $p^2$ for all but one $k$ in the interval $0$ to $p-1$.
$endgroup$
– André Nicolas
Apr 11 '15 at 22:34
$begingroup$
Thank you for solving the first question, but I believe I need some help for the 2nd one as well which seems more complicated.So since g is a primitive root mod p that we know that $g^{p-1}=1$ (mod p). We also know that if g is a primitive root then g or g+p is a primitive root of $p^2$.But How do I relate this facts to the 2nd question? @AndreNicolas
$endgroup$
– user2214
Apr 11 '15 at 20:13
$begingroup$
Thank you for solving the first question, but I believe I need some help for the 2nd one as well which seems more complicated.So since g is a primitive root mod p that we know that $g^{p-1}=1$ (mod p). We also know that if g is a primitive root then g or g+p is a primitive root of $p^2$.But How do I relate this facts to the 2nd question? @AndreNicolas
$endgroup$
– user2214
Apr 11 '15 at 20:13
1
1
$begingroup$
Your are welcome. Multipart questions in which the parts are not closely related often get closed quickly. I would prefer two questions, the second about primitive roots mod $p^2$. Recall that $g+kp$ is a primitive root mod $p^2$ for all but one $k$ in the interval $0$ to $p-1$.
$endgroup$
– André Nicolas
Apr 11 '15 at 22:34
$begingroup$
Your are welcome. Multipart questions in which the parts are not closely related often get closed quickly. I would prefer two questions, the second about primitive roots mod $p^2$. Recall that $g+kp$ is a primitive root mod $p^2$ for all but one $k$ in the interval $0$ to $p-1$.
$endgroup$
– André Nicolas
Apr 11 '15 at 22:34
add a comment |
$begingroup$
$$-g=g(-1)equiv g^{1+(p-1)/2}equiv g^{(p+1)/2}$$
We know, ord$_ma=d, $ord$_m(a^k)=dfrac d{(d,k)}$ (Proof @Page$#95$)
ord$_p g^{(p+1)/2}=dfrac{p-1}{left(p-1,dfrac{p+1}2right)}$
Now, if integer $d(>0)$ divides both, $d$ must divide $-(p-1)+2cdotdfrac{p+1}2=2$
As for odd prime $p,p-1$ is even
$left(p-1,dfrac{p+1}2right)=2$ if $dfrac{p+1}2$ is even $=2k$(say) $iff p=4k-1equiv-1pmod4$
$left(p-1,dfrac{p+1}2right)=1$ if $dfrac{p+1}2$ is odd $=2k+1$(say) $iff p=4k+1equiv1pmod4$
$endgroup$
$begingroup$
See also: math.stackexchange.com/questions/56028/…
$endgroup$
– lab bhattacharjee
Dec 6 '18 at 11:44
add a comment |
$begingroup$
$$-g=g(-1)equiv g^{1+(p-1)/2}equiv g^{(p+1)/2}$$
We know, ord$_ma=d, $ord$_m(a^k)=dfrac d{(d,k)}$ (Proof @Page$#95$)
ord$_p g^{(p+1)/2}=dfrac{p-1}{left(p-1,dfrac{p+1}2right)}$
Now, if integer $d(>0)$ divides both, $d$ must divide $-(p-1)+2cdotdfrac{p+1}2=2$
As for odd prime $p,p-1$ is even
$left(p-1,dfrac{p+1}2right)=2$ if $dfrac{p+1}2$ is even $=2k$(say) $iff p=4k-1equiv-1pmod4$
$left(p-1,dfrac{p+1}2right)=1$ if $dfrac{p+1}2$ is odd $=2k+1$(say) $iff p=4k+1equiv1pmod4$
$endgroup$
$begingroup$
See also: math.stackexchange.com/questions/56028/…
$endgroup$
– lab bhattacharjee
Dec 6 '18 at 11:44
add a comment |
$begingroup$
$$-g=g(-1)equiv g^{1+(p-1)/2}equiv g^{(p+1)/2}$$
We know, ord$_ma=d, $ord$_m(a^k)=dfrac d{(d,k)}$ (Proof @Page$#95$)
ord$_p g^{(p+1)/2}=dfrac{p-1}{left(p-1,dfrac{p+1}2right)}$
Now, if integer $d(>0)$ divides both, $d$ must divide $-(p-1)+2cdotdfrac{p+1}2=2$
As for odd prime $p,p-1$ is even
$left(p-1,dfrac{p+1}2right)=2$ if $dfrac{p+1}2$ is even $=2k$(say) $iff p=4k-1equiv-1pmod4$
$left(p-1,dfrac{p+1}2right)=1$ if $dfrac{p+1}2$ is odd $=2k+1$(say) $iff p=4k+1equiv1pmod4$
$endgroup$
$$-g=g(-1)equiv g^{1+(p-1)/2}equiv g^{(p+1)/2}$$
We know, ord$_ma=d, $ord$_m(a^k)=dfrac d{(d,k)}$ (Proof @Page$#95$)
ord$_p g^{(p+1)/2}=dfrac{p-1}{left(p-1,dfrac{p+1}2right)}$
Now, if integer $d(>0)$ divides both, $d$ must divide $-(p-1)+2cdotdfrac{p+1}2=2$
As for odd prime $p,p-1$ is even
$left(p-1,dfrac{p+1}2right)=2$ if $dfrac{p+1}2$ is even $=2k$(say) $iff p=4k-1equiv-1pmod4$
$left(p-1,dfrac{p+1}2right)=1$ if $dfrac{p+1}2$ is odd $=2k+1$(say) $iff p=4k+1equiv1pmod4$
answered Dec 6 '18 at 11:40
lab bhattacharjeelab bhattacharjee
225k15157275
225k15157275
$begingroup$
See also: math.stackexchange.com/questions/56028/…
$endgroup$
– lab bhattacharjee
Dec 6 '18 at 11:44
add a comment |
$begingroup$
See also: math.stackexchange.com/questions/56028/…
$endgroup$
– lab bhattacharjee
Dec 6 '18 at 11:44
$begingroup$
See also: math.stackexchange.com/questions/56028/…
$endgroup$
– lab bhattacharjee
Dec 6 '18 at 11:44
$begingroup$
See also: math.stackexchange.com/questions/56028/…
$endgroup$
– lab bhattacharjee
Dec 6 '18 at 11:44
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%2f1229270%2fassuming-g-is-a-primitive-root-modulo-a-prime-p-show-that-p-g-is-a-primit%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