Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

13
votes
3answers
3k 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}$.
13
votes
1answer
216 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$ ...
11
votes
4answers
5k 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)} \}$ ...
10
votes
4answers
218 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 "...
9
votes
2answers
19k 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 ...
9
votes
2answers
1k 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 ...
9
votes
0answers
279 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 ...
8
votes
1answer
179 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 ...
7
votes
1answer
197 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 ...
6
votes
3answers
89 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 ...
6
votes
2answers
316 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 ...
6
votes
1answer
502 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(...
6
votes
2answers
107 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 ...
6
votes
3answers
203 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 $37$...
6
votes
1answer
144 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 ...
5
votes
3answers
456 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
2answers
259 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 = ...
5
votes
2answers
63 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}_{...
5
votes
2answers
153 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 ...
5
votes
2answers
113 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\...
5
votes
1answer
3k 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 $\...
5
votes
2answers
454 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 ...
5
votes
5answers
158 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 ...
5
votes
1answer
196 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 ...
5
votes
1answer
341 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 ...
5
votes
1answer
425 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}...
5
votes
1answer
73 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 ...
5
votes
1answer
738 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{...
5
votes
1answer
231 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 ...
5
votes
0answers
189 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: \...
4
votes
2answers
236 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
votes
3answers
187 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. ...
4
votes
2answers
109 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 ...
4
votes
2answers
1k 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 ...
4
votes
1answer
67 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 ...
4
votes
2answers
54 views

Prove that $\gamma^{\frac{q-1}{2}}=-1$ in $\mathbb{F}_q$ when $q$ is an odd prime power and $\mathbb{F}_q^*=<\gamma >$.

I have written a proof for this, however I think there may be a simpler way to go about it and am curious for any suggestions. Also I don't fully see where my proof would fail if $q$ was even (other ...
4
votes
1answer
111 views

Primitive roots modulo primes congruent to n!

for $N \ge 4$. Show for prime numbers, $p \equiv 1$ mod $(N!)$ that none of the numbers $1,2,...,N$ are primitive roots modulo $p$ I can't figure out where to start with this question, all I can ...
4
votes
1answer
169 views

A question about a primitive root mod $p=2^{2^k}+1$, where $p$ is prime.

Let $p=2^{2^k}+1$ be a prime where $k\ge1$. Prove that the set of quadratic non-residues mod $p$ is the same as the set of primitive roots mod $p$. Use this to show that $7$ is a primitive root mod $p$...
4
votes
1answer
2k 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 ...
4
votes
1answer
118 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$ ...
4
votes
1answer
49 views

Show that $[-a^2]$ generates Up

I'm trying to show that $[-a^2]$ generates $U_p$, given that $1<a<p-1$ and p is an odd prime, $p=2q+1$ and q is also an odd prime. I know that $[-a^2]$ is a primitive root iff 1. $[-a^2]^{\phi(...
4
votes
0answers
193 views

Primitive element and choice of irreducible polynomial

It is known that every finite field of the same order $p^k$ are isomorphic. So, $F_p[x]/\langle q(x)\rangle$ leads to the same field for any choice of irriducible k-degree $q(x)$ over $F_p[x]$. But, ...
4
votes
1answer
181 views

Count of lower and upper primitive roots of prime $p \equiv 3 \bmod 4$

I was exploring the layout of primitive roots of primes over a reasonable range and this question concerns the number of primitive roots either side of $p/2$. Many primes have an exact match between ...
4
votes
0answers
90 views

About primitive roots and primes.

For any odd prime $p$ there exists at least one prime $q < p$ such that $q$ is a primitive root $\text{mod } p$ ; is this true?
3
votes
2answers
2k views

How to prove 2 is a primitive root mod 37, without calculating all powers of 2 mod 37?

How can i prove 2 is a primitive root mod 37, without calculating all powers of 2 mod 37?
3
votes
4answers
341 views

Number Theory: Find all incongruent solutions of $x^8\equiv3\pmod{13}$.

Find all incongruent solutions of $x^8\equiv3\pmod{13}$. I know that $2$ is a primitive root of $13$ and that $2^4\equiv3\pmod{13}$, so we want to solve $x^8\equiv2^4\pmod{13}$. Now, $\gcd(8,\phi(13)...
3
votes
2answers
79 views

Solve $ x^2 = 2$ over $ F_5 $.

Since $ F_5 $ is isomorphic to $ \Bbb Z_5 $, I tried to solve this equation over $ \Bbb Z_5 $. Since $ gcd(2,5)=1 $, $ \Bbb Z_5 $ contains a primitive $2$nd root of unity. So if $ \omega $ is the ...
3
votes
3answers
563 views

No primitive root modulo $2^n$ for $n\ge 3$

Prove that there is no primitive root modulo $2^n$. I'm not sure how to begin proving this. I know $\varphi(2^n)=2^{n-1}$, thus a primitive root $a\in\left(\dfrac{\mathbb{Z}}{2^n\mathbb{Z}}\right)^*$ ...
3
votes
2answers
631 views

Show that 7 is a primitive root modulo 601

How do you show that 7 is a primitive root modulo 601 without having to do many, many congruences? I'm sure there is an easier way and I should like very much to learn it.
3
votes
2answers
249 views

Find all the solutions of $y^2 \equiv 5x^3 \pmod 7$

I need to find all the solutions of $y^2 \equiv 5x^3 \pmod 7$. I managed to solve by trying one-by-one, but I guess there is some other way to solve this.