# 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.

401 questions
Filter by
Sorted by
Tagged with
392 views

### Understanding Primitive roots

I am trying to find a single primitive root modulo $11$. The definition in my textbook says "Let $a$ and $n$ be relatively prime integers with ($a \neq 0$) and $n$ positive. Then the least ...
36 views

29 views

### Let $g$ be a primitive root modulo $p^e$ for some $p$ prime, $e\geq 1$, show that gcd$(g,p)=1$

So far I've got: Suppose gcd$(p,g)\neq 1$, so $p\mid g$ and hence $p^e\mid g^e$ so $g^e\equiv 0$ (mod $p^e$) Also $g^{p^{e-1}(p-1)}\equiv 1$ (mod $p^e)$ because $g$ is a primitive root. Not sure ...
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 ...
771 views

### What does “maximum order elements to mod n” mean for a number n without primitive roots modulo n?

I apologize because probably this is trivial, but I do not understand the concept: "maximum order elements to mod n for n". This is the context: in the Wikipedia in the primitive roots modulo n ...
350 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 ...
656 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 ...
210 views

64 views

64 views

### $g^q-q$ and $g^q-gq$ are primitive roots modulo $q^2$

Let $g$ be a primitive root modulo an odd prime $q$. Then, both $g^q-q$ and $g^q-gq$ are primitive roots modulo $q^2$. I read this question somewhere and the first thing that came to my mind as a ...
150 views

### Proving $\frac{p-1}{2}$ is a primitive root modulo $p$ if and only if $2(-1)^{(p-1)/2}$ is a primitive root modulo $p$

Let $p$ be an odd prime. Prove that $\frac{p-1}{2}$ is a primitive root modulo $p$ if and only if $2(-1)^{(p-1)/2}$ is a primitive root modulo $p$. I was thinking that since $\frac{p-1}{2}$ is a ...
368 views

### primitive roots and quadratic residues

prove that if p congruent to 3 (mod 4) is a prime and g is a primitive root mod p, then p - g is not a primitive root mod p. p-g must be congruent to g^m mod p for some m, and if i want to show p - g ...
2k views

### Finding order of an integer with (mod 9)?

I am trying to solve a problem to find the order of some integers with (mod 9). I understand the concept I also have the solution to the problem. My calculations are also correct except for a few ...
925 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 ...
79 views

### How do I prove this statement about $n^\text{th}$-power residues?

I am studying A Classical Introduction to Modern Number Theory by Ireland and Rosen, and the authors leave the proof of the following proposition (4.2.2) as "an exercise" ... Suppose that $a$ is ...
243 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 ...
203 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. ...
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 ...
157 views

### Let $p$ be a prime of the form $p=2^k+1$. Prove that $\mathbb{Z}_p$ has $2^{k-1}$ primitive roots.

Let $p$ be a prime of the form $p=2^k+1$. Prove that $\mathbb{Z}_p$ has $2^{k-1}$ primitive roots. Let $g_0$ be a primitive root. Which powers of $g_0$ are primitive roots? Prove! Since $p$ is a ...
49 views

770 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 ...
74 views

### Primitive roots and 'equivalent exponents'.

If M is a primitive root mod p and M = $\ N^T$ mod p , then the order of N mod p is also (p-1) is this true?
203 views

### My proof that there are primitive roots modulo $p^2$

Let $p$ be a prime number. I'd like to prove that there are primitive roots modulo $p^2$. Could someone check this argument? Note that if $r\in\mathbb Z$ is a primitive root modulo $p^2$, it must be ...
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
319 views

### How do I find a primitive element in $Z_7$?

I understand the definition of a primitive element. I also know that 3 is primitive element of $Z_7$. I was shown that 2 is not primitive element of $Z_7$ because $2^{3}$ = 8= 1. I do not understand ...
65 views

### About primitive roots of $p$ less than $\frac{p-1}2$.
If all the residues of $p$, from $2$ to $\dfrac{p-1}2$ can be expressed as $(2^A)(3^B)(5^C) \pmod p$ for some integers $A$, $B$, $C$ then is it true at least one of $2$ or $3$ or $5$ is a primitive ...