Questions tagged [primitive-roots]
For questions about primitive roots in modular arithmetic, index calculus, and applications in cryptography. For questions about primitive roots of unity, use the (roots-of-unity) tag instead.
71
questions
12
votes
5
answers
10k
views
Prove if $n$ has a primitive root, then it has exactly $\phi(\phi(n))$ of them
Prove if $n$ has a primitive root, then it has exactly $\phi(\phi(n))$ of them.
Let $a$ be the primitive root then I know other primitive roots will be among $\{a,a^2,a^3 \cdots\cdots a^{\phi(n)} \}$ ...
- 3,078
14
votes
2
answers
2k
views
Is every non-square integer a primitive root modulo some odd prime?
This question often comes in my mind when doing exercices in elementary number theory:
Is every non-square integer a primitive root modulo some odd prime?
This would make many exercices much ...
- 25.4k
7
votes
1
answer
7k
views
Proof of existence of primitive roots
In my book (Elementary Number Theory, Stillwell), exercise 3.9.1 asks to give an alternative proof of the existence of a primitive root for any prime.
Let $p$ be prime, and consider the group $\...
- 6,392
6
votes
3
answers
2k
views
2 is a primitive root mod $3^h$ for any positive integer $h$
It's easy to verify that 2 is a primitive root mod $3^2$. But then why does it follow that 2 is a primitive root mod $3^h$ for any positive integer $h$?
This was used in the solution of 2009 Putnam ...
- 4,896
16
votes
4
answers
6k
views
Prove sum of primitive roots congruent to $\mu(p-1) \pmod{p}$
Suppose that $p$ is a prime. Prove that the sum of the primitive roots modulo $p$ is congruent to
$\mu(p − 1) \pmod{p}$.
- 425
4
votes
1
answer
239
views
Count of lower and upper primitive roots of prime $p \equiv 3 \bmod 4$
I was exploring the layout of primitive roots of primes over a reasonable range and this question concerns the number of primitive roots either side of $p/2$.
Many primes have an exact match between ...
- 39.1k
7
votes
2
answers
709
views
Question about primitive roots of p and $p^2$
If $g$ is a primitive root of a prime $p$, then $g$ is also a primitive root of $p^2$ if and only if $g^{p-1} \pmod p^2$ is not $1$. Is there a prime $p$ such that $p^2$ missing exactly $m$ primitive ...
5
votes
3
answers
4k
views
If $p$ is an odd prime and $k$ an integer with $0<k<p-1$ then $1^k + 2^k + \ldots + (p-1)^k$ is divisible by $p$
If $p$ is an odd prime and $k$ an integer with $0<k<p-1$ prove that $1^k + 2^k + \ldots + (p-1)^k$ is divisible by $p$. Given hint: use primitive root.
This is a question on a practice final of ...
5
votes
1
answer
581
views
Conjecture about the product of the primitive roots modulo a prime number ($\prod Pr_p$)
While I was learning about the primitive roots modulo $p \in \Bbb P$ (I will call $Pr_p$ to the complete list of the primitive roots module $p$) and having in mind the conjecture explained in this ...
- 8,763
5
votes
2
answers
253
views
Show $2+\alpha$ is a primitive root of $\mathbb{F}_{25}$.
Suppose $\alpha \in \mathbb{F}_{25}$ is an element with $\alpha^2 = 2$, I need to prove that $2+\alpha \in \mathbb{F}_{25}$ is a primitive root (that is: a generator of the cyclic group $\mathbb{F}_{...
- 1,579
5
votes
2
answers
2k
views
Sum of powers mod p
I've this problem that I did halve of the proof but I can't do the rest of it.
Let $p$ be an odd prime. We define $S_n$ as $S_n = 1^n +2^n + ... +(p-1)^n$
Prove that
$S_n \equiv
\begin{cases}
...
- 351
3
votes
1
answer
3k
views
Primitive Root Theorem Proof
The primitive root theorem states that $U(n)$ is a cyclic group if and only if $n$ is $1, 2, 4, p^{k}, 2p^{k}$ where $p$ is an odd prime and $k$ is an integer greater than or equal to 1. Can someone ...
- 557
2
votes
2
answers
3k
views
Prove that 3 is a primitive root of $7^k$ for all $k \ge 1$
so I am trying to find out how to prove that 3 is a primitive root of $7^k$ for all $k \ge 1$. I am trying to prove this via induction.
Thanks.
- 351
2
votes
1
answer
235
views
Let $p$ be a prime number. Show that the number of solutions to $x^k \equiv 1 \pmod p$ is $gcd(k, p-1)$
I'm really not convinced by my own proof of this. Would appreciate a critique/reformulation using the ideas I already introduced.
First note that $a^k \equiv 1 \mod p \implies k\ |\ p -1$ by Fermat's ...
- 263
4
votes
2
answers
3k
views
integer $m$ has primitive root if and only if the only solutions of the congruence $x^{2} \equiv 1 \pmod m$ are $x \equiv \pm 1\pmod m$.
Show that the integer $m$ has primitive root if and only if the only solutions of the congruence $x^{2} \equiv 1 \pmod m$ are $x \equiv \pm 1\pmod m$.
I don't quite understand what this question is ...
- 1,390
4
votes
1
answer
164
views
Primitive roots modulo primes congruent to n!
for $N \ge 4$. Show for prime numbers, $p \equiv 1$ mod $(N!)$ that none of the numbers $1,2,...,N$ are primitive roots modulo $p$
I can't figure out where to start with this question, all I can ...
- 143
3
votes
3
answers
1k
views
No primitive root modulo $2^n$ for $n\ge 3$
Prove that there is no primitive root modulo $2^n$.
I'm not sure how to begin proving this. I know $\varphi(2^n)=2^{n-1}$, thus a primitive root $a\in\left(\dfrac{\mathbb{Z}}{2^n\mathbb{Z}}\right)^*$ ...
- 103
3
votes
2
answers
2k
views
Prove that $r$ is a primitive root modulo $p$ if and only if $r^{(p−1)/q}\not\equiv 1\pmod{p}$
Suppose $p$ is an odd prime. Prove that $r$, with $\gcd(r, p) = 1$, is a primitive root
modulo $p$ if and only if $r^{(p−1)/q}\not\equiv 1\pmod{p}$ for all prime divisors $q$ of $p − 1$.
The only ...
- 3,488
3
votes
1
answer
236
views
Why is $c+q$ still a primitive root modulo $q$?
Question: Let $p$ and $q$ be distinct odd prime numbers.
By considering primitive roots, we need to show $\exists c\in\mathbb{Z}$ with the property that:
$\bullet$ $c^n\equiv 1\pmod{p}$ whenever $n$ ...
- 2,237
3
votes
1
answer
545
views
A question about a primitive root mod $p=2^{2^k}+1$, where $p$ is prime.
Let $p=2^{2^k}+1$ be a prime where $k\ge1$. Prove that the set of quadratic non-residues mod $p$ is the same as the set of primitive roots mod $p$. Use this to show that $7$ is a primitive root mod $p$...
3
votes
1
answer
1k
views
If $r$ is a primitive root of odd prime $p$, prove that $\text{ind}_r (-1) = \frac{p-1}{2}$
If $r$ is a primitive root of odd prime $p$, prove that $\text{ind}_r (-1) = \frac{p-1}{2}$
I know $r^{p-1}\equiv 1 \pmod {p} \implies r^{(p-1)/2}\equiv -1 \pmod{p}$
But some how I feel the ...
- 12k
2
votes
1
answer
196
views
If $m|n$ and $a$ is a primitive root of $n$, show that $a$ is a primitive root of $m$ (understanding a tip)
I saw the answer to this question and it is the same problem, but i didn't get how to use the tip S.C.B gave.
This was the tip:
$"$First, assume that it is not $a$ primitive root $(\text{mod m})$. ...
- 337
1
vote
1
answer
288
views
Primitive roots of the unity in $\mathbb C$
Let $\omega$ be a primitive $n-$th root of unity.
(i) Show that its powers $\omega^k$, for $k ∈ {1, \ldots, n}$, are all different;
(ii) Deduce that they are precisely all the $n-$th roots of unity.
...
user720013
1
vote
2
answers
713
views
When g and -g are both primitive roots
The question states:
Let $g$ by a primitive root of the odd prime $p$. Show that $-g$ is a primitive root , or not, according as $p \equiv 1 \pmod 4$ or not.
For me, I cannot see any connection ...
- 1,146
0
votes
1
answer
779
views
prove that $\zeta^{i}$ is a primitive root modulo p $\iff$ $\gcd(p-1,i) =1$ where $p$ is prime and $\zeta$ is a primitive root modulo p.
I was going to use a case by case proof, but i am relativley new to primitive roots and I couldnt see how to sufficiently prove either case.
- 441
0
votes
2
answers
3k
views
If $p$ and $q = 2p + 1$ are both odd primes, show that $-4$ and $2(-1)^{(1/2)(p-1)}$ are both primitive roots modulo $q$.
If $p$ and $q = 2p + 1$ are both odd primes, show that $-4$ and $2(-1)^{(1/2)(p-1)}$ are both primitive roots modulo $q$.
I cannot get heads nor tails of how to even start this let alone finish it
- 51
0
votes
1
answer
137
views
Find the number of integer pairs 0 ≤ a, b ≤ 100 such that a^20 ≡ b^50 (mod 101). Need help with understanding solution
Find the number of integer pairs 0 ≤ a, b ≤ 100 such that $a^{20}$ ≡ $b^{50} \pmod {101}$.
Here is the solution: "Since is prime, there exists a primitive
root g in modulo 101. For some integers x ...
- 11
7
votes
3
answers
401
views
$p^2$ misses 2 primitive roots
When I Checked primitive roots of some primes P, I found this following phenomenon:
$14$ is a primitive root of prime $29$, but it's not primitive root of $29^2$
$18$ is a primitive root of prime $...
- 71
6
votes
2
answers
695
views
Show that $-3$ is a primitive root modulo $p=2q+1$
This was a question from an exam:
Let $q \ge 5$ be a prime number and assume that $p=2q+1$ is also prime. Prove that $-3$ is a primitive root in $\mathbb{Z}_p$.
I guess the solution goes something ...
- 2,863
5
votes
1
answer
516
views
Determine the number of solutions of $x^p\equiv 1\mod p^h$ using primitive roots
So the problem is to determine the number of solutions of the congruence $x^p\equiv 1\mod p^h$, where $p$ is an odd prime and $h\geq2$. We are asked to establish the result using primitive roots.
We ...
- 2,005
5
votes
2
answers
1k
views
Primitive roots modulo n
How do I find a primitive root for a given $n$?
For which $n$ does a primitive root exist (I would have guessed it's for all $n$ which are not divisible by 8)?
Is there a systematic way, to constuct ...
- 401
5
votes
1
answer
1k
views
Sums of Primitive Roots and Quadratic Residues when $p \equiv 3\pmod 4$
Define
$$R_{p}=\{ r \mid r: \text{primitive root of p}, 1 \le r \le p \}$$
and also
$$Q_{p}=\{ a \mid a: \text{quadratic residue of p}, 1 \le a \le p \}$$
$$Q_p^c=\{a \mid a: \text{...
- 1,452
5
votes
1
answer
2k
views
Efficient algorithms for Primitive roots where time-complexity is $\leq O(\sqrt{n})$
I have an algorithm for primitive roots for input number $n$ that I believe is $O(n)$ currently. I also have separate algorithms for $\varphi(n)$ and $factorise(n)$ which I believe are both $O(\sqrt{n}...
- 778
4
votes
2
answers
833
views
Solve $x^8 \equiv 3 \pmod {13}$
I need to find all solutions to $x^8 \equiv 3 \pmod {13}$.
What I've tried: I know $2$ is a primitive root modulo $13$.
So it is equivalent to solve
$2^{8t} \equiv 2^4 \pmod {13}$
Then I get $t = ...
- 949
4
votes
1
answer
227
views
Does Artin's conjecture imply that the reciprocal sum of primes with a given primitive root would diverge?
Artin conjectured that every non-square integer $a\ne -1$ is a primitive root for infinitely many primes. Here it is on Wikipedia: Artin's conjecture on primitive roots. The conjecture also includes a ...
- 30.6k
4
votes
1
answer
307
views
Are there infinitely many pairs of primes, $p$ and $q$, such that $q = 4p + 1$?
How close can one come to proving that there are infinitely many primes, $p$ and $q$, such that $q = 4p + 1$?
The idea for this question came from reading the question and answers posed by
user39898,...
- 1,479
3
votes
1
answer
1k
views
How to prove that $g$ or $g+p$ is a primitive root modulo $p^a$ for a primitive root $g$ modulo $p$?
I wish to prove the following:
If $p$ is an odd prime and $g$ is a primitive root modulo $p$, then either $g$ or $g+p$ is a primitive root modulo every power of $p$.
The only reference I can find ...
- 33
3
votes
1
answer
724
views
If $r$ is a primitive root mod $p$ and $(r+tp)^{p-1} \not \equiv 1 \pmod{p^2}$, then $r+tp$ is a primitive root mod $p^k$
Assume that $r$ is a primitive root of the odd prime $p$ and $(r+tp)^{p-1} \not\equiv 1 (\mod p^2)$.
show that $r+tp$ is a primitive root of $p^k$ for each $k \geq 1$.
How to check whether something ...
- 41
3
votes
2
answers
8k
views
Primitive elements of GF(8)
I'm trying to find the primitive elements of $GF(8),$ the minimal polynomials of all elements of $GF(8)$ and their roots, and calculate the powers of $\alpha^i$ for $x^3 + x + 1.$
If I did my math ...
- 261
3
votes
2
answers
3k
views
How to prove 2 is a primitive root mod 37, without calculating all powers of 2 mod 37?
How can i prove 2 is a primitive root mod 37, without calculating all powers of 2 mod 37?
- 65
3
votes
1
answer
817
views
primitive root mod25
Verify that 2 is a primitive root mod 25.
I just want to make sure my understanding of what a primitive root is is clear. So to show my work I calculated 2^1mod25 up to 2^24mod25, and showed that all ...
- 2,224
3
votes
1
answer
116
views
PRIMES in P paper - Lemma 4.7 - why are the polynomials $X^m$ distinct in $F$?
I'm working through the original AKS paper, available here: https://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf.
There's a single transition which I don't know how to justify, I will ...
- 1,091
2
votes
3
answers
379
views
Let $p$ be an odd prime. Suppose that $a$ is an odd integer and also $a$ is a primitive root mod $p$. Show that $a$ is also a primitive root mod $2p$.
Let $p$ be an odd prime. Suppose that $a$ is an odd integer and also
$a$ is a primitive root modulo $p$. Show that a is also a primitive root modulo
$2p$.
Any hints will be appreciated. Thanks very ...
- 3,721
2
votes
1
answer
159
views
If $r$ is a primitive root of $p$ and $p^2$, then show that it is also a primitive root of $p^3$
If $r$ is a primitive root of $p$ and $p^2$, then show that it is also
a primitive root of $p^3$
This is part of a bigger proof and I'm stuck at understanding this part.
Here some lines of proof from ...
- 599
2
votes
2
answers
434
views
If primitive root modulo $mn$, then primitive root modulo $m$ and $n$
Let $a$ be a primitive root modulo $mn$. Show that $a$ is also primitive root modulo $m$ and $n$.
Showing $(a,mn)=1\Longrightarrow (a,m)=(a,n)=1$ is not a problem. The problem is showing $a^{\varphi (...
- 7,833
2
votes
2
answers
798
views
Proof of Fermat's Little Theorem using Primitive Roots
I just learned about primitive roots today, and then I thought of this proof of Fermat's Little Theorem. Seeing that most proofs of this theorem aren't simple, I think I'm either completely wrong in ...
- 2,650
2
votes
4
answers
200
views
Primitive elements of $\mathbb{F}_5[X]/[X^2-2]$
I am trying to find a primitive elements of $\mathbb{F}_5[X]/(X^2-2)$, so I was thinking about checking all the powers of an element in this field and see if they yield all the non-zero elements in ...
- 331
1
vote
1
answer
454
views
Order of 2 modulo p, where p is a prime divisor of the Fermat number $F_n=2^{2^n}+1$
The order of 2 modulo p is the minimal solution of $2^t\equiv 1 \pmod{p}$
Euler's theorem guarantees that the congruence has a solution. The challenge is to demonstrate that $k=2^{n+1}$ is the minimal ...
- 406
1
vote
1
answer
59
views
Finding a counter-example for Gaussian-periods for non-primes
I need to give a counter-example against the following theorem:
Suppose $H \subset \operatorname{Gal}(\mathbb{Q}(\zeta_n)/\mathbb{Q})$ is a subgroup. Then we have $\mathbb{Q}(\zeta_n)^H = \mathbb{Q}(\...
- 1,579
1
vote
1
answer
262
views
Primitive roots used to work out $x^7 \equiv 5 \pmod {11}$
I have a workbook question that doesn't have any example solution, that is as follows:
Primitive roots used to work out $x^7 \equiv 5 \pmod {11}$
Now I can see $\phi(11)=10$ and $2$ has order $10$ ...
- 1,423