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

559 questions
Filter by
Sorted by
Tagged with
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
338 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$ ...
• 1,760
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
32k 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 ...
• 323
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
302 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 "...
• 4,443
230 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 ...
• 156
394 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 ...
• 3,917
7k views

219 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 ...
• 71
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
5k 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 ...
• 1,729
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
1k views

635 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 ...
• 393
601 views

### How to solve $x^3 \equiv 1 \pmod{37}$

We are asked to solve $x^3 \equiv 1 \pmod{37}$. I know that the answer is $10$ since $27\cdot37 = 999$ and $10^3 = 1000$ but how do I show this rigorously? If it helps, we are given the primitive ...
• 169
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 ...
253 views

• 351
223 views

### simplify a numerical expression without calculator

The following term: $$\sqrt{2017^2-2018^2+2019^2}$$ is the same as this term: $$\sqrt{2018^2+2}$$ how can one show without the need of a calculator that these are the same? The original question was ...
• 87
144 views

• 1,452
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
197 views

• 949
256 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. ...
• 303
8k views

### Relationship between primitive roots and quadratic residues

I understand that if $g$ is a primitive root modulo an odd prime $p$, then Euler's Criterion tells us that $g$ cannot be a quadratic residue. My question is, does this result generalize to prime ...
184 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 ...
343 views

### Distribution of primitive roots mod p

Let $p$ be a prime number. I am interested in knowing how many primitive roots mod $p$ there are; at least, gaining some insight into the distribution of primitive roots mod $p$. If I need to go ...
2k views

### Online primitive root modulo n list or tool?

Please does somebody know of an online list or tool (if possible server side, not a Java applet running in my computer) to calculate the primitive roots modulo n, for instance $n \in [1,1000]$ (apart ...
• 8,763
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
67 views

133 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 ...
98 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 ...
• 5,334
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 ...