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.

Filter by
Sorted by
Tagged with
13
votes
3answers
4k 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
245 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$ ...
12
votes
4answers
7k 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)} \}$ ...
11
votes
2answers
24k 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 ...
11
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 ...
10
votes
4answers
241 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
0answers
325 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
201 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
3answers
125 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 ...
7
votes
1answer
203 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
2k 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 ...
6
votes
1answer
4k 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
votes
2answers
358 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
2answers
129 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
1answer
732 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
3answers
232 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 $...
6
votes
2answers
136 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 } (...
6
votes
1answer
289 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
2answers
96 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
198 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
119 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
2answers
2k 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$...
5
votes
2answers
612 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
1answer
51 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 $(...
5
votes
5answers
230 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
837 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
262 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
401 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
80 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
954 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
320 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
192 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
316 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 = ...
4
votes
3answers
494 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
221 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
5k 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 ...
4
votes
1answer
111 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 ...
4
votes
2answers
123 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
957 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 ...
4
votes
2answers
2k 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
3answers
79 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
1answer
94 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 ...
4
votes
1answer
84 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
1answer
150 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 ...
4
votes
2answers
57 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
120 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
3answers
65 views

Showing that $a$ is a primitive root modulo $p$ [duplicate]

Let $p > 2$ be a prime number with the property that $ q:= \frac{p-1}{2} $ is also prime. Let $a$ $ \in \mathbb{Z} $ with $$a \not\equiv 0,-1( \text{ mod }p )$$ How can I show that if $$ a^{\...
4
votes
1answer
3k 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
134 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
86 views

Is there any primitive root of $p$ which is not primitive root of $p^2$ without $1$? [closed]

Is there any primitive root of $p$ which is not primitive root of $p^2$ without $1$ (since $1$ is a primitive root of $2$ but $1$ is not a primitive root of $4$)? Are there other examples?

1
2 3 4 5
10