# 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
Filter by
Sorted by
Tagged with
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
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
7k views

• 1,579
2k views

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
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
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
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
2k views

• 949
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
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
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
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
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 ...
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?
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
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
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
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
434 views

• 1,579
1 vote
### 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$ ...