Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
1answer
24 views

Finding all solutions of 'Discrete Root'

Ques: $x^k \equiv a \pmod n$, where n is prime. What are the possible values of x? I know how to find a discrete root using both primitive root and discrete logarithm concepts. But I am wondering ...
2
votes
1answer
29 views

Let $w \in G_{15}$ be a primitive root. Find every $n \in \mathbb{N}$ such that $\sum_{i=2}^{n-1} w^{3i} = 0$

We can first rewrite the series in a useful form, $$\sum_{i=2}^{n-1} w^{3i} = \bigg( \sum_{i=0}^{n-1} w^{3i} \bigg) - w^3 - 1 $$ But since $w$ is primitive, we can apply the geometric series formula,...
0
votes
0answers
21 views

Isn't primitive root co-prime with corresponding modulo value?

Suppose, g is a primitive root modulo n. Therefore, $g^{\phi(n)} \equiv 1 \pmod n$ then g is always co-prime to n? Isn't it?
0
votes
1answer
16 views

Why is it sufficient to only check ${s/p_i}$ powers in finding primitive root?

In an answer to Finding a primitive root of a prime number, Vadim only checks $\,a^{\large s/p_i}\bmod p\,$ to check a primitive root. It works but why it is sufficient just to check only the powers ${...
1
vote
2answers
70 views

How to solve $7^x -5x^3 \equiv 0 \quad \pmod{11}?$

I have to study the solvability of the equation $$ 7^x -5x^3 \equiv 0 \quad \pmod{33} $$ and determine its integer solutions $ x $ with $ 0 \le x \le 110 $. I started dividing this equation into two ...
0
votes
0answers
34 views

Two definitions of a primitive root.

I have this definition in the book: "If gcd(a,n) = 1 and a is of order $\phi(n)$ modulo n, then a is a primitive root of the integer n. " And I have this definition given by my professor: "If $\...
0
votes
1answer
32 views

Prove reciprocal polynomial is not primitive(field).

Let $f$ be a polynomial with a non-zero constant term and define its reciprocal polynomial $f^*=x^nf(\frac{1}{x})$. (Here $\deg {f}=n$. I see several other names like "reverse/inverse polynomial", and ...
1
vote
1answer
26 views

proving that an element g is primitive

How do I go about proving that an element g is primitive? If I let p be a prime. Is it then the same as proving that every non-zero element in $Z_p$ can be written as a power of g?
0
votes
0answers
20 views

Sign of these complex embeddings

Let $\alpha$ be a root of $f = x^4 - 7$, hence $\alpha$ is a fourth root of $7$. Consider the number field $F = \mathbb{Q}(\sqrt[4]{7})$, which is of degree $4$. Since it is of degree $4$, there ...
1
vote
0answers
24 views

upper bound on, or fast algorithm to find, an order $2^n$ element in the multiplicative group modulo prime $q(2^n)+1$

I have a program which (in its current implementation) requires, for a given $N=2^n$, some $\omega$ in some field such that $\omega^N=1$ and $\omega^i\ne1$ for each $0<i<N$. Complex roots of ...
0
votes
0answers
31 views

In general, do primes of the form $a×2^{n}+1$always have primitive $2^n $th roots of unity (modulo that prime)?

EDIT: Title had an extra +1 in the 2's exponent For context, in competitive programming, problems which require a number theoretic transform usually ask for the answer modulo $998244353=7\times17\...
1
vote
5answers
72 views

For which primes p will there be a solution to x^3 + 1 ≡ (mod p) other than x ≡ - 1 (mod p)

I'm trying to learn more about modular arithmetic by practicing some problems, but I'm having some difficulty with this one. For which primes p will there be a solution to x^3 + 1 ≡ (mod p) other ...
0
votes
2answers
32 views

Given that $5$ is a primitive root of $73$, find all solutions to $x^3 - 1 ≡ 0$ (mod $73$).

I'm working through some problems with primitive roots and needed some help on this problem, specifically how do we use the fact that $5$ is a primitive root to solve this? Given: $5$ is a primitive ...
1
vote
1answer
43 views

Prove that number is a primitive root for all $k$ in range

Let $a$ be a primitive root for $p > 2$ where $p$ is prime. Show that $a^p+kp$ for $k = 1,\dots,p-1$ are $p-1$ distinct primitive roots modulo $p^2$. What I have done: First of all it is easy to ...
1
vote
0answers
25 views

Primitive roots in arithmetic progression

Let $a$ be a primitive root modulo odd prime. Show that in an arithmetic progression $a+kp$, where $k = 0,1,\dots,p-1$ there is exactly one number that is NOT a primitive root modulo $p^2$. It is ...
1
vote
0answers
34 views

What is the best upper bound for “how often” a number n is a primitive root modulo a prime p?

Let $n$ be a non-square positive number. The Artin Conjecture states that there are infinitely primes $p$ for which $n$ is a primitive root. Question: Given a number $n$, what is the best upper bound ...
0
votes
1answer
21 views

Why are the Galois groups that correspond to extensions which adjoin primitive roots of unity given by the group of units mod n

Considering all the following in the context of Galois theory. I believe, given say the primitive $9^{th}$ root of unity, that this will have as its minimum polynomial , the cyclotomic polynomial $\...
0
votes
1answer
40 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 ...
6
votes
1answer
154 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 ...
5
votes
3answers
478 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 ...
-2
votes
2answers
101 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 ...
0
votes
0answers
29 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$ ...
1
vote
1answer
34 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 ...
0
votes
1answer
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$. ...
1
vote
0answers
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 '...
1
vote
1answer
53 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 ...
1
vote
0answers
65 views

Is this a valid proof of Euler's product formula for the totient function?

I will attempt the proof using induction. But first, a lemma: Lemma 1: If $ n = p^{\alpha} $, where $ p $ is prime and $ \alpha\in\mathbb{N} $, then $ \phi(n) = n(1-\frac{1}{p}) $. $ \underline{...
1
vote
0answers
36 views

show this a primitive root question [closed]

if $n$ be positive integers,and such (1):$$\prod_{1\le i\le n,(i,n)=1}i\equiv -1\pmod n$$ (2):there exsit $a,$ such $a$ is a primitive root modulo $n$. show that $(1)\Longleftrightarrow (2)$ ...
2
votes
2answers
54 views

Prove that a primitive $q$-th root of unity is in the algebraic closure of $\Bbb F_p$

Let $p$ and $q$ be odd primes. Let $\Omega$ be the algebraic closure of $\Bbb F_p$. Let $\omega$ be a primitive $q$-th root of unity. Show that $\omega \in \Omega$. How do I show that? Please help me ...
0
votes
2answers
32 views

A proof of theorem about primitive roots [closed]

I have a such equation: $$ {x}^{n}-1=0 $$ I have n complex roots. For example:$${x}^{7}-1=0$$ $${x}_{1}=1; {x}_{2} = {(-1)}^{\frac{1}{7}}; {x}_{3}=-{(-1)}^{\frac{2}{7}}; ...;{x}_{7}={(-1)}^{\frac{6}{7}...
2
votes
2answers
76 views

If $a$ is of order $3$ mod a prime $p$, then …

The question says: Prove that if $a$ is of order $3$ modulo a prime $p$, then $1+a+a^2\equiv 0 \pmod p$. Moreover, $a+1$ is of order $6$. For the First Part: The typical idea is to start with $a^...
0
votes
1answer
48 views

$\zeta_n^k$ is primitive if and only if $(k,n) = 1$ [duplicate]

Show that for $k \in \mathbb{Z}$: Is $\zeta_n$ a primitive $n$-th root of unity, then $\zeta_n^k$ is primitive if and only if $(k,n) = 1$. I only need the backwards direction: $\zeta_n^k$ is ...
0
votes
1answer
38 views

$(e^{2\pi i}){}^n \neq e^{2\pi i n}$ where $n\in\mathbb{N}$?

When I type these equations into a calculator I get $({e^{2\pi i}}){}^n = 1$ and something else for $e^{2\pi i n}$. Is that due to the imprecision of the calculator or does the inequality follow ...
0
votes
0answers
39 views

Primes $p$ in which $3$ is a primitive root modulo $p$ [duplicate]

I want to show that if $3$ is a primitive root modulo $p$ if $p$ is a prime of the form $2^n+1$ for some $n>1$. First, I wrote $3^{p-1} \equiv 1 \mod p$. Then writing it as $(1+2)^{p-1}$, we see ...
2
votes
1answer
43 views

Which primes divide $x^2-5$?

Which primes divide $x^2-5$? What I have tried: If $p$ divides $x^2 -5 $ then: $$x^2= 5\pmod{p}$$ Therefore, from Euler's extended theorem we get that for primes s.t $\gcd(5,p)=1$ (which are all ...
0
votes
0answers
57 views

Determine a Normal Basis for Galois Extension of $\mathbb{Q}$ with primitive pth root of unit (p prime)

Let p be a prime, $\xi_p \in \mathbb{C}$ a primitive p-th unit root and $K = \mathbb{Q}(\xi_p)$. Give a normal basis for $K/\mathbb{Q}$. I know, that a basis of $L/K$ (finite and galois) is ...
3
votes
0answers
46 views

solutions of gold APN functions using trace function

The Gold APN is defined as $F(x)=x^{2^{k}+1}$ in $GF(2^n)$, where $\gcd(k,n)=1$. The differential uniformity computed using $F(x)=F(x+a)=b$ as following: $x^{2^{k}+1} + (x+a)^{2^{k}+1}=b$ $x^{2^{k}+...
0
votes
0answers
60 views

Relation between residues and primitive roots modulo $p$

I got a very satisfiying answer to my question on the relation between primeness and co-primeness of numbers which can be defined in a somehow symmetric way: $n$ is prime iff $$(\forall xy)\ ...
0
votes
0answers
42 views

Given 2 is primitive root (mod p), showing that every non-zero element of Z(p) is expressable as power of [2] (mod p)

I'm trying to find out how I would go about showing this: Given a prime number p >= 2, suppose 2 is a primitive root modulo p. Show that every non-zero element of Z(p) can be written as a power of [2]...
4
votes
1answer
69 views

Prove that $\eta - \omega \notin \mathbb{Q}$ where $\omega$ and $\eta$ are two differents n-th primitive roots $\in \mathbb{C}$

Let $n \in \mathbb{N}$ be a natural number, and be $\omega$ and $\eta$ two differents n-th primitive roots in $\mathbb{C}$. Prove that $\eta - \omega \notin \mathbb{Q}$ My attempt was to follow the ...
2
votes
1answer
65 views

PRIMES in P paper - Lemma 4.7 - why are the polynomials $X^m$ distinct in $F$?

I'm working through the original AKS paper, available here: https://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf. There's a single transition which I don't know how to justify, I will ...
0
votes
2answers
31 views

Let the extention $GF(p^m) \supset GF(p)$ that contains roots of $p(x)=x^{p^{m}}-1$. Show that those roots are distinct and that forms a field

I want to rewrite a question not so well written on this site and clarified by Mr. Lahtonen (thank you again). So here the question: Let the extention $GF(p^m) \supset GF(p)$ that contains roots ...
1
vote
1answer
135 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
172 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
119 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
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
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
286 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]$ ...