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.

1
vote
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? ...
0
votes
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$ ...
0
votes
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, \...
0
votes
0answers
25 views

Subfields of Galois Extensions and association with Galois Groups

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}]...
0
votes
1answer
31 views

Finding primitive roots modulo $x$

I'm just starting with number theory and by now I know how to test whether a given number $\alpha$ is a primitive root mod $p$ or not. But I'm not sure yet how it works if $\alpha$ isn't given. I saw ...
1
vote
1answer
37 views

Proof of $(\mathbb{Z}/p^k \mathbb{Z})^\times\cong\mathbb{Z}/\phi(p^k) \mathbb{Z}$

While learning some material about primitive roots, I read some algebraic approach of the proof of the existence of primitive roots. I read this wikipedia article, however, I got a little bit ...
1
vote
0answers
144 views

Primitive nth roots of unity related to the complex nth roots of 1.

I just cannot seem to wrap my head around this problem and would really appreciate some guidance. So I know that a primitive $n^{th}$ root of unity is a complex number $z$ such that $z^n = 1$ but $z^m ...
1
vote
1answer
93 views

How to prove that $g$ or $g+p$ is a primitive root modulo $p^a$ for a primitive root $g$ modulo $p$?

I wish to prove the following: If $p$ is an odd prime and $g$ is a primitive root modulo $p$, then either $g$ or $g+p$ is a primitive root modulo every power of $p$. The only reference I can find ...
0
votes
2answers
33 views

Why is this function equal to zero?

Say that I have a primitive root of unity $\omega$. Given $p \neq 0$, and $1-\omega^p \neq 0$, the following function is supposed to equate to zero, but I could not understand it. \begin{equation} \...
3
votes
2answers
99 views

How many primitive roots does $334$ have?

Clearly $334 = 2 \times 167$. So it is of the form $2p^k$ which implies primitive roots $\bmod 334$ exits but the question is how many? The formula $\phi(\phi(n))$ requires $n$ to be prime. If we use ...
0
votes
0answers
28 views

Solving an equation with primitive root of unity

PROBLEM Let be $w$ a primitive root of $G_{77}$ and the next sequence: $z_0 = w$ , $z_{n+1} = z_n^3$ Find all $n \in \mathbb{N}$ that makes the following true: $w^{74} + z_n = w^{50}$ Idea I've ...
2
votes
1answer
57 views

sequences of consecutive primitive roots

To mod $p=23,$ there are three sequences of two or more consecutive primitive roots. Namely $10,11$ and $14,15$ and $19,20,21.$ My question is whether there is a bound on the length of such sequences ...
0
votes
1answer
84 views

Let $p$ be a prime. Compute $1^k + 2^k + \ldots + (p-1)^k \pmod{p}$. [duplicate]

An exercise at the end of a chapter on primitive roots asked me to compute $1^k + 2^k + \ldots + (p-1)^k \pmod{p}$ for any positive integer $k$ and any prime $p$. Clearly, if $k$ is odd, the ...
2
votes
2answers
56 views

How to evaluate $ \prod_{1\le i <j\le\frac{p-1}{2}}j^2-i^2 \pmod p$

While doing my research on elementary number theory, I came across the following problem which I cannot overcome: Let $p$ be an odd prime, $g$ be any primitive of $p$. Define $$f(p)=\prod_{1\le i <...
2
votes
4answers
57 views

number of square roots of unity modulo a prime power

Let $p\geq 3$ be a prime number and let $k\geq 1$ be some integer. Is it always true that if $x^2\equiv 1\pmod{p^k}$ then $x\equiv\pm1\pmod{p^k}$ ? For $k=1$ it is true since $x^2-1\in\mathbb{F}_p[...
1
vote
1answer
79 views

$10$ is a primitive root modulo $p=4q+1$

Let $q$ be a prime number such that $p=4q+1$ is also a prime number and $q\equiv 2\ (\text{mod}\ 5)$. Prove that $10$ is a primitive root modulo $p$. I know that it is sufficient to prove that $\...
-1
votes
1answer
50 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 ...
0
votes
1answer
173 views

Root of unity belongs to Z/qZ. How?

EDIT: Really sorry for not posting this initially.. maybe it's easier to understand now. Source, page 6. I've stubled upon a statement similar to this: "Let $m,q$ be two integers such that $\mathbb{...
2
votes
0answers
192 views

Primitive $p$-th root of unity with characteristic $p$

I struggle on this since two days, and still found no answer. My course states the following: If the characteristic of $K \neq p$, then they are exactly $p-1$ different $p$-th roots of unity in the ...
0
votes
1answer
70 views

Exponential modular arithmetic for Diffie-Hellman

I've been playing around with some finite fields to test how rapid brute-force is when solving discrete logarithm problems occurring in DH methods. Working in $\mathbb{F}_{101}$, pick a private key $\...
2
votes
2answers
123 views

Sum of powers mod p

I've this problem that I did halve of the proof but I can't do the rest of it. Let $p$ be an odd prime. We define $S_n$ as $S_n = 1^n +2^n + ... +(p-1)^n$ Prove that $S_n \equiv \begin{cases} ...
2
votes
3answers
84 views

Let $w$ be a primitive root of a unit of order 3, prove that $(1-w+w^2)(1+w-w^2)=4$

The title is the statement of the problem. I did the following: $(1-w+w^2)(1+w-w^2)=$ $1+w-w^2-w-w^2+w^3+w^2+w^3-w^4=$ $1-w^2+w^3+w^3-w^4=$ $1-w^2+1+1-w^4=4$, * then,by definition of primitive ...
3
votes
1answer
88 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$ ...
1
vote
1answer
48 views

degree of extension of Q with primitive roots of unity

Question Show that $[\mathbb{Q}(\zeta+\zeta^{-1}):\mathbb{Q}]=\phi(n)/2$, where $\zeta$ is a primitive $n$-th root of unity. Attempt Let $\sigma: z\mapsto \bar{z}$,$\sigma(\zeta)=\zeta^{-1}$.Since $...
2
votes
1answer
83 views

Show that if $x$ is a primitive root modulo $p^r$, then $x$ is a primitive root modulo $p$ [duplicate]

I'm trying to solve the following problem: Let $p\geq 3$ be a prime number, let $r \in \Bbb N$, and let $x$ be a primitive root modulo $p^r$. Show that $x$ is a primitive root modulo $p$. I'm pretty ...
0
votes
1answer
47 views

Why does $ord_p(a^i) =ord_p(a) = d $ when $(i,d)=1$?

I'm having a bit of a hard time wrapping my head around why this theorem is true. Suppose p is prime and $ord_p(a) = d$. For each natural number $i$ with $(i,d) = 1 ,ord_p(a^i) =d$ My thought ...
1
vote
2answers
65 views

Finding an element of order $67$ modulo $2011$. [closed]

Suppose that we are given $p= 2011$, where $3$ is a primitive root (this is a given). Here is the question: Find an element of order $67$. I know that $e_{p}(a) =$ (the smallest exponent $e \geq 1$...
0
votes
1answer
33 views

Primitive Roots and their orders

For this question, suppose $p = 659$, where $p$ is prime. I have found that, through computing $\phi(p-1)$, where $\phi ()$ is the Euler Tiotent Function. Here, there are a total of 276 primitive ...
0
votes
1answer
35 views

$|\{1≤x≤p^2:p^2│x^{p-1}-1\}|=p-1$ [duplicate]

Let $p$ be a prime number. Let $S_p=\{1≤x≤p^2:p^2│x^{p-1}-1\}$. Prove that $|S_p|=p-1$. I managed to prove that $|S_p|\geq p-1$. I took $g$, a primitive root modulo $p^2$, and then proved that $\...
0
votes
3answers
75 views

Solve $a^6 \equiv 12 \pmod{13}$

So I'm going over my notes for a test, and I can't read my horrible slop that I call handwriting. The question was $a^6 \equiv 12 \pmod{13}$ I know that there is a primitive root $r$ and so that $a =...
0
votes
0answers
48 views

Existence of solutions to DLP and Primitive roots mod $p$

Discrete log problem - finding $x \ge 0$ for prime $p$ , generator $g>0$ and $h>0$ such that: $$g^x \cong h \pmod{p}$$ Define $G$ as the group generated by all values of $g^x \pmod{p}$. Eg $G=$...
0
votes
0answers
42 views

Algorithm for finding modulo given primitive root.

It is conjectured by Artin that for every number $g$ which is not $-1$ and not a square number, there is an infinite number of $m$ such that $g$ is a primitive root modulo $m$. How to find $m$ ...
0
votes
1answer
42 views

Primitive roots mod $p^k$

I'm having trouble understanding why this is true. Say m is the order of $g$ mod $2p^k$, with $\gcd(g, 2p^k)=1$, i.e. $g^m \equiv 1$ mod $2p^k$. How do I know that $g^m \equiv 1$ mod $p^k$?
0
votes
1answer
27 views

$m$-th primitive root of unity over $\mathbb{Z}_{2^k}$ for some integer $k$ [closed]

Can we find the $m$-th primitive root of unity over $\mathbb{Z}_{2^k}$ when $m$ is also a power of $2$?
5
votes
2answers
66 views

Show $2+\alpha$ is a primitive root of $\mathbb{F}_{25}$.

Suppose $\alpha \in \mathbb{F}_{25}$ is an element with $\alpha^2 = 2$, I need to prove that $2+\alpha \in \mathbb{F}_{25}$ is a primitive root (that is: a generator of the cyclic group $\mathbb{F}_{...
6
votes
3answers
92 views

Reluctant roots: $n$ is a primitive root of $p$ but not of $p^2$

I was looking at the primitive roots $n \bmod p$ and $p^2$ to see how often we get primitive roots of a prime that are not primitive roots of the square of that prime. I'll call this a reluctant root ...
1
vote
1answer
73 views

Show that the number of solutions to $x^n\equiv 1 \pmod p$ is $\gcd(n, p-1)$, where $p$ is a prime

Show that the number of solutions to $x^n\equiv 1 \pmod p$ is $\gcd(n, p-1)$. I know the argument should specifically use primitive roots (the desired one based off the stuff I've learned), but not ...
2
votes
1answer
91 views

Let $p$ be a prime number. Show that the number of solutions to $x^k \equiv 1 \pmod p$ is $gcd(k, p-1)$

I'm really not convinced by my own proof of this. Would appreciate a critique/reformulation using the ideas I already introduced. First note that $a^k \equiv 1 \mod p \implies k\ |\ p -1$ by Fermat's ...
2
votes
4answers
186 views

Number theory question involving Wilson's theorem. How to solve?? [duplicate]

Given p is a prime number greater than 2, and $ 1 + \frac{1}{2} + \frac{1}{3} + ... \frac{1}{p-1} = \frac{N}{p-1}$ how do I show, $ p | N $ ??? The previous part of this question had me factor $ ...
3
votes
2answers
88 views

Suppose $p$ is $3\bmod 4$. Show $a$ and $-a$ cannot both be primitive roots $\bmod p$.

Suppose $p$ is $3\bmod 4$. Show $a$ and $-a$ cannot both be primitive roots $\bmod p$. I think the idea behind my proof is right but not sure it's written out that clearly, would appreciate another ...
1
vote
0answers
337 views

Let $p$ be an odd prime. Suppose $a$ and $b$ are both primitive roots mod $p$. Show that $ab$ is not a primitive root mod $p$

Let $p$ be an odd prime. Suppose $a$ and $b$ are both primitive roots mod $p$. Show that $ab$ is not a primitive root mod $p$. Would appreciate some proof-checking here. First, we show that a ...
1
vote
1answer
36 views

Primitive Roots and Order

Determine ord$_{17}2^{12}$. Below is what I think the answer is. Any comments and suggestions on how to approach the problem would be great! So does this mean that: Since, $ 2^{12} \equiv (2^6)^...
5
votes
5answers
160 views

How to solve $x^3 \equiv 1 \pmod{37}$

We are asked to solve $x^3 \equiv 1 \pmod{37}$. I know that the answer is $10$ since $27\cdot37 = 999$ and $10^3 = 1000$ but how do I show this rigorously? If it helps, we are given the primitive ...
0
votes
1answer
39 views

proof if $P(\alpha$)=0 and $\alpha^i\neq 1$ then $P$ is irreducible

In this wikipedia article state the following :"a primitive polynomial is the minimal polynomial of a primitive element of the finite extension field . In other words, a polynomial a primitive ...
1
vote
1answer
47 views

Why the result is not $0$?

Applying some properties, this should be: $(\sqrt[n]{a} * \sqrt[k]{a} ) - (a^{\frac{n+k}{nk}})= 0$ But according to symbolab, not. I guess it's a symbolab error. But I would like to make sure.
1
vote
0answers
80 views

When does a prime divide the sum of its primitive roots?

Here : Prime numbers primitive roots and $\Phi$? the ratio between the primes dividing the sum of its primitive roots and the primes upto a given limit is asked. Is there a nice criterion ...
1
vote
2answers
139 views

Determine if a number is a primitive root

Let $p$ be an odd prime, let $g$ be a primitive root of $p$. Prove $-g$ is a primitive root of $p$ if and only if $$p\equiv1\pmod{4}$$ Hint: express $-g$ as $g^{k}$, then use property 6 ... verify $$...
1
vote
2answers
378 views

Primitive Roots mod a prime number

I haven't fully wrapped my head around primitive roots yet and I have a question with them: Let $p$ be an odd prime and $g$, $h$ be two primitive roots modulo $p$. Show that $gh$ is not a primitive ...
1
vote
0answers
44 views

How to calculate the cardinality of following set

If $$A = \bigg\{\sum_{i=0}^4a_i x^{i}+b_i x^{i}y \ \big| \bigg(\sum_{i=0}^4a_iw^i\bigg)\bigg(\sum_{i=0}^4a_iw^{4i}\bigg) = 0: a_i, b_i \in \mathbb{F}_{2^k}\bigg\}$$ where $\mathbb{F}_{2^k}$ is a field ...
0
votes
1answer
35 views

Find a primitive root of (a) $U(\mathbb{Z}/121\mathbb{Z})$, and (b) $U(\mathbb{Z}/18\mathbb{Z})$

Find a primitive root of (a) $U(\mathbb{Z}/121\mathbb{Z})$ and (b) $U(\mathbb{Z}/18\mathbb{Z})$. Both of them are cyclic groups so primitive roots exist for both of them, but I don't know their ...