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.

Filter by
Sorted by
Tagged with
2
votes
2answers
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 ...
1
vote
1answer
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$?
2
votes
3answers
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 ...
2
votes
2answers
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.
1
vote
1answer
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 ...
1
vote
0answers
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 ...
4
votes
1answer
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 ...
2
votes
2answers
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 ...
2
votes
1answer
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 ...
1
vote
2answers
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$.
0
votes
1answer
404 views

Proving if $g$ is a primitive root $\pmod n$ and $n$ is prime, then $g^k$ $\pmod n$ is also a primitive root if and only if $\gcd(k, n-1) = 1$

Prove that when $n$ is prime, and $g$ is a primitive root $\pmod n$, $g^k$ $\pmod n$ is always a primitive root whenever $\gcd(k, n-1)$ $=$ $1$. Known Facts: It would be the case that if $\gcd(k, n-...
0
votes
1answer
96 views

Holomorphic function and primitives

I need to prove that $\int_\gamma f'(z)/f(z)dz=0$ for any closed curve. It is given that f is holomorphic and satisfies $|f(z)-1|\lt1$ in the region. And we can assume $f'(z)$ is continuous. I think ...
1
vote
1answer
287 views

Primitive element for each subfield of a cyclotomic extension

Given an odd prime number $p$, a natural number $r$, and a $p^r-th$ primitive root $\zeta=\zeta_p$, I have to find an explicit expression of a primitive element for each subfield of $\mathbb{Q}(\zeta)$...
2
votes
2answers
98 views

Is 2 always a primitive root of 3ˣ?

That is, is it always that $$2^{3^x}\equiv -1\pmod{3^{x+1}}\large?$$
10
votes
4answers
220 views

Any element of $\mathbf{Z}[\xi]$ is congruent to an integer modulo $(1-\xi)^2$ if multiplied by a suitable power of $\xi$

I'm currently reading Kummer's famous paper on Fermat's Last Theorem (if anyone wants the link, I'll post it, but the paper is in German). There's the following statement in there, which should be "...
2
votes
1answer
58 views

Show that a certain set of elements is a basis of the free module $\mathbf{Z}[\xi]$

Let $\xi$ be a $p$-th root of unity for $p$ a prime. It is well-known that $\mathbf{Z}[\xi]$ is a free $\mathbb Z$-module. Now I'd like to show that $1, (1-\xi)^2, ..., (1-\xi)^{p-1}$ is a basis ...
1
vote
0answers
53 views

evaluate the integrals using Primitives

Evaluate the integrals $\int_\gamma z^ndz$ for all integers n. Here $\gamma$ is any circle not containing the origin. The answer to this problem is extremely difficult. $$ \int \limits_{\gamma }\...
0
votes
2answers
264 views

About Primitive roots

Good day! I'm currently studying on the primitive roots mod n. Eventually, I fully understand the concept of calculating the primitive roots of a number by practice, but I encounter the following ...
0
votes
1answer
92 views

Help with primitive root modulo $p^r$ [duplicate]

Let $p\ge3$ be a prime number, $r$ be a natural number and $x$ be a primitive root modulo $p^r$. Show that $x$ is a primitive root modulo $p$.
2
votes
1answer
109 views

A field of Radical Sums

I am dealing with a computation that yields numbers that are sums of radicals of the following form: $N=\sum_{i=0}^{m}{a_i\sqrt{b_i}}$ Where $a_i,b_i \in \mathbb{Q}$ (rationals). The context is ...
13
votes
1answer
226 views

Are there infinitely many primes $n$ such that $\mathbb{Z}_n^*$ is generated by $\{ -1,2 \}$?

Let $n$ a prime, and let $\mathbb{Z}_n$ denote the integers modulo $n$. Let $\mathbb{Z}^*_n$ denote the multiplicative group of $\mathbb{Z}_n$ Are there infinitely many $n$ such that $\mathbb{Z}^*_n$ ...
-3
votes
1answer
76 views

Solve $19^n$ = $801777482$ $\pmod {4535332489}$ given $4535332489$ is prime. [closed]

Solve $19^n$ = $801777482$ $\pmod {4535332489}$ given $4535332489$ is prime and without calculating any factors of $4535332488$. Is solving this possible with the current information? If so, what is $...
-1
votes
2answers
101 views

Prove that Carmichael number has no primitive roots

Prove that if $n$ is a Carmichael number, then $n$ has no primitive roots. This seems tricky to prove, and the only logical explanation for this is that it contradicts the basis of the Lucas Primality ...
1
vote
1answer
69 views

Primitive 18-th root of unity problem involving congruences.

I have some doubts about this following problem, if you can please try to answer the congruence step: Let $ \omega$ be a primitive 18-th root of unity. Find $ n \in \mathbb Z$ such that: $ \omega^n =...
9
votes
0answers
298 views

Number of primitive roots mod $p$ that are not primitive roots mod $p^2$

Consider the primitive roots of a prime $p$ in the range $1...p$ which are not primitive roots mod $p^2$. Let $n(p)$ be this number. While looking for an answer to this question, it seems that the ...
6
votes
3answers
213 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$...
1
vote
3answers
82 views

Let $f = 2x^4 + 2(a - 1)x^3 + (a^2 + 3)x^2 + bx + c.$ ,Find out $a, b, c ∈ R$ and its roots knowing that all roots are real.

Let $f = 2x^4 + 2(a - 1)x^3 + (a^2 + 3)x^2 + bx + c.$ Find out $a, b, c ∈ R$ and its roots knowing that all roots are real. The first thing that came into my mind was to use vieta's ...
6
votes
2answers
109 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 ...
2
votes
0answers
39 views

Generators in arithmetic progression.

Suppose $p+1$ is a prime fix $a,b\in\Bbb Z_p^\times$ how many generators of $\Bbb Z_p^\times$ lie on the line $ax+b$ considered over $\Bbb Z$ and what is the size of a typical minimal generator with ...
1
vote
1answer
60 views

Prove that if $g$ and $h$ are primitive roots modulo $m$ so $\text{ind}_g (h)$ is the inverse of $\text{ind}_h (g)$ modulo $\phi(m)$

Prove that if $g$ and $h$ are primitive roots modulo $m$ so $\text{ind}_g (h)$ is the inverse of $\text{ind}_h (g)$ modulo $\phi(m)$ My attempt: I need to prove that $\text{ind}_h (g)\cdot \text{ind}...
5
votes
2answers
115 views

Find the number of solutions of $x^k\equiv 45\pmod{97}$

Let $5$ be a primitive root of $97$ and $\text{ind}_5 (45)=45$ find the number of solutions of $x^k\equiv 45\pmod{97}$ where $k=7,8,9$ My attempt: $$5^{45}\equiv 45 \pmod{97}$$ For $k=7:$ $$x^7\...
2
votes
1answer
603 views

Write the index table for the primitive root $3$ of $25$

Write the index table for the primitive root $3$ of $25$ My attempt: $$ \begin{array}{c|lcr} k & 0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&...
0
votes
2answers
279 views

Prove that g is a primitive root modulo m.

We have natural number $m \ge 2$ which is relatively prime with integer number $g$. Let's assume that for every prime divider $q|\varphi(m) $ we have $$ g^{ \frac{\varphi(m)}{q} } \not\equiv 1 (mod \...
2
votes
1answer
76 views

what does $\alpha$ signify in finite fields modular arithmetic

Say $\frac{\mathbb{Z}_{2}\left [ x \right ]}{x^{2}+x+1}=\left \{0,1,\alpha ,1+\alpha \right \}$ is a finite field with its elements listed. I am finding it difficult to understand what it means ...
0
votes
1answer
68 views

Finding primitive root of unity using Newton iteration

following problem I am supposed to solve on paper. Use Newton-Iteration to find a primitive 16th root of unity over $\mathbb{Z}/17^{16}\mathbb{Z}$ with $\omega = 6 \pmod{17}$ I have some kind of ...
0
votes
1answer
21 views

Generators of $Gal(\mathbb{Q}(\zeta_n)/\mathbb{Q})$ - what is $\tau(\zeta_n)$?

I am trying to understand the structure of $Gal(\mathbb{Q}(\zeta_n)/\mathbb{Q})\simeq Z_n^*$ for $n \in \mathbb{Z}$ - it would be great if someone could me understand the generators in this group so ...
2
votes
2answers
85 views

Irreducibility of $X^5-7$ over $\mathbb{Q}(\sqrt[7]{2})[X]$ and degree of spitting field

I have worked through these two questions but am unsure if I got the right idea, please may you help me? Prove that $X^5-7$ is irreducible over $\mathbb{Q}(\sqrt[7]{2})[X]$ Can we say that $f(X)=...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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?
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
3answers
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 ...
5
votes
3answers
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 ...
0
votes
2answers
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 ...
1
vote
0answers
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]$, ...
1
vote
1answer
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
2
votes
2answers
172 views

If primitive root modulo $mn$, then primitive root modulo $m$ and $n$

Let $a$ be a primitive root modulo $mn$. Show that $a$ is also primitive root modulo $m$ and $n$. Showing $(a,mn)=1\Longrightarrow (a,m)=(a,n)=1$ is not a problem. The problem is showing $a^{\varphi (...
1
vote
1answer
237 views

Show that 3 is a primitive root modulo 14. Then, write the other primitive roots modulo 14 in terms of powers of 3. How many are there? [closed]

Show that $3$ is a primitive root mod $14$. Then, write the other primitive roots mod $14$ in terms of powers of $3$. How many are there? A bit lost with this question. Poked around online and found ...
0
votes
0answers
113 views

Finding a primitive root modulo $p$ [duplicate]

Let's attempt to find a primitive root modulo, say, $p=127$. Since $p$ is prime a primitive root exists (more specifically there are $\varphi (\varphi (127))=36$ primitive roots modulo $127$). $\...