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.

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)} \}$ ...
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 $\...
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 ...
4
votes
1answer
182 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 ...
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}$.
2
votes
2answers
1k views

Prove that 3 is a primitive root of $7^k$ for all $k \ge 1$

so I am trying to find out how to prove that 3 is a primitive root of $7^k$ for all $k \ge 1$. I am trying to prove this via induction. Thanks.
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 ...
5
votes
1answer
345 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 ...
4
votes
2answers
237 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
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
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 ...
3
votes
1answer
765 views

If $r$ is a primitive root of odd prime $p$, prove that $\text{ind}_r (-1) = \frac{p-1}{2}$

If $r$ is a primitive root of odd prime $p$, prove that $\text{ind}_r (-1) = \frac{p-1}{2}$ I know $r^{p-1}\equiv 1 \pmod {p} \implies r^{(p-1)/2}\equiv -1 \pmod{p}$ But some how I feel the ...
0
votes
2answers
1k views

If $p$ and $q = 2p + 1$ are both odd primes, show that $-4$ and $2(-1)^{(1/2)(p-1)}$ are both primitive roots modulo $q$.

If $p$ and $q = 2p + 1$ are both odd primes, show that $-4$ and $2(-1)^{(1/2)(p-1)}$ are both primitive roots modulo $q$. I cannot get heads nor tails of how to even start this let alone finish it
3
votes
3answers
577 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)^*$ ...
1
vote
2answers
114 views

When g and -g are both primitive roots

The question states: Let $g$ by a primitive root of the odd prime $p$. Show that $-g$ is a primitive root , or not, according as $p \equiv 1 \pmod 4$ or not. For me, I cannot see any connection ...
0
votes
1answer
194 views

prove that $\zeta^{i}$ is a primitive root $modulo(p)$ $\iff$ $\gcd(p-1,i) =1$ where $p$ is prime and $\zeta$ is a primitive root modulo p.

I was going to use a case by case proof, but i am relativley new to primitive roots and I couldnt see how to sufficiently prove either case.
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?
6
votes
3answers
207 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$...
2
votes
1answer
155 views

Are there infinitely many pairs of primes, $p$ and $q$, such that $q = 4p + 1$?

How close can one come to proving that there are infinitely many primes, $p$ and $q$, such that $q = 4p + 1$? The idea for this question came from reading the question and answers posed by user39898,...
2
votes
2answers
475 views

Proof of Fermat's Little Theorem using Primitive Roots

I just learned about primitive roots today, and then I thought of this proof of Fermat's Little Theorem. Seeing that most proofs of this theorem aren't simple, I think I'm either completely wrong in ...
2
votes
1answer
91 views

Let $p$ be a prime number. Show that the number of solutions to $x^k \equiv 1 \pmod p$ is $gcd(k, p-1)$

I'm really not convinced by my own proof of this. Would appreciate a critique/reformulation using the ideas I already introduced. First note that $a^k \equiv 1 \mod p \implies k\ |\ p -1$ by Fermat's ...
1
vote
2answers
198 views

Product of quadratic residues in terms of primitive root

Let $a$ be a primitive root for prime $p(\geq 3)$. Show that the product of all non-zero quadratic residues is congruent to $a^\frac{p^2−1}{4}$ and that the product of quadratic nonresidues is ...
5
votes
1answer
740 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
2answers
455 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 ...
3
votes
1answer
261 views

primitive root mod25

Verify that 2 is a primitive root mod 25. I just want to make sure my understanding of what a primitive root is is clear. So to show my work I calculated 2^1mod25 up to 2^24mod25, and showed that all ...
3
votes
1answer
295 views

If $r$ is a primitive root mod $p$ and $(r+tp)^{p-1} \not \equiv 1 \pmod{p^2}$, then $r+tp$ is a primitive root mod $p^k$

Assume that $r$ is a primitive root of the odd prime $p$ and $(r+tp)^{p-1} \not\equiv 1 (\mod p^2)$. show that $r+tp$ is a primitive root of $p^k$ for each $k \geq 1$. How to check whether something ...
2
votes
2answers
123 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} ...
2
votes
3answers
164 views

Let $p$ be an odd prime. Suppose that $a$ is an odd integer and also $a$ is a primitive root mod $p$. Show that $a$ is also a primitive root mod $2p$.

Let $p$ be an odd prime. Suppose that $a$ is an odd integer and also $a$ is a primitive root modulo $p$. Show that a is also a primitive root modulo $2p$. Any hints will be appreciated. Thanks very ...
1
vote
1answer
908 views

Prove that $a$ is a primitive root $\bmod{p}$ if and only if $-a$ has order $\frac{p-1}{2}$

Consider a prime $p$ $\in\mathbb{N}$ of the form $4t+3$, with $t$ $\in\mathbb{N}$. Prove that a $\in\mathbb{Z}$ is a primitive root $\mod p$ if and only if $-a$ has order $\frac{(p-1)}{2}$. I showed ...
1
vote
1answer
283 views

Show that $α^k$ is also a primitive element if and only if gcd$(k, q − 1) = 1$.

Let $α$ be a primitive element of $F_q$ . Show that $α^k$ is also a primitive element if and only if gcd$(k, q − 1) = 1$. $1=ak+b(q-1) \implies α^1=α^{(ak+b(q-1))}=α^{(ak)}α^{(q-1)}a=α^ka=α$ i cant ...
1
vote
1answer
38 views

Showing two different definitions of a primitive root are the same

In a book im reading the following definition is given for a primitive root: "An integer $a$ is called a primitive root mod $p$ if $\overline{ a }$ generates the group $U(\mathbb{Z}/p\mathbb{Z})$. ...
1
vote
1answer
110 views

Solving a congruence using primitive roots

Suppose we know that $3$ is a primitive root of $17$. How can that help us solving $7^x \equiv 6 \pmod {17}$?
1
vote
4answers
113 views

To show congruence $3^8 \equiv -1 \pmod{17}$

How to show that $3^8 ≡ -1 \pmod{17}$. I have tried by using value of $3^8$ but is there any other method available for solving when more higher powers are included ?
0
votes
1answer
147 views

Odd prime factors of $n^2+1$ are congruent to $1 \bmod 4$

Show that prime factors of $n^2+1$ are congruent to $1 \bmod 4$ Solution: I think that if I denote $g$ as a primitive root, I know that the order of $g=p-1$ In other words, since $g^{p-1}\equiv 1\...
0
votes
0answers
60 views

Relation between residues and primitive roots modulo $p$

I got a very satisfiying answer to my question on the relation between primeness and co-primeness of numbers which can be defined in a somehow symmetric way: $n$ is prime iff $$(\forall xy)\ ...
0
votes
1answer
1k views

How does one find the primitive roots of a non-prime number? [closed]

Several algorithms exist to find the primitive roots of prime numbers. How does one find the primitive roots of a non-prime number?
0
votes
1answer
35 views

$|\{1≤x≤p^2:p^2│x^{p-1}-1\}|=p-1$ [duplicate]

Let $p$ be a prime number. Let $S_p=\{1≤x≤p^2:p^2│x^{p-1}-1\}$. Prove that $|S_p|=p-1$. I managed to prove that $|S_p|\geq p-1$. I took $g$, a primitive root modulo $p^2$, and then proved that $\...
0
votes
1answer
65 views

primitive roots $g^a \mod{p}$

$p$ prime, $g$ primitive root $\mod{p}$, $0 \leq a \leq p-2$ Show: $g^a \mod{p}$ is a primitive root $\mod{p}$ $\Leftrightarrow$ gcd($a,p-1) = 1$ Ideas: $g^a \mod{p}$ is a primitive root if $ord(...