Questions tagged [primitive-roots]

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

Filter by
Sorted by
Tagged with
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-...
David R's user avatar
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 ...
Command Master's user avatar
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[-\...
Mastrem's user avatar
  • 458
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....
loqueelviento's user avatar
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 ...
anomaly's user avatar
  • 432
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}...
Kannan's user avatar
  • 11
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 \...
Favst's user avatar
  • 1,923
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^...
mathfan's user avatar
  • 11
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 ...
A.S.'s user avatar
  • 101
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 ...
Daniel Loughran's user avatar
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 ...
Asem Abdelraouf's user avatar
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(...
MegaOwIer's user avatar
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 ...
Daniel Santiago's user avatar
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 ...
Junsukim's user avatar
  • 141
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{...
Zhi-Wei Sun's user avatar
  • 14.3k
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} &...
Konstantinos Gaitanas's user avatar
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 ...
Arnold Neumaier's user avatar
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 ...
Mclalalala's user avatar
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 $$\...
Mikhail Goltvanitsa's user avatar
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 ...
Chebolu's user avatar
  • 575
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 ...
Joël's user avatar
  • 25.6k
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 ...
Charles Matthews's user avatar
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 $\...
Favst's user avatar
  • 1,923
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(...
Joël's user avatar
  • 25.6k
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 ...
Dima Pasechnik's user avatar
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 ...
Winnie's user avatar
  • 183
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$.
tim's user avatar
  • 111
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 ...
Hej's user avatar
  • 1,045
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 ...
David Loeffler's user avatar
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 ...
Zev Chonoles's user avatar
  • 6,702