# Questions tagged [primitive-roots]

For questions related to primitive roots, the generators of the multiplicative group of integers modulo n.

30
questions

0
votes

1
answer

100
views

### On a summation in "Artin's conjecture for primitive roots" by Heath-Brown

This is a question on the paper: D. R. Heath-Brown. Artin's conjecture for primitive roots. Quarterly J. Math. 37 (1): 27–38, 1986.
At the beginning of the proof of his main theorem on page 35, Heath-...

0
votes

0
answers

179
views

### Efficiently count the number of primitive roots in all moduli up to $n$

Let's define $f(n)$ as the number of primitive roots modulo $n$. That is, $f(n) = \begin{cases}\varphi(\varphi(n))&n=1,2,4,p^k,2p^k\\0&\text{otherwise}\end{cases}$. We want to efficiently ...

8
votes

0
answers

237
views

### Explanation for the sum of primitive roots modulo $p$ (taken from $[-(p-1)/2,(p-1)/2]$) being positive way more often than being negative?

An earlier version of this question received a few upvotes but no answers on math.stackexchange.
For $p$ an odd prime, let $S(p)$ denote the sum of the primitive roots modulo $p$, taken from $\left[-\...

8
votes

1
answer

1k
views

### For a non-square, is there a prime number for which it is a primitive root?

For a natural number not a perfect square, is there always at least a prime number for which it is a primitive root?
Artin's conjecture on primitive roots is that there are infinitely many such primes....

10
votes

1
answer

1k
views

### State of the art for primitive roots

I was recently compiling some notes for an undergrad-level course on number theory, and I went over the proof of the fact that $(\mathbb{Z}/p\mathbb{Z})^\times$ is cyclic for any prime $p$: it's a ...

1
vote

0
answers

158
views

### Units in residue classes modulo prime ideal

Let $K$ be a number field and $\mathcal{O}_K$ be its ring of integers with unit rank $\geq 1$. For a given prime ideal $\mathfrak{p}$, shall we say that the map $\mathcal{O}_K^\times \to (\mathcal{O}...

11
votes

2
answers

2k
views

### Is Gauss's generalization of Wilson's theorem non-superficially related to the classification of moduli for which primitive roots exist?

Wilson's theorem (actually proven by Lagrange) from elementary number theory states that: If $n\ge 2$ is an integer, then
$$
(n-1)! \equiv
\begin{cases}
\hfill -1 \pmod {n} &\text{ if } n \...

1
vote

0
answers

233
views

### How to show the minimal polynomial of primitive n-th root of unity on prime field with characteristic p is the following? [closed]

How to show : w, the primitive n-th root of unity over prime field F with characteristic p, gcd(n,p)=1, is $(x-w)(x-w^p)(x-w^{p^2})...(x-w^{p^{r-1}})$ where r is the smallest positive integer s.t. $p^...

10
votes

0
answers

235
views

### Some variants of Artin's primitive root conjecture

Artin's primitive root conjecture asserts that if an integer $a \ne -1$ is not a perfect square then $a$ is a primitive root mod $p$ for infinitely many primes $p$. This conjecture is still open.
An ...

16
votes

2
answers

962
views

### Weakened version of the Artin's primitive root conjecture

$\DeclareMathOperator{\ord}{ord}$Artin's conjecture stipulates that $\ord_p(2) = p -1$ for infinitely many primes $p$, where $\ord_p(2)$ denotes the multiplicative order of $2$ modulo $p$. More ...

1
vote

0
answers

225
views

### A question related to Artin's Conjecture

I have the following question:
Given an integer $n \ge 1 $ which is not a square, does there exist a prime number $p$ for which $n$ is a primitive root modulo $p?$
It is easy to see that if $n$ is a ...

5
votes

1
answer

596
views

### The smallest primitive root modulo powers of prime

I wrote a program to calculate the minimal primitive root modulo $p^a$ where $p > 2$ is a prime, by enumerating $g$ from $2$ and checking whether it's a primitive root, but I forgot to check $\gcd(...

5
votes

2
answers

383
views

### Do there exist general conditions for cyclicity of unit groups of quotient rings (generalizations of the primitive root theorem)?

Let $R$ by a commutative ring with $1$, and $I \subset R$ a non-zero integral ideal in $R$. When $R$ has finite quotients, and $I = P$ is prime in $R$, the group of units $(R/P)^{\times}$ of the ...

9
votes

3
answers

621
views

### Does the expression $x^4 +y^4$ take on all values in $\mathbb{Z}/p\mathbb{Z}$?

As the title asks: does there exist $N$ such that, for any prime $p$ larger than $N$, the expression $x^4 +y^4$ takes on all values in $\mathbb{Z}/p\mathbb{Z}$?
I have been thinking about this ...

4
votes

0
answers

155
views

### Primitive roots modulo primes related to Fibonacci numbers or Lucas numbers

The Fibonacci numbers $F_0,F_1,F_2,\ldots$ and the Lucas numbers $L_0,L_1,L_2,\ldots$ are given by
$$F_0=0,\ F_1=1,\ \text{and}\ F_{n+1}=F_n+F_{n-1}\ (n=1,2,3,\ldots)$$
and
$$L_0=2,\ L_1=1,\ \text{...

6
votes

1
answer

294
views

### Can a primitive root-permutation of $A=\{1, 2, \ldots, p-1 \}$ be a cycle of length $p-1$ only for finitely many $p$?

Let $p$ be an odd prime, $g$ a primitive root of $p$ and $A=\{1, 2, \ldots, p-1 \}$.
Obviously, $\sigma_g(p)=\begin{pmatrix}
1 & 2 & \ldots & {p-1} \\
g^1\pmod{p} & g^2\pmod{p} &...

3
votes

1
answer

2k
views

### list of primes for which 2 is a primitive root

I am looking for a list of primes $\le N$ for which 2 is a primitive root, with $N$ as large as available. I know of a table of smallest primitive roots for all primes below 1000, from which such a ...

2
votes

1
answer

202
views

### How to prove an approximation of a combinatorics identity

How to prove that $$\sum_{k\ge 0} \binom{n}{rk} =\frac{1}{r}\sum_{j=0}^{r-1}(1+w^j)^n$$ can be approximated as $\frac{2^n}{r}$, where $n\ge 0$, $r\ge 0$, $n>r$ and $w^r=1$ is a primitive $r$-th ...

2
votes

1
answer

125
views

### Bases of the special form

Let $R = \mathrm{GF}(q)$, $S = \mathrm{GF}(q^n), \ n\geq 2$ be extension of $R$, $h$ be a primitive element of $S$. I want to count or estimate the number $N$ of bases of the following form.
Let $$\...

7
votes

0
answers

793
views

### Primes for which 2 is a primitive root

I am writing a paper in which I keep referring to primes p for which 2 is a primitive root mod p and so I want to give a name for these primes. Is there a name for these primes in the literature ...

3
votes

1
answer

531
views

### Least non primitive root

There is an abundant literature, and even here on MO no shortage of questions, on the question of the smallest prime primitivee root modulo $q$ (where $q$ is a prime, or more generally
an odd prime ...

8
votes

2
answers

557
views

### Proof theory and primitive roots

I have had this question on my mind for two decades. We know, after Heath-Brown, that one out (say) of 3, 5, 7 is a primitive root mod p for infinitely many primes p. We just don't know which one. (We ...

0
votes

1
answer

250
views

### Order of difference of two generators of cyclic group

Let $n\in\mathbb{Z}^+$ and $\alpha,\beta $ be two generators of the cyclic group $\left(\frac{\mathbb{Z}}{(2^n - 1)\mathbb{Z}},+\right)$.
Question: What are known theorems regarding the order of $\...

9
votes

1
answer

2k
views

### Least prime primitive root

For $p$ a prime number, let $G(p)$ be the least prime $q$ such that $q$ is a primitive root mod $p$, that is $q$ generates the multiplicative group $(\mathbb Z/p\mathbb Z$)* .
Is it known that $G(...

3
votes

1
answer

477
views

### primitive root 2 in (Z/pZ)* for prime p and generating GF(2^{p-1})

It appears (from computer experiments) that if $p$ is a prime such that 2 generates the multiplicative group $\mathbb{F}_p^\times$ of the corresponding finite field $\mathbb{F}_p$, then the ...

10
votes

2
answers

759
views

### Approximate primitive roots mod p

Artin conjectured that if $a$ is an integer which is not a square and not $-1$ then $a$ is a primitive root for infinitely many primes. This conjecture has not been resolved, but partial results are ...

11
votes

2
answers

2k
views

### primitive roots and primes

Given a positive integer $n > 1$, is it true that there exists infinitely many primes $p$ such that $n$ is a primitive root modulo $p$.

26
votes

2
answers

1k
views

### Primitive roots

If Artin's conjecture on primitive roots is true, then 2 generates $(\mathbb{Z}/p\mathbb{Z})^\times$ for infinitely many primes $p$. Can one at least show that $(\mathbb{Z}/p\mathbb{Z})^\times$ is ...

15
votes

4
answers

3k
views

### Is the smallest primitive root modulo p a primitive root modulo p^2?

Let $p \ne 2$ be a prime and $a$ the smallest positive integer that is a primitive root modulo $p$. Is $a$ necessarily a primitive root modulo $p^2$ (and hence modulo all powers of $p$)? I checked ...

2
votes

3
answers

1k
views

### Generalization of primitive roots

The standard definition is that $a\in\mathbb{Z}$ is a primitive root modulo $p$ if the order of $a$ modulo $p$ is $p-1$.
Let me rephrase, to motivate my generalization: $a\in\mathbb{Z}$ is a ...