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
1
vote
1answer
148 views

Show that $−g$ is also a primitive root of $p$ if $p\equiv 1 \pmod{4}$, but that $ord_p(−g) = \frac{p−1}{2}$ if $p \equiv 3 \pmod{4}$. [duplicate]

Let $p$ be an odd prime and let $g$ be a primitive root $\pmod{p}$. Show that $−g$ is also a primitive root of $p$ if $p \equiv 1 \pmod{4}$, but that $ord_p(−g) = \frac{p−1}{2}$ if $p \equiv 3 \pmod{...
4
votes
1answer
177 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$...
0
votes
1answer
120 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 ...
1
vote
1answer
43 views

Find a polynomial in $\mathbb{Z}_{41}$

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 \...
3
votes
1answer
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$ ...
1
vote
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 ...
0
votes
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 ...
1
vote
0answers
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]$ ...
3
votes
1answer
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?
3
votes
0answers
45 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: $$...
1
vote
1answer
224 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$, ...
2
votes
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 ...
0
votes
1answer
28 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, ...
1
vote
0answers
38 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
36 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
36 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 ...
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 ...
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 ...
0
votes
1answer
71 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 $\...
1
vote
0answers
155 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} \...
2
votes
1answer
58 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 ...
3
votes
2answers
102 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 ...
0
votes
1answer
86 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
58 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
81 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
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 ...
2
votes
2answers
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 ...
1
vote
2answers
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, ...
0
votes
1answer
202 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
206 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 ...
5
votes
2answers
465 views

Primitive roots modulo n

How do I find a primitive root for a given $n$? For which $n$ does a primitive root exist (I would have guessed it's for all $n$ which are not divisible by 8)? Is there a systematic way, to constuct ...
2
votes
2answers
127 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} ...
1
vote
1answer
53 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
86 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
50 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
35 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
76 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
49 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
43 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}_{...