Mixing
Show that if $a$ has order $3bmod p$ then $a+1$ has order $6bmod p$.
$begingroup$
Show that if $a$ has order $3bmod p$ then $a+1$ has order $6bmod p$. I know I am supposed to use primitive roots but I think this is where I am getting caught up. The definition of primitive root is "if $a$ is a least residue and the order of $abmod p$ is $phi(m)$ then $a$ is a primitive root of $m$. But I really am not sure how to use this to my advantage in solving anything.
Thanks!
number-theory
edited Aug 8 '13 at 19:05
MvG
30.8k449101
asked Aug 8 '13 at 18:08
KathyKathy
1019
$endgroup$
add a comment |
$begingroup$
Show that if $a$ has order $3bmod p$ then $a+1$ has order $6bmod p$. I know I am supposed to use primitive roots but I think this is where I am getting caught up. The definition of primitive root is "if $a$ is a least residue and the order of $abmod p$ is $phi(m)$ then $a$ is a primitive root of $m$. But I really am not sure how to use this to my advantage in solving anything.
Thanks!
number-theory
edited Aug 8 '13 at 19:05
MvG
30.8k449101
asked Aug 8 '13 at 18:08
KathyKathy
1019
$endgroup$
$begingroup$
math.stackexchange.com/questions/332325/…
$endgroup$
– Zach Teitler
Dec 14 '18 at 20:29
add a comment |
$begingroup$
Show that if $a$ has order $3bmod p$ then $a+1$ has order $6bmod p$. I know I am supposed to use primitive roots but I think this is where I am getting caught up. The definition of primitive root is "if $a$ is a least residue and the order of $abmod p$ is $phi(m)$ then $a$ is a primitive root of $m$. But I really am not sure how to use this to my advantage in solving anything.
Thanks!
number-theory
edited Aug 8 '13 at 19:05
MvG
30.8k449101
asked Aug 8 '13 at 18:08
KathyKathy
1019
$endgroup$
Show that if $a$ has order $3bmod p$ then $a+1$ has order $6bmod p$. I know I am supposed to use primitive roots but I think this is where I am getting caught up. The definition of primitive root is "if $a$ is a least residue and the order of $abmod p$ is $phi(m)$ then $a$ is a primitive root of $m$. But I really am not sure how to use this to my advantage in solving anything.
Thanks!
number-theory
number-theory
edited Aug 8 '13 at 19:05
MvG
30.8k449101
asked Aug 8 '13 at 18:08
KathyKathy
1019
edited Aug 8 '13 at 19:05
MvG
30.8k449101
asked Aug 8 '13 at 18:08
KathyKathy
1019
edited Aug 8 '13 at 19:05
MvG
30.8k449101
edited Aug 8 '13 at 19:05
MvG
30.8k449101
edited Aug 8 '13 at 19:05
MvG
30.8k449101
30.8k449101
asked Aug 8 '13 at 18:08
KathyKathy
1019
asked Aug 8 '13 at 18:08
KathyKathy
1019
asked Aug 8 '13 at 18:08
KathyKathy
1019
1019
$begingroup$
math.stackexchange.com/questions/332325/…
$endgroup$
– Zach Teitler
Dec 14 '18 at 20:29
add a comment |
$begingroup$
math.stackexchange.com/questions/332325/…
$endgroup$
– Zach Teitler
Dec 14 '18 at 20:29
$begingroup$
math.stackexchange.com/questions/332325/…
$endgroup$
– Zach Teitler
Dec 14 '18 at 20:29
$begingroup$
math.stackexchange.com/questions/332325/…
$endgroup$
– Zach Teitler
Dec 14 '18 at 20:29
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Note that if $a=1$, $a$ has order $1$. Thus, we can assume $ane1$. Furthermore, $pne2$ since no element mod $2$ has order $3$. Therefore, $-1ne1pmod{p}$.
$$
begin{align}
(a+1)^3
&=a^3+3a^2+3a+1\
&=1+3a^2+3a+1\
&=-1+3(1+a+a^2)\
&=-1+3frac{a^3-1}{a-1}\
&=-1
end{align}
$$
Therefore, $(a+1)^3=-1$ and $(a+1)^6=1$. (Shortened a la ccorn).
$$
begin{align}
(a+1)^2
&=a^2+2a+1\
&=a+(a^2+a+1)\
&=a+frac{a^3-1}{a-1}\
&=a\
&ne1
end{align}
$$
Therefore, $(a+1)^2ne1$.
Thus, $(a+1)$ has order $6$.
answered Aug 8 '13 at 18:24
robjohn♦robjohn
265k27303626
$endgroup$
1
$begingroup$
$(a+1)^6=1$ also follows easily from $(a+1)^3=-1$
$endgroup$
– ccorn
Aug 8 '13 at 18:25
1
$begingroup$
@ccorn: indeed it does, but I had already written the part for $(a+1)^6$. I guess I could shorten the answer. Thanks.
$endgroup$
– robjohn♦
Aug 8 '13 at 18:27
$begingroup$
With the edit made the (a+1)^{2} is not needed right? If it is I don't understand.
$endgroup$
– Kathy
Aug 8 '13 at 19:19
1
$begingroup$
@Kathy: we still have to show that $a+1$ doesn't have order $2$. We could argue that if $(a+1)^2=1$ and $(a+1)^3=-1$, then $a+1=-1$; that is, $a=-2$. Since $a^3=1$ we have that $-8equiv1pmod{p}$, which implies that $pmid9$, whence $p=3$. Since there are no elements of order $3$ mod $3$, we could stop. Personally, I think the argument in my answer is simpler.
$endgroup$
– robjohn♦
Aug 8 '13 at 19:38
$begingroup$
Is there a problem with this answer? Just wondering if the downvote means something needs fixing.
$endgroup$
– robjohn♦
Jan 1 at 19:45
add a comment |
$begingroup$
ord_$pa=3iff p$ divides $(a^3-1)=(a-1)(a^2+a+1)$
But $pnotmid (a-1)$ as ord_$pa=3 $
$displaystyleimplies a^2+a+1equiv0pmod p$
$displaystyleiff a(a+1)equiv-1pmod p$
Method $1:$
$implies a^3(a+1)^3equiv-1pmod pimplies (a+1)^3equiv-1$ and $(a+1)^6equiv1$
$implies $ord_$p(a+1)mid 6$ but does not divide $3$
If ord_$p(a+1)mid 2, (a+1)^2equiv1pmod p$ and $a^2(a+1)^2equiv1pmod pimplies a^2equiv1$ which is impossible as ord$_pa=3$
$implies $ord$_p(a+1)=6$
Method $2:$
$displaystyle a(a+1)equiv-1pmod piff a+1equiv (-a)^{-1}pmod p$
Again as $a^3equiv1pmod p, (-a)^3=-a^3equiv-1pmod pimplies (-a)^6equiv1implies $ord$_p(-a)=6$
Using this, ord$_p{(-a)^{-1}})=$ord$_p(-a)=6$
edited Apr 13 '17 at 12:19
Community♦
1
answered Aug 8 '13 at 18:12
lab bhattacharjeelab bhattacharjee
224k15156274
$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%2f463010%2fshow-that-if-a-has-order-3-bmod-p-then-a1-has-order-6-bmod-p%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$
Note that if $a=1$, $a$ has order $1$. Thus, we can assume $ane1$. Furthermore, $pne2$ since no element mod $2$ has order $3$. Therefore, $-1ne1pmod{p}$.
$$
begin{align}
(a+1)^3
&=a^3+3a^2+3a+1\
&=1+3a^2+3a+1\
&=-1+3(1+a+a^2)\
&=-1+3frac{a^3-1}{a-1}\
&=-1
end{align}
$$
Therefore, $(a+1)^3=-1$ and $(a+1)^6=1$. (Shortened a la ccorn).
$$
begin{align}
(a+1)^2
&=a^2+2a+1\
&=a+(a^2+a+1)\
&=a+frac{a^3-1}{a-1}\
&=a\
&ne1
end{align}
$$
Therefore, $(a+1)^2ne1$.
Thus, $(a+1)$ has order $6$.
answered Aug 8 '13 at 18:24
robjohn♦robjohn
265k27303626
$endgroup$
1
$begingroup$
$(a+1)^6=1$ also follows easily from $(a+1)^3=-1$
$endgroup$
– ccorn
Aug 8 '13 at 18:25
1
$begingroup$
@ccorn: indeed it does, but I had already written the part for $(a+1)^6$. I guess I could shorten the answer. Thanks.
$endgroup$
– robjohn♦
Aug 8 '13 at 18:27
$begingroup$
With the edit made the (a+1)^{2} is not needed right? If it is I don't understand.
$endgroup$
– Kathy
Aug 8 '13 at 19:19
1
$begingroup$
@Kathy: we still have to show that $a+1$ doesn't have order $2$. We could argue that if $(a+1)^2=1$ and $(a+1)^3=-1$, then $a+1=-1$; that is, $a=-2$. Since $a^3=1$ we have that $-8equiv1pmod{p}$, which implies that $pmid9$, whence $p=3$. Since there are no elements of order $3$ mod $3$, we could stop. Personally, I think the argument in my answer is simpler.
$endgroup$
– robjohn♦
Aug 8 '13 at 19:38
$begingroup$
Is there a problem with this answer? Just wondering if the downvote means something needs fixing.
$endgroup$
– robjohn♦
Jan 1 at 19:45
add a comment |
$begingroup$
Note that if $a=1$, $a$ has order $1$. Thus, we can assume $ane1$. Furthermore, $pne2$ since no element mod $2$ has order $3$. Therefore, $-1ne1pmod{p}$.
$$
begin{align}
(a+1)^3
&=a^3+3a^2+3a+1\
&=1+3a^2+3a+1\
&=-1+3(1+a+a^2)\
&=-1+3frac{a^3-1}{a-1}\
&=-1
end{align}
$$
Therefore, $(a+1)^3=-1$ and $(a+1)^6=1$. (Shortened a la ccorn).
$$
begin{align}
(a+1)^2
&=a^2+2a+1\
&=a+(a^2+a+1)\
&=a+frac{a^3-1}{a-1}\
&=a\
&ne1
end{align}
$$
Therefore, $(a+1)^2ne1$.
Thus, $(a+1)$ has order $6$.
answered Aug 8 '13 at 18:24
robjohn♦robjohn
265k27303626
$endgroup$
1
$begingroup$
$(a+1)^6=1$ also follows easily from $(a+1)^3=-1$
$endgroup$
– ccorn
Aug 8 '13 at 18:25
1
$begingroup$
@ccorn: indeed it does, but I had already written the part for $(a+1)^6$. I guess I could shorten the answer. Thanks.
$endgroup$
– robjohn♦
Aug 8 '13 at 18:27
$begingroup$
With the edit made the (a+1)^{2} is not needed right? If it is I don't understand.
$endgroup$
– Kathy
Aug 8 '13 at 19:19
1
$begingroup$
@Kathy: we still have to show that $a+1$ doesn't have order $2$. We could argue that if $(a+1)^2=1$ and $(a+1)^3=-1$, then $a+1=-1$; that is, $a=-2$. Since $a^3=1$ we have that $-8equiv1pmod{p}$, which implies that $pmid9$, whence $p=3$. Since there are no elements of order $3$ mod $3$, we could stop. Personally, I think the argument in my answer is simpler.
$endgroup$
– robjohn♦
Aug 8 '13 at 19:38
$begingroup$
Is there a problem with this answer? Just wondering if the downvote means something needs fixing.
$endgroup$
– robjohn♦
Jan 1 at 19:45
add a comment |
$begingroup$
Note that if $a=1$, $a$ has order $1$. Thus, we can assume $ane1$. Furthermore, $pne2$ since no element mod $2$ has order $3$. Therefore, $-1ne1pmod{p}$.
$$
begin{align}
(a+1)^3
&=a^3+3a^2+3a+1\
&=1+3a^2+3a+1\
&=-1+3(1+a+a^2)\
&=-1+3frac{a^3-1}{a-1}\
&=-1
end{align}
$$
Therefore, $(a+1)^3=-1$ and $(a+1)^6=1$. (Shortened a la ccorn).
$$
begin{align}
(a+1)^2
&=a^2+2a+1\
&=a+(a^2+a+1)\
&=a+frac{a^3-1}{a-1}\
&=a\
&ne1
end{align}
$$
Therefore, $(a+1)^2ne1$.
Thus, $(a+1)$ has order $6$.
answered Aug 8 '13 at 18:24
robjohn♦robjohn
265k27303626
$endgroup$
Note that if $a=1$, $a$ has order $1$. Thus, we can assume $ane1$. Furthermore, $pne2$ since no element mod $2$ has order $3$. Therefore, $-1ne1pmod{p}$.
$$
begin{align}
(a+1)^3
&=a^3+3a^2+3a+1\
&=1+3a^2+3a+1\
&=-1+3(1+a+a^2)\
&=-1+3frac{a^3-1}{a-1}\
&=-1
end{align}
$$
Therefore, $(a+1)^3=-1$ and $(a+1)^6=1$. (Shortened a la ccorn).
$$
begin{align}
(a+1)^2
&=a^2+2a+1\
&=a+(a^2+a+1)\
&=a+frac{a^3-1}{a-1}\
&=a\
&ne1
end{align}
$$
Therefore, $(a+1)^2ne1$.
Thus, $(a+1)$ has order $6$.
answered Aug 8 '13 at 18:24
robjohn♦robjohn
265k27303626
edited Jan 1 at 20:27
answered Aug 8 '13 at 18:24
robjohn♦robjohn
265k27303626
answered Aug 8 '13 at 18:24
robjohn♦robjohn
265k27303626
answered Aug 8 '13 at 18:24
robjohn♦robjohn
265k27303626
265k27303626
1
$begingroup$
$(a+1)^6=1$ also follows easily from $(a+1)^3=-1$
$endgroup$
– ccorn
Aug 8 '13 at 18:25
1
$begingroup$
@ccorn: indeed it does, but I had already written the part for $(a+1)^6$. I guess I could shorten the answer. Thanks.
$endgroup$
– robjohn♦
Aug 8 '13 at 18:27
$begingroup$
With the edit made the (a+1)^{2} is not needed right? If it is I don't understand.
$endgroup$
– Kathy
Aug 8 '13 at 19:19
1
$begingroup$
@Kathy: we still have to show that $a+1$ doesn't have order $2$. We could argue that if $(a+1)^2=1$ and $(a+1)^3=-1$, then $a+1=-1$; that is, $a=-2$. Since $a^3=1$ we have that $-8equiv1pmod{p}$, which implies that $pmid9$, whence $p=3$. Since there are no elements of order $3$ mod $3$, we could stop. Personally, I think the argument in my answer is simpler.
$endgroup$
– robjohn♦
Aug 8 '13 at 19:38
$begingroup$
Is there a problem with this answer? Just wondering if the downvote means something needs fixing.
$endgroup$
– robjohn♦
Jan 1 at 19:45
add a comment |
1
$begingroup$
$(a+1)^6=1$ also follows easily from $(a+1)^3=-1$
$endgroup$
– ccorn
Aug 8 '13 at 18:25
1
$begingroup$
@ccorn: indeed it does, but I had already written the part for $(a+1)^6$. I guess I could shorten the answer. Thanks.
$endgroup$
– robjohn♦
Aug 8 '13 at 18:27
$begingroup$
With the edit made the (a+1)^{2} is not needed right? If it is I don't understand.
$endgroup$
– Kathy
Aug 8 '13 at 19:19
1
$begingroup$
@Kathy: we still have to show that $a+1$ doesn't have order $2$. We could argue that if $(a+1)^2=1$ and $(a+1)^3=-1$, then $a+1=-1$; that is, $a=-2$. Since $a^3=1$ we have that $-8equiv1pmod{p}$, which implies that $pmid9$, whence $p=3$. Since there are no elements of order $3$ mod $3$, we could stop. Personally, I think the argument in my answer is simpler.
$endgroup$
– robjohn♦
Aug 8 '13 at 19:38
$begingroup$
Is there a problem with this answer? Just wondering if the downvote means something needs fixing.
$endgroup$
– robjohn♦
Jan 1 at 19:45
1
1
$begingroup$
$(a+1)^6=1$ also follows easily from $(a+1)^3=-1$
$endgroup$
– ccorn
Aug 8 '13 at 18:25
$begingroup$
$(a+1)^6=1$ also follows easily from $(a+1)^3=-1$
$endgroup$
– ccorn
Aug 8 '13 at 18:25
1
1
$begingroup$
@ccorn: indeed it does, but I had already written the part for $(a+1)^6$. I guess I could shorten the answer. Thanks.
$endgroup$
– robjohn♦
Aug 8 '13 at 18:27
$begingroup$
@ccorn: indeed it does, but I had already written the part for $(a+1)^6$. I guess I could shorten the answer. Thanks.
$endgroup$
– robjohn♦
Aug 8 '13 at 18:27
$begingroup$
With the edit made the (a+1)^{2} is not needed right? If it is I don't understand.
$endgroup$
– Kathy
Aug 8 '13 at 19:19
$begingroup$
With the edit made the (a+1)^{2} is not needed right? If it is I don't understand.
$endgroup$
– Kathy
Aug 8 '13 at 19:19
1
1
$begingroup$
@Kathy: we still have to show that $a+1$ doesn't have order $2$. We could argue that if $(a+1)^2=1$ and $(a+1)^3=-1$, then $a+1=-1$; that is, $a=-2$. Since $a^3=1$ we have that $-8equiv1pmod{p}$, which implies that $pmid9$, whence $p=3$. Since there are no elements of order $3$ mod $3$, we could stop. Personally, I think the argument in my answer is simpler.
$endgroup$
– robjohn♦
Aug 8 '13 at 19:38
$begingroup$
@Kathy: we still have to show that $a+1$ doesn't have order $2$. We could argue that if $(a+1)^2=1$ and $(a+1)^3=-1$, then $a+1=-1$; that is, $a=-2$. Since $a^3=1$ we have that $-8equiv1pmod{p}$, which implies that $pmid9$, whence $p=3$. Since there are no elements of order $3$ mod $3$, we could stop. Personally, I think the argument in my answer is simpler.
$endgroup$
– robjohn♦
Aug 8 '13 at 19:38
$begingroup$
Is there a problem with this answer? Just wondering if the downvote means something needs fixing.
$endgroup$
– robjohn♦
Jan 1 at 19:45
$begingroup$
Is there a problem with this answer? Just wondering if the downvote means something needs fixing.
$endgroup$
– robjohn♦
Jan 1 at 19:45
add a comment |
$begingroup$
ord_$pa=3iff p$ divides $(a^3-1)=(a-1)(a^2+a+1)$
But $pnotmid (a-1)$ as ord_$pa=3 $
$displaystyleimplies a^2+a+1equiv0pmod p$
$displaystyleiff a(a+1)equiv-1pmod p$
Method $1:$
$implies a^3(a+1)^3equiv-1pmod pimplies (a+1)^3equiv-1$ and $(a+1)^6equiv1$
$implies $ord_$p(a+1)mid 6$ but does not divide $3$
If ord_$p(a+1)mid 2, (a+1)^2equiv1pmod p$ and $a^2(a+1)^2equiv1pmod pimplies a^2equiv1$ which is impossible as ord$_pa=3$
$implies $ord$_p(a+1)=6$
Method $2:$
$displaystyle a(a+1)equiv-1pmod piff a+1equiv (-a)^{-1}pmod p$
Again as $a^3equiv1pmod p, (-a)^3=-a^3equiv-1pmod pimplies (-a)^6equiv1implies $ord$_p(-a)=6$
Using this, ord$_p{(-a)^{-1}})=$ord$_p(-a)=6$
edited Apr 13 '17 at 12:19
Community♦
1
answered Aug 8 '13 at 18:12
lab bhattacharjeelab bhattacharjee
224k15156274
$endgroup$
add a comment |
$begingroup$
ord_$pa=3iff p$ divides $(a^3-1)=(a-1)(a^2+a+1)$
But $pnotmid (a-1)$ as ord_$pa=3 $
$displaystyleimplies a^2+a+1equiv0pmod p$
$displaystyleiff a(a+1)equiv-1pmod p$
Method $1:$
$implies a^3(a+1)^3equiv-1pmod pimplies (a+1)^3equiv-1$ and $(a+1)^6equiv1$
$implies $ord_$p(a+1)mid 6$ but does not divide $3$
If ord_$p(a+1)mid 2, (a+1)^2equiv1pmod p$ and $a^2(a+1)^2equiv1pmod pimplies a^2equiv1$ which is impossible as ord$_pa=3$
$implies $ord$_p(a+1)=6$
Method $2:$
$displaystyle a(a+1)equiv-1pmod piff a+1equiv (-a)^{-1}pmod p$
Again as $a^3equiv1pmod p, (-a)^3=-a^3equiv-1pmod pimplies (-a)^6equiv1implies $ord$_p(-a)=6$
Using this, ord$_p{(-a)^{-1}})=$ord$_p(-a)=6$
edited Apr 13 '17 at 12:19
Community♦
1
answered Aug 8 '13 at 18:12
lab bhattacharjeelab bhattacharjee
224k15156274
$endgroup$
add a comment |
$begingroup$
ord_$pa=3iff p$ divides $(a^3-1)=(a-1)(a^2+a+1)$
But $pnotmid (a-1)$ as ord_$pa=3 $
$displaystyleimplies a^2+a+1equiv0pmod p$
$displaystyleiff a(a+1)equiv-1pmod p$
Method $1:$
$implies a^3(a+1)^3equiv-1pmod pimplies (a+1)^3equiv-1$ and $(a+1)^6equiv1$
$implies $ord_$p(a+1)mid 6$ but does not divide $3$
If ord_$p(a+1)mid 2, (a+1)^2equiv1pmod p$ and $a^2(a+1)^2equiv1pmod pimplies a^2equiv1$ which is impossible as ord$_pa=3$
$implies $ord$_p(a+1)=6$
Method $2:$
$displaystyle a(a+1)equiv-1pmod piff a+1equiv (-a)^{-1}pmod p$
Again as $a^3equiv1pmod p, (-a)^3=-a^3equiv-1pmod pimplies (-a)^6equiv1implies $ord$_p(-a)=6$
Using this, ord$_p{(-a)^{-1}})=$ord$_p(-a)=6$
edited Apr 13 '17 at 12:19
Community♦
1
answered Aug 8 '13 at 18:12
lab bhattacharjeelab bhattacharjee
224k15156274
$endgroup$
ord_$pa=3iff p$ divides $(a^3-1)=(a-1)(a^2+a+1)$
But $pnotmid (a-1)$ as ord_$pa=3 $
$displaystyleimplies a^2+a+1equiv0pmod p$
$displaystyleiff a(a+1)equiv-1pmod p$
Method $1:$
$implies a^3(a+1)^3equiv-1pmod pimplies (a+1)^3equiv-1$ and $(a+1)^6equiv1$
$implies $ord_$p(a+1)mid 6$ but does not divide $3$
If ord_$p(a+1)mid 2, (a+1)^2equiv1pmod p$ and $a^2(a+1)^2equiv1pmod pimplies a^2equiv1$ which is impossible as ord$_pa=3$
$implies $ord$_p(a+1)=6$
Method $2:$
$displaystyle a(a+1)equiv-1pmod piff a+1equiv (-a)^{-1}pmod p$
Again as $a^3equiv1pmod p, (-a)^3=-a^3equiv-1pmod pimplies (-a)^6equiv1implies $ord$_p(-a)=6$
Using this, ord$_p{(-a)^{-1}})=$ord$_p(-a)=6$
edited Apr 13 '17 at 12:19
Community♦
1
answered Aug 8 '13 at 18:12
lab bhattacharjeelab bhattacharjee
224k15156274
edited Apr 13 '17 at 12:19
Community♦
1
edited Apr 13 '17 at 12:19
Community♦
1
edited Apr 13 '17 at 12:19
Community♦
1
1
answered Aug 8 '13 at 18:12
lab bhattacharjeelab bhattacharjee
224k15156274
answered Aug 8 '13 at 18:12
lab bhattacharjeelab bhattacharjee
224k15156274
answered Aug 8 '13 at 18:12
lab bhattacharjeelab bhattacharjee
224k15156274
224k15156274
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%2f463010%2fshow-that-if-a-has-order-3-bmod-p-then-a1-has-order-6-bmod-p%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$
math.stackexchange.com/questions/332325/…
$endgroup$
– Zach Teitler
Dec 14 '18 at 20:29