28 votes
Accepted

State of the art for primitive roots

Artin's conjecture on primitive roots has a qualitative version and quantitative version. The qualitative version says if $a \in \mathbf Z$ is not $-1$ or a perfect square then $a \bmod p$ is a ...
KConrad's user avatar
  • 49.6k
25 votes
Accepted

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

We do not know that. It is typical for questions about the infinitude of primes satisfying some property that even proving the existence of at least one of those primes in sufficient generality is ...
KConrad's user avatar
  • 49.6k
17 votes

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

Both Gauss' generalization, and the classification of moduli with primitive roots, are 'shadows' of the structural theory of the finite abelian group $G_m:=(\mathbb{Z}/m\mathbb{Z})^{\times}$. Gauss' ...
Ofir Gorodetsky's user avatar
17 votes

Weakened version of the Artin's primitive root conjecture

Since Joe Silverman raised the possibility of variations of the question, I want to point out (as a long comment) that even a mild variation $$ \sum_{p } \frac{1}{ \operatorname{ord}_p(2)^2 \log ( \...
Will Sawin's user avatar
  • 137k
14 votes

Weakened version of the Artin's primitive root conjecture

Not quite what you've asked for, but in case it helps in whatever application you have in mind: $$ \sum_{p~\text{prime}} \frac{\log p}{p \operatorname{ord}_p(a)^\epsilon} \le \log\log a + \frac{2}{\...
Joe Silverman's user avatar
12 votes

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

Expanding on a comment, the curve $X^4+Y^4=aZ^4$ (for $a\ne0$) has genus $3$. So the Hasse-Weil bound says $$ N_p(a) := \#\bigl\{ [X,Y,Z]\in\mathbb P^2(\mathbb F_p) : X^4+Y^4=aZ^4 \bigr\} $$ satisfies ...
Joe Silverman's user avatar
12 votes
Accepted

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

I will show the two results are non-superficially related by showing one of them implies the other: the classification of moduli $n \geq 2$ for which the unit group $(\mathbf Z/(n))^\times$ is cyclic ...
KConrad's user avatar
  • 49.6k
11 votes
Accepted

Arithmetic sequences and Artin's conjecture

It's plausible that there are infinitely many primes $p \equiv 1 \bmod 4$ of which $2$ is a primitive residue. However, this is false for $p \equiv \pm 1 \bmod 8$, because $2$ is a quadratic residue. ...
Noam D. Elkies's user avatar
8 votes
Accepted

list of primes for which 2 is a primitive root

The sequence of primes for which 2 is a primitive root is OEIS A001122. It contains a list for the first 10.000 entries, which goes up to $N=310091$. I'm not sure if that is sufficient for you, but it'...
Glorfindel's user avatar
  • 2,743
6 votes
Accepted

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

emtom has found the right reference, but there is a more explicit result in that book (Ireland and Rosen, A Classical Introduction to Modern Number Theory). In fact, Theorem 5 of Chapter 8 (on page ...
R.P.'s user avatar
  • 4,745
5 votes
Accepted

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

Throughout, let $R$ be a Noetherian ring and $I \subseteq R$ an ideal such that $R/I$ is finite. Then $R/I$ is Artinian, so we may write $I = I_1 \cdots I_r$ with $I_i = \mathfrak m_i^{n_i}$ where $\...
R. van Dobben de Bruyn's user avatar
5 votes

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

Not exactly an answer, but in exercise $18$ in page $106$ of Ireland and Rosen's A Classical Introduction to Modern Number theory it states: Let $p\equiv 1\mod 4$ and let $p=A^2+B^2$ where we fix $A$ ...
emtom's user avatar
  • 51
4 votes

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

$\newcommand{\F}{\mathbb{F}} \newcommand{\Z}{\mathbb{Z}}$ [Throughout this answer all rings will be commutative (and unital!).] It seems that van Dobben de Bruyn has essentially rediscovered a ...
Pete L. Clark's user avatar
4 votes
Accepted

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

As pointed out in the comments, primitive roots with a single cycle appear to be rather common. The standard heuristic argument suggests that there are infinitely many such $p$, and a bit more. The ...
Victor Protsak's user avatar
2 votes

How to prove an approximation of a combinatorics identity

You could show that it is one of $r$ approximately equal things which add to $2^n.$ You might also bound how far apart they can be from each other. This is really pretty much what Fedor said but the ...
Aaron Meyerowitz's user avatar
2 votes
Accepted

Bases of the special form

Let me estimate the number $N_k$ of such bases for a fixed $k$. Aside remark. The number of bases for $k=k_0$ equals the number of those for $k=n-k_0$, as the bijection $(\beta_0,\dots,\beta_{n-1})\to ...
Ilya Bogdanov's user avatar
1 vote
Accepted

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

Consider the double sum on the right-hand side. If $n$ is a square, then $e+f+g+h$ is even, hence its contribution is asymptotically $\pi(x)$. If $n$ is not a square, then its contribution is $o(\pi(x)...
GH from MO's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible