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.
127
questions with no upvoted or accepted answers
9
votes
0
answers
395
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 ...
- 3,917
7
votes
0
answers
144
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 '...
- 7,877
5
votes
0
answers
197
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,294
4
votes
0
answers
149
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 ...
- 199
4
votes
0
answers
134
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: ...
- 299
4
votes
0
answers
60
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,...$ (...
- 405
4
votes
0
answers
125
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,323
4
votes
0
answers
473
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
253
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 ...
- 39.2k
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?
- 281
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,666
3
votes
1
answer
232
views
Given a prime $p$ and a positive integer $a \not \equiv 0,1 \pmod p$, show that S = $\sum^{p-1}_{i=1} a^i \equiv 0 \pmod p$
The origin of this question is actually a different question:
Show that all primes except 2 and 5 divide infinitely many elements of $B :=\{1,11,111,1111,\cdots\}$.
It's relatively straightforward ...
- 2,621
3
votes
0
answers
249
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
1
answer
894
views
How to find primitive elements in $\operatorname{GF}(9)$
I have to find primitive elements of $\operatorname{GF}(9)$ in finite field. $p=3$, $k=2$, $q=9$.
Am I correct, I need minimal polynomials to be
$x^2$
$x^2 + 1$
$x^2 + 2$
$x^2 + x$
$x^2 + x + 1$ ...
- 39
3
votes
0
answers
96
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
67
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(...
- 17.8k
3
votes
1
answer
228
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 ...
- 405
2
votes
0
answers
61
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 ...
- 200
2
votes
0
answers
44
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
221
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,038
2
votes
0
answers
37
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 ...
- 806
2
votes
0
answers
114
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
186
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,556
2
votes
0
answers
1k
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
135
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
89
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
437
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
285
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
228
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,340
2
votes
0
answers
301
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,004
2
votes
1
answer
118
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
253
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.
- 3,743
2
votes
2
answers
763
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 ...
- 687
2
votes
0
answers
43
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,159
2
votes
0
answers
700
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,499
2
votes
0
answers
113
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 ...
- 1,953
2
votes
0
answers
70
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 $\...
- 281
1
vote
0
answers
32
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
94
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 ...
- 399
1
vote
2
answers
54
views
Characterizing generators for the multiplicative group of a finite field.
Fix a finite field $\mathbb{F}_p$ and consider its multiplicative group $\mathbb{F}_p^\times$, which we know is cyclic. Is there an general way to characterize this group's generators (the primitive $(...
- 686
1
vote
0
answers
83
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 $...
- 55
1
vote
0
answers
44
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
94
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
101
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 ...
- 6,812
1
vote
0
answers
60
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
69
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 $...
- 647
1
vote
0
answers
106
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 ...
- 183
1
vote
0
answers
73
views
How can these two arguments relate?
I found the excerpt here that said the second involves the p-adic analog of the above. How can these two statement related?
The transcendence of $2^{\sqrt2}$ and $e^\pi$: Gelfand's proof. (Assuming ...
1
vote
0
answers
51
views
Let $k\ge2$ and p an odd prime number. If $g^{p-1}\equiv1[p]$ and $g^{p-1} \not\equiv 1 [p^2]$ then $g^{p^k-1} \equiv 1[p^k]$
Let $k\ge2$ and p an odd prime number.
If
$$g^{p-1}\equiv1[p]$$
and
$$g^{p-1} \not\equiv 1 [p^2]$$ then
$$g^{p^k-1} \equiv 1[p^k]$$
I want to use this lemma:
$$g^n \equiv 1[p^k] \Rightarrow \phi(p^...
