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
1answer
107 views

Strategy of the proof of every prime number has a primitive root

I am going through number theory from the following book : https://www.saylor.org/site/wp-content/uploads/2013/05/An-Introductory-in-Elementary-Number-Theory.pdf On page 96, the proof is given that ...
4
votes
1answer
75 views

Distribution of primitive roots mod p

Let $p$ be a prime number. I am interested in knowing how many primitive roots mod $p$ there are; at least, gaining some insight into the distribution of primitive roots mod $p$. If I need to go ...
2
votes
1answer
46 views

Prove that there are exactly $\phi(p-1)$ primitive roots modulo a prime $p$

Note, in the proof below, I assume as proven the theorem that, if $d$ is any factor of $p-1$, then the equation $$\tag{1} x^d -1\equiv 0\pmod{p}$$ has exactly $d$ solutions, and I skip the details of ...
2
votes
0answers
25 views

Product of the primitive roots

If $p$ is a prime number, what is the product of elements like $g$ such that $1\le g\le p^2$ and $g$ is a primitive root modulo $p$ but it's not a primitive root modulo $p^2$? I am interested in the ...
2
votes
2answers
53 views

What are the chances of common generators? [closed]

Supposing $n=\prod_{i=1}^tp_i$ is odd and may not be square-free and $g$ generates each of multiplicative groups mod $\lambda(p_i)$ then what are the chances that $g$ generates multiplicative group ...
1
vote
1answer
25 views

Is $\bar{x}$ a primitive element in $\mathbb{F}_p[x]/(P(x))$

Let $\mathbb{F}_p$ be the finite field of $p$ elements (where $p$ is a prime) and let $P(x)\in \mathbb{F}_p[x]$ be an irreducible polynomial. I have to prove that $\bar{x}$ is a primitive element of $\...
3
votes
4answers
82 views

Orders of primitive roots

So I'm working through a textbook and the question asks: Consider the prime $p =13$. For each divisor $d = 1,2,3,4,6,12$ of $12= p-1$, mark which of the natural numbers in the set $\{1,2,3,4,5,6,7,8,...
3
votes
1answer
87 views

Why is $[\mathbb{Q}(\zeta):\mathbb{Q}] = 8$ and not $14$? (Where $\zeta$ is a primitive $15^{th}$ root of unity)

I have a field extension $\mathbb{Q}(\zeta)/\mathbb{Q}$, where $\zeta$ is a primitive $15^{th}$ root of unity. So, since $x^{15}-1 = \phi_{1}(x)\phi_{3}(x)\phi_{5}(x)\phi_{15}(x)$, where $\phi_{n}(x)$...
0
votes
1answer
51 views

Formal proofs for $f_p(a \cdot b) = f_p(a) + f_p(b) \mod p $?

Let $ x $ be coprime to an odd prime $p$. Then consider $$ f_p(x) = \frac{x^{p-1} - 1}{p} $$ By Fermat's little we know this is always an integer. In 1850 Eisenstein proved that $$ f_p(a \cdot b)...
0
votes
1answer
48 views

What is the value of (Vandermonde matrix)$^4~$?

This is Vandermonde matrix: $\omega$ is primitive N-root. What is $W^4$? I'm trying to calculate it but I don't know how exactly.... Thank you!
1
vote
1answer
25 views

Can at least one primitive root $w$ of $N$ be expressed as $a^2-b$, where $(b|N)=-1$

I am stuck on a thought experiment: can any (or for that matter, at least one) primitive root $w$ of $N$, $N$ prime, be expressed as $w=a^2-b$, where $(b|N)=-1$, and $a,b\in\mathbb{N}$. We know that ...
1
vote
1answer
34 views

More Clarification on the number of $I$th powers modulo $p$

Jack provides an answer and explanation as to how many $I$th powers there are modulo a prime $p$. However, I am unsure as to the logic behind the following step: When we apply the map $x\mapsto x^...
2
votes
2answers
116 views

About the existence of primitive root modulo prime

I was reading the theorem about the existence of an integer $t$, the primitive root modulo prime. The proof seemed a bit confusing. I mean the construction part. Why did not they immediately take $t = ...
0
votes
0answers
26 views

Let $w \in G_{63}$ be a primitive root of unity. Find all $n\geq 6$ such that $\sum_{k=6}^n w^{35k} = 0$ and $w^{12n} = w^{15}$

This is probably totally wrong. We know that $5$ and $63$ are relatively prime, therefore $w^5 \in G_{63}$ primitive (we'll suppose $w= w^5$ without loss of generality). We also know that $(w^7)^9 = ...
1
vote
0answers
51 views

Prove that numbers relatively prime to $n$ are congruent modulo $n$ to powers of primitive root of $n$

Suppose that we have $\gcd(a,n) = 1$ where $a$ is primitive root of $n$ and $\{a_1, a_2 .. a_{\phi(n)} \}$ are numbers less than $n$ which are relative prime to it. Show that this set of numbers is ...
0
votes
1answer
76 views

Rational coefficients of the prime roots of unity (basis set in $\mathbb{Q}$).

It is well known that the set of prime roots of unity $S = \{\zeta, \zeta^2, \zeta^3, ..., \zeta^{p-1}\}$ form a basis in $\mathbb{Q}$ (where $\zeta = e^{\frac {i2\pi}{p}}$, $p \in \mathbb{N}, p $ is ...
0
votes
0answers
34 views

Let $w\in G_{18}$ be a primitive root of unity. Prove that $w^{16} \sum_{j=1}^{17}(w^3 \overline{w})^{3j+1}$ is imaginary pure.

This is what I've got: $$w^3\overline{w}=w^3w^{-1}=w^2 \iff \\ w^{16} \sum_{j=1}^{17}(w^3 \overline{w})^{3j+1} = w^{16}w^2\sum_{j=1}^{17}w^{6j} = \bigg( \sum_{j=0}^{17}w^{6j} \bigg) - 1$$ Given that ...
2
votes
1answer
31 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
1answer
33 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 ...
0
votes
1answer
27 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 ${...
0
votes
0answers
23 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?
1
vote
2answers
84 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
46 views

Two definitions of a primitive root. [duplicate]

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 $\...
1
vote
1answer
45 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
27 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
22 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
25 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
38 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
81 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
36 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
0answers
26 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
1answer
45 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
37 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
27 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
44 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
179 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 ...
-1
votes
2answers
190 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
32 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
43 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
14 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
40 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
69 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
72 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
56 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}...
0
votes
1answer
50 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
40 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 ...