Show that $−g$ is also a primitive root of $p$ if $pequiv 1 pmod{4}$, but that $ord_p(−g) =...
$begingroup$
This question already has an answer here:
When g and -g are both primitive roots
2 answers
Let $p$ be an odd prime and let $g$ be a primitive root $pmod{p}$.
Show that $−g$ is also a primitive root of $p$ if $p equiv 1 pmod{4}$, but that $ord_p(−g) = frac{p−1}{2}$ if $p equiv 3 pmod{4}$.
So far, I have shown as $p equiv1 pmod{4}$ I can use Fermat's Little Theorem.
$$g equiv g^{p} equiv -(-g)^{p} pmod{p}$$
Since $p equiv 1 pmod{4}$, $x^2 equiv -1 pmod{p}$. ($-1$ is a QR of $p$)
There $exists k in mathbb{Z}$ such that
$$-1 equiv g^{2k} equiv (-g)^{2k} pmod{p}$$
Thus, $g equiv (-g)^{2k}(-g)^{p} pmod{p}$.
As $g$ is congruent to $-g^{p}$, $-g$ is a primitive root of $p$.
Is this enough to show the first part of the question, also how do I begin to show the 2nd part?
number-theory prime-numbers modular-arithmetic primitive-roots
$endgroup$
marked as duplicate by user10354138, user593746, Jyrki Lahtonen, Kevin, José Carlos Santos Dec 13 '18 at 15:09
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
$begingroup$
This question already has an answer here:
When g and -g are both primitive roots
2 answers
Let $p$ be an odd prime and let $g$ be a primitive root $pmod{p}$.
Show that $−g$ is also a primitive root of $p$ if $p equiv 1 pmod{4}$, but that $ord_p(−g) = frac{p−1}{2}$ if $p equiv 3 pmod{4}$.
So far, I have shown as $p equiv1 pmod{4}$ I can use Fermat's Little Theorem.
$$g equiv g^{p} equiv -(-g)^{p} pmod{p}$$
Since $p equiv 1 pmod{4}$, $x^2 equiv -1 pmod{p}$. ($-1$ is a QR of $p$)
There $exists k in mathbb{Z}$ such that
$$-1 equiv g^{2k} equiv (-g)^{2k} pmod{p}$$
Thus, $g equiv (-g)^{2k}(-g)^{p} pmod{p}$.
As $g$ is congruent to $-g^{p}$, $-g$ is a primitive root of $p$.
Is this enough to show the first part of the question, also how do I begin to show the 2nd part?
number-theory prime-numbers modular-arithmetic primitive-roots
$endgroup$
marked as duplicate by user10354138, user593746, Jyrki Lahtonen, Kevin, José Carlos Santos Dec 13 '18 at 15:09
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
1
$begingroup$
math.stackexchange.com/questions/1229270/…
$endgroup$
– lab bhattacharjee
Dec 11 '18 at 11:43
1
$begingroup$
Find a way to write -1 as a power of the primitive root g then use the fact that $text{ord}_p(g^d) = frac{text{ord}_p(g)}{text{gcd}(text{ord}_p(g),d)}$. That is, find the gcd$(text{ord}_p(g),d)$, where $-g equiv g^d text{mod }p$ and the result will follow.
$endgroup$
– user337254
Dec 11 '18 at 15:28
add a comment |
$begingroup$
This question already has an answer here:
When g and -g are both primitive roots
2 answers
Let $p$ be an odd prime and let $g$ be a primitive root $pmod{p}$.
Show that $−g$ is also a primitive root of $p$ if $p equiv 1 pmod{4}$, but that $ord_p(−g) = frac{p−1}{2}$ if $p equiv 3 pmod{4}$.
So far, I have shown as $p equiv1 pmod{4}$ I can use Fermat's Little Theorem.
$$g equiv g^{p} equiv -(-g)^{p} pmod{p}$$
Since $p equiv 1 pmod{4}$, $x^2 equiv -1 pmod{p}$. ($-1$ is a QR of $p$)
There $exists k in mathbb{Z}$ such that
$$-1 equiv g^{2k} equiv (-g)^{2k} pmod{p}$$
Thus, $g equiv (-g)^{2k}(-g)^{p} pmod{p}$.
As $g$ is congruent to $-g^{p}$, $-g$ is a primitive root of $p$.
Is this enough to show the first part of the question, also how do I begin to show the 2nd part?
number-theory prime-numbers modular-arithmetic primitive-roots
$endgroup$
This question already has an answer here:
When g and -g are both primitive roots
2 answers
Let $p$ be an odd prime and let $g$ be a primitive root $pmod{p}$.
Show that $−g$ is also a primitive root of $p$ if $p equiv 1 pmod{4}$, but that $ord_p(−g) = frac{p−1}{2}$ if $p equiv 3 pmod{4}$.
So far, I have shown as $p equiv1 pmod{4}$ I can use Fermat's Little Theorem.
$$g equiv g^{p} equiv -(-g)^{p} pmod{p}$$
Since $p equiv 1 pmod{4}$, $x^2 equiv -1 pmod{p}$. ($-1$ is a QR of $p$)
There $exists k in mathbb{Z}$ such that
$$-1 equiv g^{2k} equiv (-g)^{2k} pmod{p}$$
Thus, $g equiv (-g)^{2k}(-g)^{p} pmod{p}$.
As $g$ is congruent to $-g^{p}$, $-g$ is a primitive root of $p$.
Is this enough to show the first part of the question, also how do I begin to show the 2nd part?
This question already has an answer here:
When g and -g are both primitive roots
2 answers
number-theory prime-numbers modular-arithmetic primitive-roots
number-theory prime-numbers modular-arithmetic primitive-roots
edited Dec 13 '18 at 8:07
rtybase
11k21533
11k21533
asked Dec 11 '18 at 11:28
frankfieldsfrankfields
165
165
marked as duplicate by user10354138, user593746, Jyrki Lahtonen, Kevin, José Carlos Santos Dec 13 '18 at 15:09
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by user10354138, user593746, Jyrki Lahtonen, Kevin, José Carlos Santos Dec 13 '18 at 15:09
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
1
$begingroup$
math.stackexchange.com/questions/1229270/…
$endgroup$
– lab bhattacharjee
Dec 11 '18 at 11:43
1
$begingroup$
Find a way to write -1 as a power of the primitive root g then use the fact that $text{ord}_p(g^d) = frac{text{ord}_p(g)}{text{gcd}(text{ord}_p(g),d)}$. That is, find the gcd$(text{ord}_p(g),d)$, where $-g equiv g^d text{mod }p$ and the result will follow.
$endgroup$
– user337254
Dec 11 '18 at 15:28
add a comment |
1
$begingroup$
math.stackexchange.com/questions/1229270/…
$endgroup$
– lab bhattacharjee
Dec 11 '18 at 11:43
1
$begingroup$
Find a way to write -1 as a power of the primitive root g then use the fact that $text{ord}_p(g^d) = frac{text{ord}_p(g)}{text{gcd}(text{ord}_p(g),d)}$. That is, find the gcd$(text{ord}_p(g),d)$, where $-g equiv g^d text{mod }p$ and the result will follow.
$endgroup$
– user337254
Dec 11 '18 at 15:28
1
1
$begingroup$
math.stackexchange.com/questions/1229270/…
$endgroup$
– lab bhattacharjee
Dec 11 '18 at 11:43
$begingroup$
math.stackexchange.com/questions/1229270/…
$endgroup$
– lab bhattacharjee
Dec 11 '18 at 11:43
1
1
$begingroup$
Find a way to write -1 as a power of the primitive root g then use the fact that $text{ord}_p(g^d) = frac{text{ord}_p(g)}{text{gcd}(text{ord}_p(g),d)}$. That is, find the gcd$(text{ord}_p(g),d)$, where $-g equiv g^d text{mod }p$ and the result will follow.
$endgroup$
– user337254
Dec 11 '18 at 15:28
$begingroup$
Find a way to write -1 as a power of the primitive root g then use the fact that $text{ord}_p(g^d) = frac{text{ord}_p(g)}{text{gcd}(text{ord}_p(g),d)}$. That is, find the gcd$(text{ord}_p(g),d)$, where $-g equiv g^d text{mod }p$ and the result will follow.
$endgroup$
– user337254
Dec 11 '18 at 15:28
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
First of all, consider this fact:
If $a$ is of order $h$ $pmod n$, then $a^k$ is of order $frac{h}{gcd(h,k)} quad quad quadquad quad (1)$
The Proof:
Since $g$ is a primitive root, $-1 equiv g^{frac{p-1}{2}} pmod p$. Therefore, $-g equiv (-1)(g) equiv g^{frac{p-1}{2}}g equiv g^{frac{p+1}{2}} pmod p$. Now, the order of $g^{frac{p+1}{2}} pmod p$ according to $(1)$ is $frac{p-1}{gcd(frac{p+1}{2},p-1)}$. If $pequiv 1 pmod 4$, then $frac{p+1}{2}$ is odd and ${gcd(frac{p+1}{2},p-1)}$ is 1 making the order of $-g$ to be $p-1$. i.e. a primitive root. Otherwise, the term $frac{p+1}{2}$ is even and ${gcd(frac{p+1}{2},p-1)} = frac{p-1}{2} > 1$. Therefore, the order of $-g$ is not $p-1$. i.e. not a primitive root.
I am quoting my answer on my question here with some minor changes.
$endgroup$
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
First of all, consider this fact:
If $a$ is of order $h$ $pmod n$, then $a^k$ is of order $frac{h}{gcd(h,k)} quad quad quadquad quad (1)$
The Proof:
Since $g$ is a primitive root, $-1 equiv g^{frac{p-1}{2}} pmod p$. Therefore, $-g equiv (-1)(g) equiv g^{frac{p-1}{2}}g equiv g^{frac{p+1}{2}} pmod p$. Now, the order of $g^{frac{p+1}{2}} pmod p$ according to $(1)$ is $frac{p-1}{gcd(frac{p+1}{2},p-1)}$. If $pequiv 1 pmod 4$, then $frac{p+1}{2}$ is odd and ${gcd(frac{p+1}{2},p-1)}$ is 1 making the order of $-g$ to be $p-1$. i.e. a primitive root. Otherwise, the term $frac{p+1}{2}$ is even and ${gcd(frac{p+1}{2},p-1)} = frac{p-1}{2} > 1$. Therefore, the order of $-g$ is not $p-1$. i.e. not a primitive root.
I am quoting my answer on my question here with some minor changes.
$endgroup$
add a comment |
$begingroup$
First of all, consider this fact:
If $a$ is of order $h$ $pmod n$, then $a^k$ is of order $frac{h}{gcd(h,k)} quad quad quadquad quad (1)$
The Proof:
Since $g$ is a primitive root, $-1 equiv g^{frac{p-1}{2}} pmod p$. Therefore, $-g equiv (-1)(g) equiv g^{frac{p-1}{2}}g equiv g^{frac{p+1}{2}} pmod p$. Now, the order of $g^{frac{p+1}{2}} pmod p$ according to $(1)$ is $frac{p-1}{gcd(frac{p+1}{2},p-1)}$. If $pequiv 1 pmod 4$, then $frac{p+1}{2}$ is odd and ${gcd(frac{p+1}{2},p-1)}$ is 1 making the order of $-g$ to be $p-1$. i.e. a primitive root. Otherwise, the term $frac{p+1}{2}$ is even and ${gcd(frac{p+1}{2},p-1)} = frac{p-1}{2} > 1$. Therefore, the order of $-g$ is not $p-1$. i.e. not a primitive root.
I am quoting my answer on my question here with some minor changes.
$endgroup$
add a comment |
$begingroup$
First of all, consider this fact:
If $a$ is of order $h$ $pmod n$, then $a^k$ is of order $frac{h}{gcd(h,k)} quad quad quadquad quad (1)$
The Proof:
Since $g$ is a primitive root, $-1 equiv g^{frac{p-1}{2}} pmod p$. Therefore, $-g equiv (-1)(g) equiv g^{frac{p-1}{2}}g equiv g^{frac{p+1}{2}} pmod p$. Now, the order of $g^{frac{p+1}{2}} pmod p$ according to $(1)$ is $frac{p-1}{gcd(frac{p+1}{2},p-1)}$. If $pequiv 1 pmod 4$, then $frac{p+1}{2}$ is odd and ${gcd(frac{p+1}{2},p-1)}$ is 1 making the order of $-g$ to be $p-1$. i.e. a primitive root. Otherwise, the term $frac{p+1}{2}$ is even and ${gcd(frac{p+1}{2},p-1)} = frac{p-1}{2} > 1$. Therefore, the order of $-g$ is not $p-1$. i.e. not a primitive root.
I am quoting my answer on my question here with some minor changes.
$endgroup$
First of all, consider this fact:
If $a$ is of order $h$ $pmod n$, then $a^k$ is of order $frac{h}{gcd(h,k)} quad quad quadquad quad (1)$
The Proof:
Since $g$ is a primitive root, $-1 equiv g^{frac{p-1}{2}} pmod p$. Therefore, $-g equiv (-1)(g) equiv g^{frac{p-1}{2}}g equiv g^{frac{p+1}{2}} pmod p$. Now, the order of $g^{frac{p+1}{2}} pmod p$ according to $(1)$ is $frac{p-1}{gcd(frac{p+1}{2},p-1)}$. If $pequiv 1 pmod 4$, then $frac{p+1}{2}$ is odd and ${gcd(frac{p+1}{2},p-1)}$ is 1 making the order of $-g$ to be $p-1$. i.e. a primitive root. Otherwise, the term $frac{p+1}{2}$ is even and ${gcd(frac{p+1}{2},p-1)} = frac{p-1}{2} > 1$. Therefore, the order of $-g$ is not $p-1$. i.e. not a primitive root.
I am quoting my answer on my question here with some minor changes.
answered Dec 13 '18 at 7:42
Maged SaeedMaged Saeed
8671417
8671417
add a comment |
add a comment |
1
$begingroup$
math.stackexchange.com/questions/1229270/…
$endgroup$
– lab bhattacharjee
Dec 11 '18 at 11:43
1
$begingroup$
Find a way to write -1 as a power of the primitive root g then use the fact that $text{ord}_p(g^d) = frac{text{ord}_p(g)}{text{gcd}(text{ord}_p(g),d)}$. That is, find the gcd$(text{ord}_p(g),d)$, where $-g equiv g^d text{mod }p$ and the result will follow.
$endgroup$
– user337254
Dec 11 '18 at 15:28