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.

410 questions
Filter by
Sorted by
Tagged with
1k views

Prove that $r$ is a primitive root modulo $p$ if and only if $r^{(p−1)/q}\not\equiv 1\pmod{p}$

Suppose $p$ is an odd prime. Prove that $r$, with $\gcd(r, p) = 1$, is a primitive root modulo $p$ if and only if $r^{(p−1)/q}\not\equiv 1\pmod{p}$ for all prime divisors $q$ of $p − 1$. The only ...
46 views

Is $g$ mod $p$ a generator for the multiplicative group mod $p^2$?

How would one go about proving/disproving whether $g$, a multiplicative generator mod $p$, is also a multiplicative generator mod $p^2$?
175 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 ...
74 views

Prove that if $r$ is a primitive root modulo $m$, and $(a, m) = (b, m) = 1$, then $r^a \equiv r^b \pmod{m}$ implies $a\equiv b \pmod{\varphi(m)}$

Prove that if $r$ is a primitive root modulo $m$, and $(a, m) = (b, m) = 1$, then $r^a \equiv r^b \pmod{m}$ implies $a \equiv b \pmod{φ(m)}$. Any hints will be appreciated. Thanks so much.
121 views

Is primitive root or order in number theory relate with order of element in cyclic group?

I just read abstract algebra and found notation of cyclic group (I don't read the whole yet ) the order in number theory state $a^{b}\equiv 1(mod N)$ and Cyclic group state $a^{n}=e$ or I not sure ...
99 views

Finding primitive root mod n?

in wikipedia, https://en.wikipedia.org/wiki/Primitive_root_modulo_n#Finding_primitive_roots, it says there is no formula to compute primitive root mod n. and in the footnote 8, it seems that there ...
2k 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 ...
354 views

$a$ is a primitive root modulo a prime $p$; $ab\equiv1\bmod p$; prove $b$ is a primitive root modulo $p$

Let $p$ be prime. Prove that if $a$ is a primitive root modulo $p$ and $ab\equiv1\bmod p$, then $b$ is a primitive root modulo $p$. I understand the definition of primitive roots. I am having trouble ...
346 views

Assuming that $r$ is a primitive root of the odd prime $p$ prove that $r^{(p-1)/2}\equiv -1 \pmod p$ holds

I know if $r$ is primitive root $r^{^{n}}\equiv a\pmod n$ from the set of residue $\{1,2,3....(n-1)\}$ but if change to $r^{(p-1)/2}\equiv -1 \pmod p$. My assumption: It's no longer be primitive ...
136 views

$h^{\frac{p-1}{2}} \equiv 1 \bmod p$ and $g^x \equiv h \bmod p$ for a primitive root $g$ $\iff$ $x$ is even

Let $g$ be a primitive root for the odd prime $p.$ Suppose $g^x \equiv h \pmod p$. Show that $x$ is even if $h^{\frac{p-1}{2}} \equiv 1\pmod p$ and $x$ is odd if $h^{\frac{p-1}{2}}\equiv -1\pmod p$.
404 views

112 views

Number of fields between $\mathbb{Q}$ and $\mathbb{Q}(\zeta_n)$

If $\zeta_n$ is the $n$-th primitive root of unity then $Gal(\mathbb{Q}(\zeta_n)/\mathbb{Q}) \simeq Z_n^*$ due to the following map $$\tau(\zeta_n)=\zeta^n$$ I was wondering if we could use this and ...
290 views

Solving $n^{th}$ power residue of a congruence

I'm given $x^2$ ≡ -1 mod 365 I know that 365 = $5*73$ so then my congruence becomes, $x^2$ ≡ -1 mod 5 and $x^2$ ≡ -1 mod 73 Since $(-1)^2$ ≡ 1 mod 5 and $(-1)^{36}$ ≡ 1 mod 73 implies that there ...
427 views

Find a primitive element in the splitting field of $x^4-8x^2+15$.

I'm trying to find a primitive element in the splitting field of $x^4-8x^2+15$. I don't know in general what should I do with this kind of questions. Should I solve the roots and get the Galois group?
129 views

primitive root modulo prime powers [duplicate]

Suppose that $g$ is a primitive root modulo $p$. Show that, modulo $p^h$ for $h\geq 2$, every primitive root has the form $g'=g+np$ for a certain integer $n$. The proof of the previous statement ...
47 views

Showing that the polynomial $f = x^4+x^3+1 \in Z_2[x]$ is primitive?

I have shown it is irreducible. I've tried considering $\alpha = \bar{x} \in \mathbb{Z}_2[x]$ s.t. $\alpha^4+\alpha^3+1 = 0$. From my understanding you use the fact that $\alpha^{16-1} = 1$ and hence ...
126 views

Congruence $16^{(x^ 2+x+1)} \equiv 4 \mod 11$

Given the congruence $16^{x^2+x+1}≡ 4 \mod 11$ I'm not necessarily sure how to approach this problem if someone can help me head in the right direction since 16 is not a primitive root of mod 11 I ...
602 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 ...
145 views

can composite groups have primitive roots (be cyclic)?

Imagine Z/nZ with n not prime (n=pq). Can the multiplicative group be cyclic? I read the paper over here: http://math.uga.edu/~pete/4400primitiveroots.pdf At one point he dismiss the case where the ...
42 views

Is $\mathbb{Q}(z,\dots,z^{n-1})$ the splitting field of some polynomial $\mathbb{Q}[x]$, where $z$ is a primitive root of unity?

Is $\mathbb{Q}(z,...z^{n-1})$ the splitting field of some polynomial in $\mathbb{Q}[x]$, where $z$ is a primitive root of unity? I know that if $n\ge 1$ and $k$ is a field, and $f(x)=x^n-1\in k[x]$, ...
48 views

let $q$ be a prime of the form $q=3r+1$ and assume that $p=4q+1$ is also a prime. Show that $3$ is a primitive root of $p$

How to even begin? The proof for if $p$ is an odd prime then $(\frac{2}{p})=(-1)^{\frac{p^{2}-1}{8}}$ seems useful but not sure how to adapt it
172 views