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
16
votes
4
answers
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
15
votes
1
answer
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
14
votes
2
answers
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
13
votes
2
answers
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
12
votes
5
answers
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
10
votes
4
answers
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
9
votes
1
answer
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
9
votes
0
answers
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
7
votes
1
answer
7k
views
Proof of existence of primitive roots
In my book (Elementary Number Theory, Stillwell), exercise 3.9.1 asks to give an alternative proof of the existence of a primitive root for any prime.
Let $p$ be prime, and consider the group $\...
- 6,392
7
votes
3
answers
233
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 ...
- 39.1k
7
votes
2
answers
709
views
Question about primitive roots of p and $p^2$
If $g$ is a primitive root of a prime $p$, then $g$ is also a primitive root of $p^2$ if and only if $g^{p-1} \pmod p^2$ is not $1$. Is there a prime $p$ such that $p^2$ missing exactly $m$ primitive ...
7
votes
3
answers
401
views
$p^2$ misses 2 primitive roots
When I Checked primitive roots of some primes P, I found this following phenomenon:
$14$ is a primitive root of prime $29$, but it's not primitive root of $29^2$
$18$ is a primitive root of prime $...
- 71
7
votes
1
answer
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
6
votes
3
answers
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
6
votes
1
answer
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
6
votes
2
answers
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
6
votes
1
answer
1k
views
Find a primitive root of $71$.
In my Number Theory Class we found that $7$ was a primitive root of 41 by first finding two integers who have order $5$ and $8$ $modulo 41$ respectively, these being $16$ and $3$. Since $16(3)=7(...
- 89
6
votes
2
answers
283
views
Find the smallest prime divisor of $1^{60}+2^{60}+...+33^{60}$
Find the smallest prime divisor of $1^{60}+2^{60}+...+33^{60}$.
I found a solution online, but I have a few questions:
In the beginning, the solver claims that $S^n = \begin{cases}S &\text{if } (...
user706791
6
votes
1
answer
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
6
votes
5
answers
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
5
votes
3
answers
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 ...
5
votes
2
answers
253
views
Show $2+\alpha$ is a primitive root of $\mathbb{F}_{25}$.
Suppose $\alpha \in \mathbb{F}_{25}$ is an element with $\alpha^2 = 2$, I need to prove that $2+\alpha \in \mathbb{F}_{25}$ is a primitive root (that is: a generator of the cyclic group $\mathbb{F}_{...
- 1,579
5
votes
2
answers
2k
views
Sum of powers mod p
I've this problem that I did halve of the proof but I can't do the rest of it.
Let $p$ be an odd prime. We define $S_n$ as $S_n = 1^n +2^n + ... +(p-1)^n$
Prove that
$S_n \equiv
\begin{cases}
...
- 351
5
votes
2
answers
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
5
votes
2
answers
144
views
Find the number of solutions of $x^k\equiv 45\pmod{97}$
Let $5$ be a primitive root of $97$ and $\text{ind}_5 (45)=45$ find the number of solutions of $x^k\equiv 45\pmod{97}$ where $k=7,8,9$
My attempt:
$$5^{45}\equiv 45 \pmod{97}$$
For $k=7:$
$$x^7\...
- 1,892
5
votes
2
answers
5k
views
Proving a number has no primitive roots
How do you prove an arbitrary number $n$ has no primitive roots without finding all numbers less than $n$ which are also coprime to $n$ and exhausting that none of the order of these numbers modulo $n$...
- 51
5
votes
2
answers
1k
views
Primitive roots modulo n
How do I find a primitive root for a given $n$?
For which $n$ does a primitive root exist (I would have guessed it's for all $n$ which are not divisible by 8)?
Is there a systematic way, to constuct ...
- 401
5
votes
1
answer
1k
views
Assuming that $r$ is a primitive root of the odd prime $p$ prove that $ r^{(p-1)/2}\equiv -1 \pmod p $ holds
I know if $r$ is primitive root $r^{^{n}}\equiv a\pmod n$
from the set of residue $\{1,2,3....(n-1)\}$ but if change to $r^{(p-1)/2}\equiv -1 \pmod p$.
My assumption: It's no longer be primitive ...
- 1,729
5
votes
1
answer
55
views
Maximal order with primitive determinant in $\operatorname{GL}_n(\mathbb{F}_q)$
The following question has come up in a facet of a current project. Having an answer (hopefully affirmative) will help me design and test some computational simulations.
$\mathbb{F}_q$ denotes the ...
- 17.5k
5
votes
1
answer
2k
views
Efficient algorithms for Primitive roots where time-complexity is $\leq O(\sqrt{n})$
I have an algorithm for primitive roots for input number $n$ that I believe is $O(n)$ currently. I also have separate algorithms for $\varphi(n)$ and $factorise(n)$ which I believe are both $O(\sqrt{n}...
- 778
5
votes
1
answer
200
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$ ...
- 131
5
votes
1
answer
418
views
Chinese reminder Theorem and primitive roots
The problem I am working on is "Let $p$ be a prime such that $p\equiv 1\pmod{105}$. Show that there exist integers $n, x, y, z$ such that $p$ does not divide $n$ and $n \equiv 3x^3 \equiv 5y^5 \equiv ...
- 391
5
votes
1
answer
581
views
Conjecture about the product of the primitive roots modulo a prime number ($\prod Pr_p$)
While I was learning about the primitive roots modulo $p \in \Bbb P$ (I will call $Pr_p$ to the complete list of the primitive roots module $p$) and having in mind the conjecture explained in this ...
- 8,763
5
votes
1
answer
108
views
Is there a counterexample? $\forall p \in \Bbb P\ ,\ p\gt 61\ ,\ \exists\ r1,r2\ \in \{\ Primitive\ Roots\ Modulo\ p\ \}\ /\ r1+r2 = NextPrime(p)$
This is the weirdest thing I have observed so far! Take the set of Primitive Roots Modulo p (link to definition here) of a prime number $p$, $Pr(p)$. For those primes $p \gt 61$ there is always a pair ...
- 8,763
5
votes
1
answer
1k
views
Sums of Primitive Roots and Quadratic Residues when $p \equiv 3\pmod 4$
Define
$$R_{p}=\{ r \mid r: \text{primitive root of p}, 1 \le r \le p \}$$
and also
$$Q_{p}=\{ a \mid a: \text{quadratic residue of p}, 1 \le a \le p \}$$
$$Q_p^c=\{a \mid a: \text{...
- 1,452
5
votes
1
answer
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
5
votes
0
answers
197
views
Spliting subspaces and finite fields
I'm sure that the following is true, but I can't prove it.
Let $R<S<K, R=\mathrm{GF}(q),\ S= \mathrm{GF}(q^n), \ K= \mathrm{GF}(q^{mn})$ be a tower of finite fields and
$A = \{\theta\in K: \...
- 1,284
4
votes
2
answers
833
views
Solve $x^8 \equiv 3 \pmod {13}$
I need to find all solutions to $x^8 \equiv 3 \pmod {13}$.
What I've tried: I know $2$ is a primitive root modulo $13$.
So it is equivalent to solve
$2^{8t} \equiv 2^4 \pmod {13}$
Then I get $t = ...
- 949
4
votes
3
answers
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
4
votes
2
answers
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 ...
- 51
4
votes
2
answers
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 ...
- 737
4
votes
1
answer
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 ...
user256340
4
votes
2
answers
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
4
votes
2
answers
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
4
votes
1
answer
67
views
Existence of primitive root satisfying a certain condition
Let $l$ and $p$ be prime numbers such that $p|l-1$. Suppose there is an integer $r \in \mathbb Z$ such that $r^p \equiv 1 $ mod $l$. Can anyone please help me see why there exists a generator $s$ of $(...
- 419
4
votes
1
answer
248
views
If $p$ is an odd prime and $\alpha\in\Bbb Z/p\Bbb Z^*$, then $\alpha^2$ is not a primitive root modulo $p$.
Prove true or give a counterexample if false.
If $p$ is an odd prime and $\alpha\in\Bbb Z/p\Bbb Z^*$, then $\alpha^2$ is not a primitive root modulo $p$.
I was trying to prove it to be true, but I ...
- 71
4
votes
3
answers
108
views
Sum of complex roots' fractions
According to this:
If $\omega^7 =1$ and $\omega \neq 1$ then find value of
$\displaystyle\frac{1}{(\omega+1)^2} +
\frac{1}{(\omega^2+1)^2} +
\frac{1}{(\omega^3+1)^2} +
... + \frac{1}{(\omega^6+1)^2}=...
4
votes
1
answer
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 ...
- 153k
4
votes
1
answer
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
4
votes
1
answer
227
views
Does Artin's conjecture imply that the reciprocal sum of primes with a given primitive root would diverge?
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 ...
- 30.6k