# 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
148 views

93 views

### What are the intermediate fields of $\mathbb{Q}(\sqrt[4]{2},i)/\mathbb{Q}$ of order $4$ over $\mathbb{Q}$?

Let $K = \mathbb{Q}(\sqrt[4]{2},i)$. Am I correct to say that $K$ has a 8-th primitive root: $\zeta_8 = \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{2}}i$? The 8-th cyclotomic polynomial is $\Omega_8 = X^4+1$ ...
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 ...
63 views

### Show that if $p|(a^{2^n}+1)$, then $p = 2$ or $p\equiv 1 \pmod{2^{n+1}}$

As the title indicates, I do not know how to proceed. There is a hint to prove it. The hint says that: show that if $p>2$ then a is of order $2^{n+1} \pmod p$. But I do not see any connection ...
294 views

### Efficient way to find primitive root without prime factorization

I was wondering if there is a more efficient brute-forcing approach to find any primitive root of number $p$ without prime factorization. My approach is as follows: Get a random residue class $[x]$ ...
51 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?
45 views

58 views

52 views

### Does a number have a primitive root if and only if φ(n)=λ(n)?

From the Wikipedia article on root primitives: In particular, for a to be a primitive root modulo n, φ(n) has to be the smallest power of a which is congruent to 1 modulo n. Am I correct if I say ...
1k views

### How to find primitive roots modulo products of primes and other composites?

I know how to find the primitive roots modulo $23$ and and the primitive roots modulo $23^2=529$, in which we are finding the primitive roots of prime powers. My questions are what if we want to find ...
246 views

### Primitive roots generated from a primitive root

Let $p$ be a prime number, and let $a$ be a primitive root $\mod p$. Is it true that $a^m$ is a primitive root if and only if $\gcd(m,p-1)=1$? One direction is correct: if $a^m$ is a primitive root, ...
202 views