If $a$ is of order $3$ mod a prime $p$, then …
up vote
1
down vote
favorite
The question says:
Prove that if $a$ is of order $3$ modulo a prime $p$, then $1+a+a^2equiv 0 pmod p$. Moreover, $a+1$ is of order $6$.
For the First Part:
The typical idea is to start with $a^3 equiv 1 pmod p to a^3 -1 equiv 0 pmod p$. Factoring the term on the left hand side, the rest is straightforward.
However, I need to check the following idea:
$$1+a+a^2 equiv a^3+a^2+a equiv a(1+a+a^2)equiv a^2(1+a+a^2)$$
$$equiv a^3(1+a+a^2) equiv 0 pmod p$$
Since, by the hypothesis, $a^3$ cannot be zero modulo the prime $p$, the desired result holds.
If this idea holds true, it can be generalized to the following result:
if $a$ is of order $k$, then, modulo prime $p$, then $1+a+a^2+cdots + a^{k-1}$ is divisible by $p$.
Is it??
For the Second Part:
I can see that:
$$1+a+a^2 equiv 0 to 1+a equiv -a^2 pmod p$$
However, does this implies anything? Given that $a$ is of order $3$, but what about $-a$??
Please Help, and Thanks in advance,,
number-theory elementary-number-theory modular-arithmetic divisibility primitive-roots
asked Nov 23 at 4:16
Maged Saeed
762316
add a comment |
up vote
1
down vote
favorite
The question says:
Prove that if $a$ is of order $3$ modulo a prime $p$, then $1+a+a^2equiv 0 pmod p$. Moreover, $a+1$ is of order $6$.
For the First Part:
The typical idea is to start with $a^3 equiv 1 pmod p to a^3 -1 equiv 0 pmod p$. Factoring the term on the left hand side, the rest is straightforward.
However, I need to check the following idea:
$$1+a+a^2 equiv a^3+a^2+a equiv a(1+a+a^2)equiv a^2(1+a+a^2)$$
$$equiv a^3(1+a+a^2) equiv 0 pmod p$$
Since, by the hypothesis, $a^3$ cannot be zero modulo the prime $p$, the desired result holds.
If this idea holds true, it can be generalized to the following result:
if $a$ is of order $k$, then, modulo prime $p$, then $1+a+a^2+cdots + a^{k-1}$ is divisible by $p$.
Is it??
For the Second Part:
I can see that:
$$1+a+a^2 equiv 0 to 1+a equiv -a^2 pmod p$$
However, does this implies anything? Given that $a$ is of order $3$, but what about $-a$??
Please Help, and Thanks in advance,,
number-theory elementary-number-theory modular-arithmetic divisibility primitive-roots
asked Nov 23 at 4:16
Maged Saeed
762316
math.stackexchange.com/questions/220493/…
– lab bhattacharjee
Nov 23 at 7:16
@labbhattacharjee, I would like to see your comments about thoughts on the first part.
– Maged Saeed
Nov 23 at 8:12
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
The question says:
Prove that if $a$ is of order $3$ modulo a prime $p$, then $1+a+a^2equiv 0 pmod p$. Moreover, $a+1$ is of order $6$.
For the First Part:
The typical idea is to start with $a^3 equiv 1 pmod p to a^3 -1 equiv 0 pmod p$. Factoring the term on the left hand side, the rest is straightforward.
However, I need to check the following idea:
$$1+a+a^2 equiv a^3+a^2+a equiv a(1+a+a^2)equiv a^2(1+a+a^2)$$
$$equiv a^3(1+a+a^2) equiv 0 pmod p$$
Since, by the hypothesis, $a^3$ cannot be zero modulo the prime $p$, the desired result holds.
If this idea holds true, it can be generalized to the following result:
if $a$ is of order $k$, then, modulo prime $p$, then $1+a+a^2+cdots + a^{k-1}$ is divisible by $p$.
Is it??
For the Second Part:
I can see that:
$$1+a+a^2 equiv 0 to 1+a equiv -a^2 pmod p$$
However, does this implies anything? Given that $a$ is of order $3$, but what about $-a$??
Please Help, and Thanks in advance,,
number-theory elementary-number-theory modular-arithmetic divisibility primitive-roots
asked Nov 23 at 4:16
Maged Saeed
762316
The question says:
Prove that if $a$ is of order $3$ modulo a prime $p$, then $1+a+a^2equiv 0 pmod p$. Moreover, $a+1$ is of order $6$.
For the First Part:
The typical idea is to start with $a^3 equiv 1 pmod p to a^3 -1 equiv 0 pmod p$. Factoring the term on the left hand side, the rest is straightforward.
However, I need to check the following idea:
$$1+a+a^2 equiv a^3+a^2+a equiv a(1+a+a^2)equiv a^2(1+a+a^2)$$
$$equiv a^3(1+a+a^2) equiv 0 pmod p$$
Since, by the hypothesis, $a^3$ cannot be zero modulo the prime $p$, the desired result holds.
If this idea holds true, it can be generalized to the following result:
if $a$ is of order $k$, then, modulo prime $p$, then $1+a+a^2+cdots + a^{k-1}$ is divisible by $p$.
Is it??
For the Second Part:
I can see that:
$$1+a+a^2 equiv 0 to 1+a equiv -a^2 pmod p$$
However, does this implies anything? Given that $a$ is of order $3$, but what about $-a$??
Please Help, and Thanks in advance,,
number-theory elementary-number-theory modular-arithmetic divisibility primitive-roots
number-theory elementary-number-theory modular-arithmetic divisibility primitive-roots
asked Nov 23 at 4:16
Maged Saeed
762316
asked Nov 23 at 4:16
Maged Saeed
762316
edited Nov 23 at 4:20
asked Nov 23 at 4:16
Maged Saeed
762316
asked Nov 23 at 4:16
Maged Saeed
762316
asked Nov 23 at 4:16
Maged Saeed
762316
762316
math.stackexchange.com/questions/220493/…
– lab bhattacharjee
Nov 23 at 7:16
@labbhattacharjee, I would like to see your comments about thoughts on the first part.
– Maged Saeed
Nov 23 at 8:12
add a comment |
math.stackexchange.com/questions/220493/…
– lab bhattacharjee
Nov 23 at 7:16
@labbhattacharjee, I would like to see your comments about thoughts on the first part.
– Maged Saeed
Nov 23 at 8:12
math.stackexchange.com/questions/220493/…
– lab bhattacharjee
Nov 23 at 7:16
math.stackexchange.com/questions/220493/…
– lab bhattacharjee
Nov 23 at 7:16
@labbhattacharjee, I would like to see your comments about thoughts on the first part.
– Maged Saeed
Nov 23 at 8:12
@labbhattacharjee, I would like to see your comments about thoughts on the first part.
– Maged Saeed
Nov 23 at 8:12
add a comment |
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
For the second part, taking from the first part that $1+a = -a^2pmod pimplies (1+a)^6= (-a^2)^6 = a^{12}pmod p= (a^3)^4 =1^4pmod p=1pmod p$ . Thus $1+a$ is of order $6$ as claimed. And if $a$ is of order $3$ then $(-a)^3 = -a^3 = -1 = p-1pmod p$. And from this we have: $(-a)^6 = ((-a)^3)^2 = (-1)^2 = 1pmod p$. So $-a$ is of order $6$ as well.
answered Nov 23 at 4:25
DeepSea
70.8k54487
Thanks, but how to be sure that $6$ is the least power congruent to $1 pmod p$ for $(1+a)$??
– Maged Saeed
Nov 23 at 4:28
I need also to make sure my thoughts are correct for the first part. Thanks in advance.
– Maged Saeed
Nov 23 at 4:29
1
@MagedSaeed: You can prove it yourself that if $k$ is such that $(a+1)^k = 1pmod p implies k = 6$. In fact, such $k$ must satisfies $k mid 6 implies k = 1,2,3$. And none of these can satisfy since $a$ is of order $3$.
– DeepSea
Nov 23 at 4:35
Oh, thanks,, I see.
– Maged Saeed
Nov 23 at 4:37
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',
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%2f3009968%2fif-a-is-of-order-3-mod-a-prime-p-then%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
up vote
2
down vote
accepted
For the second part, taking from the first part that $1+a = -a^2pmod pimplies (1+a)^6= (-a^2)^6 = a^{12}pmod p= (a^3)^4 =1^4pmod p=1pmod p$ . Thus $1+a$ is of order $6$ as claimed. And if $a$ is of order $3$ then $(-a)^3 = -a^3 = -1 = p-1pmod p$. And from this we have: $(-a)^6 = ((-a)^3)^2 = (-1)^2 = 1pmod p$. So $-a$ is of order $6$ as well.
answered Nov 23 at 4:25
DeepSea
70.8k54487
Thanks, but how to be sure that $6$ is the least power congruent to $1 pmod p$ for $(1+a)$??
– Maged Saeed
Nov 23 at 4:28
I need also to make sure my thoughts are correct for the first part. Thanks in advance.
– Maged Saeed
Nov 23 at 4:29
1
@MagedSaeed: You can prove it yourself that if $k$ is such that $(a+1)^k = 1pmod p implies k = 6$. In fact, such $k$ must satisfies $k mid 6 implies k = 1,2,3$. And none of these can satisfy since $a$ is of order $3$.
– DeepSea
Nov 23 at 4:35
Oh, thanks,, I see.
– Maged Saeed
Nov 23 at 4:37
add a comment |
up vote
2
down vote
accepted
For the second part, taking from the first part that $1+a = -a^2pmod pimplies (1+a)^6= (-a^2)^6 = a^{12}pmod p= (a^3)^4 =1^4pmod p=1pmod p$ . Thus $1+a$ is of order $6$ as claimed. And if $a$ is of order $3$ then $(-a)^3 = -a^3 = -1 = p-1pmod p$. And from this we have: $(-a)^6 = ((-a)^3)^2 = (-1)^2 = 1pmod p$. So $-a$ is of order $6$ as well.
answered Nov 23 at 4:25
DeepSea
70.8k54487
Thanks, but how to be sure that $6$ is the least power congruent to $1 pmod p$ for $(1+a)$??
– Maged Saeed
Nov 23 at 4:28
I need also to make sure my thoughts are correct for the first part. Thanks in advance.
– Maged Saeed
Nov 23 at 4:29
1
@MagedSaeed: You can prove it yourself that if $k$ is such that $(a+1)^k = 1pmod p implies k = 6$. In fact, such $k$ must satisfies $k mid 6 implies k = 1,2,3$. And none of these can satisfy since $a$ is of order $3$.
– DeepSea
Nov 23 at 4:35
Oh, thanks,, I see.
– Maged Saeed
Nov 23 at 4:37
add a comment |
up vote
2
down vote
accepted
up vote
2
down vote
accepted
For the second part, taking from the first part that $1+a = -a^2pmod pimplies (1+a)^6= (-a^2)^6 = a^{12}pmod p= (a^3)^4 =1^4pmod p=1pmod p$ . Thus $1+a$ is of order $6$ as claimed. And if $a$ is of order $3$ then $(-a)^3 = -a^3 = -1 = p-1pmod p$. And from this we have: $(-a)^6 = ((-a)^3)^2 = (-1)^2 = 1pmod p$. So $-a$ is of order $6$ as well.
answered Nov 23 at 4:25
DeepSea
70.8k54487
For the second part, taking from the first part that $1+a = -a^2pmod pimplies (1+a)^6= (-a^2)^6 = a^{12}pmod p= (a^3)^4 =1^4pmod p=1pmod p$ . Thus $1+a$ is of order $6$ as claimed. And if $a$ is of order $3$ then $(-a)^3 = -a^3 = -1 = p-1pmod p$. And from this we have: $(-a)^6 = ((-a)^3)^2 = (-1)^2 = 1pmod p$. So $-a$ is of order $6$ as well.
answered Nov 23 at 4:25
DeepSea
70.8k54487
edited Nov 23 at 4:42
answered Nov 23 at 4:25
DeepSea
70.8k54487
answered Nov 23 at 4:25
DeepSea
70.8k54487
answered Nov 23 at 4:25
DeepSea
70.8k54487
70.8k54487
Thanks, but how to be sure that $6$ is the least power congruent to $1 pmod p$ for $(1+a)$??
– Maged Saeed
Nov 23 at 4:28
I need also to make sure my thoughts are correct for the first part. Thanks in advance.
– Maged Saeed
Nov 23 at 4:29
1
@MagedSaeed: You can prove it yourself that if $k$ is such that $(a+1)^k = 1pmod p implies k = 6$. In fact, such $k$ must satisfies $k mid 6 implies k = 1,2,3$. And none of these can satisfy since $a$ is of order $3$.
– DeepSea
Nov 23 at 4:35
Oh, thanks,, I see.
– Maged Saeed
Nov 23 at 4:37
add a comment |
Thanks, but how to be sure that $6$ is the least power congruent to $1 pmod p$ for $(1+a)$??
– Maged Saeed
Nov 23 at 4:28
I need also to make sure my thoughts are correct for the first part. Thanks in advance.
– Maged Saeed
Nov 23 at 4:29
1
@MagedSaeed: You can prove it yourself that if $k$ is such that $(a+1)^k = 1pmod p implies k = 6$. In fact, such $k$ must satisfies $k mid 6 implies k = 1,2,3$. And none of these can satisfy since $a$ is of order $3$.
– DeepSea
Nov 23 at 4:35
Oh, thanks,, I see.
– Maged Saeed
Nov 23 at 4:37
Thanks, but how to be sure that $6$ is the least power congruent to $1 pmod p$ for $(1+a)$??
– Maged Saeed
Nov 23 at 4:28
Thanks, but how to be sure that $6$ is the least power congruent to $1 pmod p$ for $(1+a)$??
– Maged Saeed
Nov 23 at 4:28
I need also to make sure my thoughts are correct for the first part. Thanks in advance.
– Maged Saeed
Nov 23 at 4:29
I need also to make sure my thoughts are correct for the first part. Thanks in advance.
– Maged Saeed
Nov 23 at 4:29
1
1
@MagedSaeed: You can prove it yourself that if $k$ is such that $(a+1)^k = 1pmod p implies k = 6$. In fact, such $k$ must satisfies $k mid 6 implies k = 1,2,3$. And none of these can satisfy since $a$ is of order $3$.
– DeepSea
Nov 23 at 4:35
@MagedSaeed: You can prove it yourself that if $k$ is such that $(a+1)^k = 1pmod p implies k = 6$. In fact, such $k$ must satisfies $k mid 6 implies k = 1,2,3$. And none of these can satisfy since $a$ is of order $3$.
– DeepSea
Nov 23 at 4:35
Oh, thanks,, I see.
– Maged Saeed
Nov 23 at 4:37
Oh, thanks,, I see.
– Maged Saeed
Nov 23 at 4:37
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3009968%2fif-a-is-of-order-3-mod-a-prime-p-then%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
math.stackexchange.com/questions/220493/…
– lab bhattacharjee
Nov 23 at 7:16
@labbhattacharjee, I would like to see your comments about thoughts on the first part.
– Maged Saeed
Nov 23 at 8:12