# 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.

488 questions
Filter by
Sorted by
Tagged with
4k 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}$.
245 views

### Are there infinitely many primes $n$ such that $\mathbb{Z}_n^*$ is generated by $\{ -1,2 \}$?

Let $n$ a prime, and let $\mathbb{Z}_n$ denote the integers modulo $n$. Let $\mathbb{Z}^*_n$ denote the multiplicative group of $\mathbb{Z}_n$ Are there infinitely many $n$ such that $\mathbb{Z}^*_n$ ...
7k 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)} \}$ ...
24k views

### What are primitive roots modulo n?

I'm trying to understand what primitive roots are for a given $\bmod\ n$. Wolfram's definition is as follows: A primitive root of a prime $p$ is an integer $g$ such that $g\ (\bmod\ p)$ has ...
1k 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 ...
241 views

### Any element of $\mathbf{Z}[\xi]$ is congruent to an integer modulo $(1-\xi)^2$ if multiplied by a suitable power of $\xi$

I'm currently reading Kummer's famous paper on Fermat's Last Theorem (if anyone wants the link, I'll post it, but the paper is in German). There's the following statement in there, which should be "...
325 views

### Number of primitive roots mod $p$ that are not primitive roots mod $p^2$

Consider the primitive roots of a prime $p$ in the range $1...p$ which are not primitive roots mod $p^2$. Let $n(p)$ be this number. While looking for an answer to this question, it seems that the ...
201 views

### AMM 2488: Primitive Root Relatively Prime to p-1

(from American Mathematical Monthly, problem 2488. I hope this hasn't been posted before but I'm new and maybe not very good at using the search function effectively..) Let $p>3$ be a prime. Show ...
125 views

### Reluctant roots: $n$ is a primitive root of $p$ but not of $p^2$

I was looking at the primitive roots $n \bmod p$ and $p^2$ to see how often we get primitive roots of a prime that are not primitive roots of the square of that prime. I'll call this a reluctant root ...
203 views

### Find the last digit of the exponent $x$.

Let \begin{align} p&=396543857870745963499374527519378569849832249490600276007703072957912\cdots\\ &\phantom{=}8049490077183813353745228056691 \end{align} This number is a 100-digit prime ...
2k 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 ...
4k views

232 views

289 views

### Prove that there are infinitely many primes which are primitive roots modulo $N$

Assuming $N$ has a primitive root, show that there are infinitely many primes which are primitive roots modulo $N$. It is obviously true using Dirichlet's theorem on primes, but I want to prove ...
96 views

316 views

94 views

### A general type of generator of the multiplicative group of a finite field

Let $p>2$ be a prime number and $\alpha \in \overline{\mathbb{F}_p}$. It generates a finite field $\mathbb{F}_p(\alpha)$. Is there some $u \in \mathbb{F}_p$ such that $\alpha + u$ is a generator ...
84 views

### Prove that $\eta - \omega \notin \mathbb{Q}$ where $\omega$ and $\eta$ are two differents n-th primitive roots $\in \mathbb{C}$

Let $n \in \mathbb{N}$ be a natural number, and be $\omega$ and $\eta$ two differents n-th primitive roots in $\mathbb{C}$. Prove that $\eta - \omega \notin \mathbb{Q}$ My attempt was to follow the ...
150 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 ...
57 views

### Prove that $\gamma^{\frac{q-1}{2}}=-1$ in $\mathbb{F}_q$ when $q$ is an odd prime power and $\mathbb{F}_q^*=<\gamma >$.

I have written a proof for this, however I think there may be a simpler way to go about it and am curious for any suggestions. Also I don't fully see where my proof would fail if $q$ was even (other ...
120 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 ...
65 views

Let $p > 2$ be a prime number with the property that $q:= \frac{p-1}{2}$ is also prime. Let $a$ $\in \mathbb{Z}$ with $$a \not\equiv 0,-1( \text{ mod }p )$$ How can I show that if $$a^{\... 1answer 3k views ### Every primitive root modulo an odd prime is a quadratic nonresidue This is my proof of the title statement. Is it correct? Suppose a is a primitive root and quadratic residue modulo p. Then by definition$$\operatorname{ord}_p(a)=p-1 But Euler's ...
Looking at the Wikipedia entry for Primitive roots modulo $n$, I noticed that for some $n$, they came in pairs: When $n=p^k$ or $2p^k$ and $p\equiv1 \mod{4}$, then $r$ is a primitive root iff $n-r$ ...
### Is there any primitive root of $p$ which is not primitive root of $p^2$ without $1$? [closed]
Is there any primitive root of $p$ which is not primitive root of $p^2$ without $1$ (since $1$ is a primitive root of $2$ but $1$ is not a primitive root of $4$)? Are there other examples?