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

385 questions
30 views

37 views

### How does Fermat's Little Theorem help find primitive roots of unity?

I am asked to find the primitive roots of unity mod 23, and recommended to use Fermat's Little Theorem to help simplify calculation. I know that, once I've found one, I can find all others by finding ...
143 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 ...
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 ...
93 views

### Given 2 is a primitive root mod 19, find all solutions to x^12 ≡ 7 (mod 19) (a) x^12 ≡ 6 (mod 19)

I'm stuck on (another) problem under Number Theory. There are quite a few gaps on what was covered in my class so I'm having quite a bit of trouble. Could you please help me solve the following ...
27 views

### Any finite field of $q$ elements has exactly $\Phi(q-1)$ primitive roots

Is the following prove of the above statement correct? $\bullet\$Any finite field of $q$ elements is isomorphic to $\mathbb{F}_q$ and we know that $\mathbb{F}_q^*$ is a cyclic group of $q-1$ ...
26 views

### Use primitive root to prove if $a^{\phi(m)/2}\equiv 1\pmod m$ then $a$ is a quadratic residue modulo $m$.

This is trivial in arguments of quadratic residues, but I couldn't solve it using primitive root. The problem seeks to use primitive root to be proved. Problem: Let $m>2$ be an integer having a ...
13 views

### If $(a,m)=(b,m)=1$ and if $(\exp_m(a),\exp_m(b))=1$, prove that $\exp_m(ab)=\exp_m(a)\exp_m(b).$

If $(a,m)=(b,m)=1$ and if $(\exp_m(a),\exp_m(b))=1$, prove that $$\exp_m(ab)=\exp_m(a)\exp_m(b).$$ The notation $\exp_m(a)$ is denote the smallest positive integer $n$ such that $a^n\equiv 1\pmod m$. ...
38 views

### Certain conditions for primitive roots of $n$.

Let $a$ be a primitive root for modulo $n$. Then, $a^{\frac{\phi(n)}{2}}\equiv-1\pmod{n}$. I have a question for its converse. In general, its converse is false. Is it possible to make(it means '...
48 views

### Number of solutions of $x^e \equiv c \mod p$

We have to find the number of solutions to the equation:- $$x^e \equiv c \mod p$$ where $c \not\equiv 0\mod p$. For $c=1$, we can prove that the above has $\gcd(e,p-1)=d$ solutions in the following ...
61 views

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$...
118 views

### The set of the primitive roots modulo $p$, with $p$ a fermat prime

"Let $p$ be a prime of the form $2^{2^{n}}+1$, with $n \in \mathbb{N}$ (This means $p$ is a Fermat prime) Using Euler's Criterion, prove that the set of primitive roots mod $p$ is equal to the set ...
Find a $7^\text{th}$ degree polynomial $p(x)$ in $\mathbb{Z}_{41}[x]$, so that $$p(14^i) = i\pmod{41}\ \forall i = 0,1,\ldots,7.$$ Hint: $3$ is the $8^\text{th}$ primitive root of unity and $3 \... 1answer 81 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$... 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 ... 1answer 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 ... 0answers 279 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]$... 1answer 46 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? 0answers 43 views ### Some questions concerning the generators of cyclic groups Let$g(p)$be the least positive primitive root of the prime$p$, the primitive roots being the generators of the cyclic group$\mathbb{Z}_{p-1}$. These are the values for the first prime numbers:$$... 1answer 162 views ### How to find all primitive roots modulo 121? This question is different from this question as I want to find all primitive roots, and not just some. Is my following approach correct? We have$121=11^2$, with$11$an odd prime, and$2 \ge 1$, ... 2answers 4k views ### Primitive elements of GF(8) I'm trying to find the primitive elements of$GF(8),$the minimal polynomials of all elements of$GF(8)$and their roots, and calculate the powers of$\alpha^i$for$x^3 + x + 1.$If I did my math ... 1answer 26 views ### Solutions of$x^2 \equiv \pm 2 \ (\text{mod} \ p)$and primitive root modulo$p.$If$p = 8n+1$is a prime and$r$is a primitive root modulo$p,$then the solutions of$x^2 \equiv \pm 2 \ (\text{mod} \ p)$are given by$x \equiv \pm(r^{7n} \pm r^n) \ (\text{mod} \ p).$Again, ... 0answers 37 views ### n is primitive root for odd prime p. If -n is primitive root iff p = 4k+1 for some integer k if$n$is primitive root for odd prime$p$, then$-n$is also a primitive root for$p\iff p = 1 \text{ mod } 4$I am having trouble solving this question, can someone show to me how to solve it? ... 1answer 18 views ###$\zeta$is a p-th primitive untary root iff$-\zeta$if a 2p-th primitive unitary root, with$p$an odd prime$\Rightarrow(-\zeta)^{2p}=(-\zeta^p)^{2}=1$and if$i \in[{1,2p-1}]$there is$k \in[0,p-1]$such that$i=2k+1$if is odd and$2k$if is even so$(-\zeta)^{i}=(-\zeta)^{2k}=(\zeta^k)^{2}\neq 1$... 1answer 35 views ### How to Simplify$\mathbb{Q}(\zeta_4,\zeta_8 , \zeta_{12},\zeta_6 )$If$mdc(m,n)=1$then$\mathbb{Q}(\zeta_m,\zeta_n )=\mathbb{Q}(\zeta_{mn} )$,but what if the degree of the roots are divisors and multiples of each other? I guess that$\mathbb{Q}(\zeta_4,\zeta_6, \...
Let $\mathbb{K}\subseteq \mathbb{L}$ be a Galois extension with order $n$. If $p$ is a prime divisor of $n$, show that exists a subfield $\mathbb{M}$ of $\mathbb{L}$ such that \$[\mathbb{L},\mathbb{M}]...