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

385 questions
3answers
3k 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}$.
1answer
216 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$ ...
4answers
5k 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)} \}$ ...
4answers
218 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 "...
2answers
19k 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 ...
2answers
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 ...
0answers
279 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 ...
1answer
179 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 ...
1answer
197 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 ...
3answers
89 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 ...
2answers
316 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 ...
1answer
502 views

2answers
63 views

2answers
236 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 ...
3answers
187 views

### primitive roots problem. that integer n can never have exactly 26 primitive roots.

Show that no integer $n$ can have exactly 26 primitive roots. I know that if $n$ has primitive roots then it has exactly $\phi(\phi(n))$ primitive roots. I think the proof has to use contradiction. ...
2answers
109 views

### Solve $7^x \equiv 6 \pmod{17}$ given 3 is a primitive root $\bmod 17$

It's easy to show that 3 is a primitive root $\bmod 17$, but how do I use it prove the congruence? Is there a general way to solve any congruence of the form $a^x \equiv b \pmod{c}$ if you know a ...
2answers
1k 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 ...
1answer
67 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 ...
2answers
54 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 ...
1answer
111 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 ...
1answer
169 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$...
1answer
2k 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 ...
1answer
118 views

### Primitive root pairs

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$ ...
1answer
49 views

2answers
79 views

### Solve $x^2 = 2$ over $F_5$.

Since $F_5$ is isomorphic to $\Bbb Z_5$, I tried to solve this equation over $\Bbb Z_5$. Since $gcd(2,5)=1$, $\Bbb Z_5$ contains a primitive $2$nd root of unity. So if $\omega$ is the ...
3answers
563 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)^*$ ...
2answers
631 views

### Show that 7 is a primitive root modulo 601

How do you show that 7 is a primitive root modulo 601 without having to do many, many congruences? I'm sure there is an easier way and I should like very much to learn it.
2answers
249 views

### Find all the solutions of $y^2 \equiv 5x^3 \pmod 7$

I need to find all the solutions of $y^2 \equiv 5x^3 \pmod 7$. I managed to solve by trying one-by-one, but I guess there is some other way to solve this.