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.
126
questions with no upvoted or accepted answers
9
votes
0
answers
406
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 ...
- 4,027
7
votes
0
answers
164
views
Intuition behind this strange heuristic for primitive roots modulo $p$?
Let $p$ be an odd prime. Define $S(p)$ as the sum of all primitive roots modulo $p$ taken from $\left[-\frac{p-1}2,\frac{p-1}2\right]$.
Now here's the strange thing. If the primitive roots were '...
- 8,476
5
votes
0
answers
201
views
Spliting subspaces and finite fields
I'm sure that the following is true, but I can't prove it.
Let $R<S<K, R=\mathrm{GF}(q),\ S= \mathrm{GF}(q^n), \ K= \mathrm{GF}(q^{mn})$ be a tower of finite fields and
$A = \{\theta\in K: \...
- 1,364
4
votes
0
answers
165
views
Given an odd prime $p$, is there another odd prime $q$ such that $p$ is a primitive root modulo all powers of $q$?
As the title says, I want to know if for every odd prime $p$, there is another odd prime $q$ such that $p$ is a primitive root modulo $q^m$ for all $m\ge1$. For small $p$ such as $p=3,5,7$, I could ...
- 271
4
votes
0
answers
142
views
How to solve the equation in algebraic number theory?
First step: When $p\equiv 1 \pmod{ 3}$, prove that there exists a pair $(a,b)$ of integers such that $4p=a^2+27b^2$, $a\equiv 1 \pmod{ 3}$ and a is unique (the proof of the first step).
Second step: ...
- 319
4
votes
0
answers
61
views
Probability of a prime $p=3\pmod 4$ occurring in A213052
As you may notice, A213052 contains primes mostly congruent to $1\pmod 4$ (in fact, all of the known ones are except $3$).
Consider the sequence of smallest primes $p_n$ such that $2,3,5,7,11,13,...$ (...
- 447
4
votes
0
answers
160
views
Is there a deeper reason for the classification of moduli in which a primitive root exists?
The primitive root theorem classifies the set of moduli for which a primitive root exists as $$1,2,4,p^k,2p^k$$ where $p$ is an odd prime and $k$ is a positive integer.
I have worked through a proof ...
- 3,415
4
votes
0
answers
606
views
Primitive element and choice of irreducible polynomial
It is known that every finite field of the same order $p^k$ are isomorphic. So, $F_p[x]/\langle q(x)\rangle$ leads to the same field for any choice of irriducible k-degree $q(x)$ over $F_p[x]$. But, ...
- 309
4
votes
1
answer
271
views
Count of lower and upper primitive roots of prime $p \equiv 3 \bmod 4$
I was exploring the layout of primitive roots of primes over a reasonable range and this question concerns the number of primitive roots either side of $p/2$.
Many primes have an exact match between ...
- 40k
4
votes
0
answers
96
views
About primitive roots and primes.
For any odd prime $p$ there exists at least one prime $q < p$ such that $q$ is a primitive root $\text{mod } p$ ; is this true?
- 279
3
votes
0
answers
67
views
A sum of root of $-1$ modulo n
Find the sum of positive integers $n$ less than $2021$ such that $n^{3 \cdot 7 \cdot 23} \equiv -1 \pmod{2021}$.
I was making an elementary number theory problem using the year number $2021=43 \cdot ...
- 1,901
3
votes
0
answers
366
views
Show that 1/p has period p-1 iff 10 is a primitive root mod p
I have this excersice, and i want verify my proof:
Let $p$ be a prime, then $1/p$ has period $p-1$ iff 10 is a primitive root $\mod p$.
My attempt:
$\rightarrow)$ Let $\frac{1}{p}=0,\overline{a_1\...
- 451
3
votes
0
answers
106
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}+...
- 215
3
votes
0
answers
69
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:
$$g(...
- 18.3k
3
votes
1
answer
256
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 ...
- 415
2
votes
0
answers
26
views
If $u$ is a non-primitive root modulo $p$ then do there always exist non-primitives $v,w$ such that $u+v,v+w,w+u$ is primitive?
Let $p$ be a prime number $\geq 17$ and $u$ be a non-primitive root modulo $p$. Let $\{v_{1},v_{2},\cdots, v_{n}\}$ be the set of those non-primitive roots modulo $p$ such that $u+v_{i}$ is primitive. ...
- 69
2
votes
0
answers
64
views
Artin's conjecture on primitive roots for perfect powers
Let $a\neq -1,0,1$ be an integer. Write $a=(b^2c)^k$, where $b^2c$ is not a perfect power, and $c$ is squarefree. Artin's conjecture on primitive roots states that the asymptotic density of the set of ...
- 1,945
2
votes
0
answers
55
views
When does this Galois theorem "variation" holds?
Im reading about solvability by radicals in different books, more concretely in Fields and Galois Theory by Patrick Morandi and Introduction to abstract algebra by Benjamin Fine, etc. In the second ...
- 23
2
votes
0
answers
104
views
Is it possible to create factors of $p_n\#$ which cannot create any primitive root of $p_{n+1}$?
(Edited for clarity.)
Take the primorial of the $n$th prime $p_n$ by using $H=\prod_{i=1}^np_i$.
Does there exist an $n$ such that there exists $d\mid H$ where there are no factors of $d^{p_{n+1}-1}$ ...
- 8,185
2
votes
0
answers
88
views
Cyclotomic Polynomials and The Existence of Infinite Prime Power
Prove that there exist infinitely many positive integers n such that all prime divisors
of $n^2 + n + 1$ are not greater than $\sqrt{n}$
This is a problem related to cyclotomic polynomial. It is ...
- 297
2
votes
0
answers
83
views
Finding primitive roots including negative sign
I commonly run into the following question such that if $p$ and $q=4p+1$ are both odd primes prove that $2$ is primitve root modulo q . However , i could not prove it for other number that are given ...
user1121946
2
votes
0
answers
303
views
A primitive root modulo $p^k$ is primitive modulo $p^{k+1}$,for $k\geq 2$.
I am a graduate student of Mathematics.I am stuck with the following number theory problem:
Let $p$ be an odd prime.Prove that any primitive root modulo $p^k$ is a primitive root modulo $p^{k+1}$, for ...
- 3,703
2
votes
0
answers
42
views
Quadratic number fields that contain primitive root of unity
Find all quadratic fields $\mathbb{Q}[\sqrt{d}]$ that contain some $p$-th primitive root of unity, where $p>2$ is a prime.
Now, my reasoning was: if $\mathbb{Q}[\sqrt{d}]$ contains one $p$-th root ...
- 826
2
votes
0
answers
142
views
How to find an irreducible polynomial over a finite field with a primitive root (and low hamming weight)
I found there that a polynomial in $F[x]$ with $|F| =q $ with degree $n$ will have its roots in $K$ of order $q^n$
Here, I found that either all the roots are primitive or none of them are.
I am ...
2
votes
0
answers
215
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 ...
- 3,618
2
votes
0
answers
2k
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 ...
- 21
2
votes
0
answers
137
views
Theorems on Primitive Roots
Let g be a primitive root modulo $p$($p$ is an odd prime) with $g^{p-1}\ncong{1}\ (mod\ p^{2})$. I am interested in proving that
$$g^{(p-1)p^{m-2}}\ncong{1}\ (mod\ p^{m})$$ for every $m\geq{2}$
So ...
- 153
2
votes
0
answers
90
views
How to prove that all the eigenvalues of this matrix have modulus $\sqrt{n}$?
Let $\zeta$ be a primitive $n$-th root of unity.
Prove that all eigenvalues of the matrix $\left(\begin{matrix} 1 & 1 & 1 & \cdots & 1\\ 1 & \zeta & \zeta^2 & \cdots & ...
- 81
2
votes
1
answer
483
views
If g is a primitive root modulo $N$, then g is a primitive root modulo $D$, where $D|N$.
Let g be a primitive root modulo $N\ge2$ and $D\ge 2$ a divisor of $N$. Show that the reduction modulo D of g is a primitive root modulo D.
I've tried using Gauss' Theorem, but I'm not quite sure how ...
- 29
2
votes
0
answers
299
views
Subgroups and corresponding fixed fields of Galois group of primitive 24th root of unity.
I have been asked to determine the lattice of subgroups of $G=\Gamma(\mathbb{Q}(\zeta):\mathbb{Q})$ where $\zeta$ is a primitive $24^{th}$ root of unity. I am then asked to determine their ...
2
votes
0
answers
243
views
Are non-squares primitive roots?
We know that even squares cannot be primitive roots modulo primes.Are all other natural numbers primitive roots mod some p?
My heuristic argument goes as follows: the probability that a natural ...
- 1,380
2
votes
0
answers
304
views
Primitive elements of finite fields
Let $p$ be a prime number and $q=p^n$ for some positive integer $n$. $F_q[x]$ is the polynomial ring with coefficients in $F_q$. For any $M(x)\in F_q[x]$, define $\mathcal{R}(M(x))\subset F_q[x]$ to ...
- 1,082
2
votes
1
answer
128
views
Show that if ab has a primitive root with $(a,b) = 1$, then $a<3$ or $b<3$
Show that if $ab$ has a primitive root with $\gcd\left(a,b\right) = 1$, then $a<3$ or $b<3$
I have no idea how to start this question at all...
One is that I do not see how 3 is related to ...
2
votes
1
answer
338
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.
- 4,267
2
votes
2
answers
860
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 ...
- 717
2
votes
0
answers
44
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 ...
- 6,263
2
votes
0
answers
778
views
When is 2 a primitive root for a Sophie Germain prime $p$ or its associate $2p + 1$?
A prime $p$ is a Sophie Germain prime if its associate $2p + 1$ is also prime.
When is $2$ a primitive root for a Sophie Germain prime $p$ or its associate $2p + 1$?
A previous question found that a ...
- 1,547
2
votes
0
answers
122
views
Lower bound for the values of cyclotomic polynomials evualuated at integers
Let $b,n \geq 2$ be integers and let $\Phi_n(b)$ be the value of the $n$-th cyclotomic polynomial evaluated at $b$. I've recently noticed by computer experiments that whenever $n$ is odd, we seem to ...
- 2,003
2
votes
0
answers
72
views
A multivalued function $ f(x) = 0 $ with integer solutions $ x_1=p(n) $ and $x_2=q(n) $
Please help me to define a multivalued function $ f(x) = 0 $ with integer solutions :
$ x_1 = p(n)$ and $ x_2 = q(n) $
such that
$\dfrac{ p(n) + q(n) } { 2 } = 2 n + 1 $
and
$ \...
- 21
2
votes
0
answers
53
views
About primitive roots and ways of expressing them.
If $q$ is a primitive root mod $p$ and $q = (2^a)(3^b)(5^c)\pmod p$ for some $a,b,c$ all elements of integers then say that this $q$ has the 'form' $\{2,3,5\}(p)$. Then is it true all the residues $\...
- 279
1
vote
0
answers
42
views
Vinogradov's proof that $U_{p^{\alpha}}$ is cyclic. How to prove $p^{r-1} (p-1) \mid \delta$ for $1 \leq r \leq \alpha$
The proof of Vinogradov that $U_{p^{\alpha}}$ ($\alpha \geq 1$) is cyclic for an odd prime $p$, has a part that I don't understand.
We take $g$ a primitive root of $U_p$.
And, at a certain point of ...
- 1,245
1
vote
0
answers
47
views
$(a+pk)^{p-1}≡1+ph−pka^{p−2} \mod{p^2}$, for some $h∈\mathbb{Z}$; if $k≢ah \mod{p}$, then $a+pk$ is a primitive root mod $p^2$.
Started an introductory number theory class and totally stuck on some homework after hours of effort. Feel like I'm so close but can't do the final bit to solve it and starting to wonder if my ...
- 11
1
vote
0
answers
341
views
Prove that the roots of cyclotomic polynomial $\Phi_{p-1}(x) \equiv 0 (mod~p)$ are exactly the primitive roots mod p
$p$ is a prime, and $\Phi_{p-1}(x)$ denote the cyclotomic polynomial of order $p-1$. And I want to show the following:
$g$ is a solution of the congruence $\Phi_{p-1}(x) \equiv 0 (mod~p)$ if and only ...
- 425
1
vote
0
answers
92
views
Number of roots in cyclotomic polynomial $\Phi_{15}[x]$ in $\mathbb F_p$
I'm trying to understand why if the $gcd(p-1, 15) = d \neq 15$, then there are zero roots (since if it's $=15$, there are exactly 8). I was thinking that since a solution to $x^d - 1$ is relevant if $...
- 47
1
vote
0
answers
48
views
I've followed two different methods to find congruence with primitive roots but have two different answers
So I'm using the fact that 2 is a primitive root modulo 53, I'm solving $x^5 \equiv 8\mod{53}$
Originally I was trying to rewrite both sides in terms of two so had the following:
let $x=2^y$ for y ...
- 11
1
vote
0
answers
135
views
How can you use a primitive root to solve a modular congruence?
I've read through this answer to get some ideas: Solving a congruence using a primitive root
But my problem is slightly different and it's thrown me off in terms of understanding the logic.
I have $ x^...
- 73
1
vote
0
answers
186
views
For what primes is $6$ a primitive root?
While thinking about an unrelated problem, I had to decide whether $6$ was a primitive root with respect to multiple prime moduli. I could discover no obvious pattern as to primes for which $6$ is a ...
- 7,523
1
vote
0
answers
69
views
Solving the equivalent congruence I found and using it to derive the solution to the original congruence (elementary number theory)
I am trying to solve following problem. I have done the entire problem, so I'm not asking anyone to do the problem for me. But I need some confirmation on whether or not the very last part of my ...
1
vote
0
answers
83
views
Some problems on primitive roots and divisors in number theory.
I have two questions:
Let $n>1$ be a positive integer that isn't a perfect power. Is $n$ a generator mod infinitely many primes?
Let $C,x,y$ be pairwise coprime integers $\in \mathbb{N}$. Let $...
- 755
1
vote
0
answers
122
views
A Primitive element in Finite Fields
My question is about the roots of unity in finite fields. It goes like this:
Suppose we have two primes p and q, both greater than 3, which satisfy $q|(p-1)$. Then there exists a $q$-the root of unity ...
- 321